본문 바로가기

백트래킹19

백준 1035 자바 - 조각 움직이기 (BOJ 1035 JAVA) 문제 : boj1035 처음엔 그리디로 풀어보려 했지만, 별다른 규칙을 찾지 못했다. 와중에 생각해보니 어차피 5x5 밖에 안되고, 조각은 최대 5개 이므로 최악의 경우라도 O(25^5*25*5) 정도로 풀 수 있다. 25^5는 5x5 크기의 보드에 5개의 조각을 모든 위치에 놓는 경우의 수이고, 해당 경우의 수에 대해 *25는 그 중 하나의 조각을 찾는 것이고, *5는 5개가 인접해있는지 확인하는 것이다. 저대로는 당연히 불가능하지만, 여기에 백트래킹을 더해서 이미 나왔던 최소 이동 횟수 이상이라면 해당 경우의 수와 그 이후의 경우의 수를 중간에 중지하는 방식으로 진행한다면 어느정도 가능할 것 같아서 일단 해봤다. 참고로 이 경우 모든 경우의 수는 조각이 n개 있었다면 다음과 같이 확인하면 된다. 1... 2022. 3. 21.
백준 9997 자바 - 폰트 (BOJ 9997 JAVA) 문제 : boj9997 1,2,3에 걸쳐서 점점 효율성이 좋은 풀이를 설명할 겁니다. 그러니 최종적으로는 '3'만 보셔도 되긴합니다. 왜 그렇게 설명하냐면 제가 그렇게 풀었기 때문입니다 ㅋㅋㅋ 시간 제한 딱 맞춰서 푸는건(1초제한인데 백준에서 자바로 제출할 시 '원래시간*2+1'초 이므로 자바로는 3초제한 이었어요.) 뭔가 기분나빠서 줄이다보니 줄여지네요. 1. 우선 빠듯하게 가능한 풀이 우선 모든 경우를 살펴보는게 가능할지 생각해보면, O(2^25*100*26)가 필요하다(2는 해당 문자를 사용하거나, 안하거나이고 25는 N의 최대수치, 100은 단어 길이의 최대수치, 26은 a~z 모든 문자가 포함되었는지 확인). 상당히 빠듯하긴 하지만, 어찌보면 할만해 보이므로 일단 해봤다. 이 때 단어 길이는 1.. 2022. 3. 20.
백준 1590 자바 - 캠프가는 영식 (BOJ 1590 JAVA) 문제 : boj1590 n개의 경우 각각에 대해 만족하는 가장 작은 시각을 찾아보면 된다. n개의 경우 각각에 대해 a가 0부터 C-1까지의 자연수라고 할 때, 다음 식을 통해 나온 값 중 최초로 T 이상의 값이 나오는 경우가 해당 경우의 최소수치이다. n개에 대해 각각 위의 최소수치를 구하고, 그 중 가장 작은 값이 답이다. 이 때 C는 최대 100 이므로 0부터 99까지 전부 다 해봐도 최대 O(NC) 정도의 시간복잡도이므로 전부 다 해보면 된다. 따라서 브루트 포스이며, 최초로 T 이상의 값이 나올 경우 바로 중지하면 되고 추가로 f(a)가 이미 이전에 나온 값보다 큰 경우엔 더이상 볼 필요도 없으므로 백트래킹도 가미하면 좀 더 효율적으로 할 수 있다. 코드에서 while문 내의 's < t'부분이.. 2022. 2. 6.
백준 2239 자바 - 스도쿠 (BOJ 2239 JAVA) 문제 : boj2239 row기준 9개, 세로기준 9개, 3x3으로 나뉜 9개에 모두 1~9가 하나씩 들어가기만 하면 된다. 따라서 로직은 다음과 같다. 1. 입력에서 0이 아닌 칸에 대해 위 3개의 조건을 체크한다. 2. 0인 칸 모두에 대해 차례대로 1~9중 들어갈 수 있는 숫자를 무작정 넣어본다. 3. 그렇게 해서 0인칸 모두를 채울 수 있는 경우가 나온다면 그대로 출력하면 된다. 그렇지 않다면 바로 직전 단계로 돌아가서 다른 수를 넣어본다.(따라서 백트래킹 문제이다.) 다음 스도쿠 이미지를 보자. 저 빨간부분에는 우선 row를 기준으로 보면(초록색 선) 아직 체크안된 값은 1과 4이다. 그리고 col기준(파란선)으로 보면 역시 1과 4가 들어갈 수 있다. 격자 기준(연두색)으로 보면 1,4,9가 .. 2022. 1. 26.
백준 2580 자바 - 스도쿠 (BOJ 2580 JAVA) 문제 : boj2580 row기준 9개, 세로기준 9개, 3x3으로 나뉜 9개에 모두 1~9가 하나씩 들어가기만 하면 된다. 따라서 로직은 다음과 같다. 1. 입력에서 0이 아닌 칸에 대해 위 3개의 조건을 체크한다. 2. 0인 칸 모두에 대해 차례대로 1~9중 들어갈 수 있는 숫자를 무작정 넣어본다. 3. 그렇게 해서 0인칸 모두를 채울 수 있는 경우가 나온다면 그대로 출력하면 된다. 그렇지 않다면 바로 직전 단계로 돌아가서 다른 수를 넣어본다.(따라서 백트래킹 문제이다.) 예를들어 기본 예제를 약간 변경한 다음 스도쿠 이미지를 보자. 저 빨간부분에는 우선 row를 기준으로 보면(초록색 선) 아직 체크안된 값은 1과 4이다. 그리고 col기준(파란선)으로 보면 역시 1과 4가 들어갈 수 있다. 격자 기.. 2022. 1. 26.
백준 18511 자바 - 큰 수 구성하기 (BOJ 18511 JAVA) 문제 : boj18511 N이 최대 1억이고, K의 각 원소는 1부터 9 까지이므로 어쨌든 8자리 수 이내로 모든 답이 나온다. 그리고 K는 최대 3개까지이므로 모든 경우를 봐도 최대 O(3^8) 이다. 따라서 따로 다른 방법 생각해볼 것 없이 브루트 포스로 풀면 된다. 약간의 백트래킹을 넣어서 예를들어 이미 N보다 큰 값이라면 더이상 볼 것 없이 종료하는 식으로 하면 된다. 백트래킹 개념을 넣지 않아도 시간내에 통과 가능한 간단한 문제이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private int max =.. 2022. 1. 3.
백준 2014 자바 - 소수의 곱 (BOJ 2014 JAVA) 문제 : boj2014 1. 문제 이해 문제를 다소 이해하기 힘들 수 있는데 문제를 이해하기 쉽게 써보면 다음과 같다. 예를들어 2,5,7이 입력으로 주어졌다면 이하의 수식으로 나온 결과 중 N번째로 작은 수를 구하면 되는 것이다. (단, i,j,k가 모두 0이면 안됨. 그리고 K(k와 다름. 문제에서 주어진 K) 가 늘어나면 물론 i,j,k 외에도 더 추가해주면 됨.) 2. 해결 로직 생각해보기 근데 i, j, k를 임의로 정해서 작은 수를 찾기에는 뭐부터 해야지 작은수부터 차례대로 나올지 알 수 없다. 또한 무한정 i, j, k를 늘려나가기엔 당연히 무리가 있다. 따라서 처음에 주어진 K개를 모두 넣어두고 작은 수부터 차례대로 K개의 소수를 곱해 넣고, 그 결과중에서도 다시 작은 수부터 차례대로 K개.. 2021. 12. 12.
LeetCode 5 - Longest Palindromic Substring - Medium (Java) LeetCode도 자주 들어봤는데 한번도 해본적은 없어서 한번 풀어봤다. 일단 시간 제한이 안써있으면서 TLE(시간초과)는 뜨는게 상당히 거슬린다. 시간제한 알려주든가! 프로그래머스도 그게 좀 불만인경우가 많은데.. 그리고 남의 코드를 못본다는 점이 상당히 아쉬워서 메인 OJ(Online Judge)로는 별론 것 같다. 그래도 유명한 사이트니 간간히 생각날 때 하나씩 풀어보게 될 것 같다. 처음 해보는 사이트라 여기저기 눌러보다보니 DP 태그가 붙어있는걸 봤다. 이미 태그를 봐버린 이상 태그대로 푸는건 자존심 상하기도 하고 어차피 Brute Force(이하 BF)로도 가능할 것 같아서 BF(하지만 Back Tracking을 좀 끼얹은)로 풀어봤다. 1. 단순히 모든 경우를 보도록 짜게되면 다음과 같이 짜.. 2021. 11. 30.
백트래킹 알고리즘 (Back Tracking) 다음과 같은 그래프가 있다. 여기서 1부터 시작해서 숫자 순서대로 얼마나 멀리 갈 수 있는지 찾고싶다. 즉 1->2->3->4->5->... 이런식의 루트를 찾으려 한다. 우선 생각해볼 수 있는 방법은, 그냥 모든 루트에 대해 DFS 등을 사용해 전부 탐색해 보는 것이다. 이 방식이 이전에 작성한 Brute Force 방식이다. 그냥 컴퓨터의 빠른 연산력에 기대어 모든 경우를 확인하는 것이다. 위는 모든 경우를 살펴보는 DFS 과정의 순서를 표시한 것이다. 모든 경우를 확인해보니 결국 1->2->3->4를 찾긴했다. 그런데 우린 직관적으로, 중간과정에서 이미 순서가 안맞다면 해당 루트로는 아예 안가봐도 될 것임을 알 수 있다. 그럼 다음 이미지를 보자. 위와 같이 답이 될 가능성이 없는 경로라면 더이상 .. 2021. 10. 3.

티스토리툴바