dfs
-
BOJ) 신기한 소수알고리즘/백준 2020. 7. 21. 15:15
신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수� www.acmicpc.net 풀이 처음에는 모든 숫자에 대해 DFS를 진행하면서 답을 구하려고 시도했다. 하지만 문제의 최대 조건인 n=8인 경우에 엄청난 시간이 소요되면서, 가지치기가 더 필요한 것을 느꼈다. 문제의 조건을 자세히 봤다. n=4 인 경우에 나오는 수를 살펴보면, 첫번째 자리에는 {2,3,5,7} 만 오고 나머지 자리에는 {1,3,7,9}만 나와있음을 확인했다. 이 말은, n=3인 경우, n=2인 경우에도 앞의 자리가 위의 네가지 숫자 말고는 올 수..
-
BOJ) 분해합알고리즘/백준 2020. 7. 21. 15:03
분해합 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+ www.acmicpc.net 풀이 어떤 자연수 M과 N이 있을 때, M과 M의 각 자릿수 합이 N이되는 수의 최소값을 구하는 문제다. 범위를 어떻게 줄일지 생각이 나지 않아서, 일단은 DFS로 모든 경우의 수를 만들어서 검증했다. 자릿수 만큼 숫자를 만들고, 문제의 조건에 맞다면 최소값을 최신화해줬다. 메모리와 시간이 너무 보기 싫었다. 범위를 어떻게하면 줄일 수 있을지 생각하다가, 주어진 숫자의 각 자릿수가 9로만 이루어진 경우가 해당 자릿수에서 나올 수 ..
-
BOJ) 단어 수학알고리즘/백준 2020. 7. 18. 22:23
단어 수학 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 N개의 단어를 각각 숫자로 바꿔서 모두 더한 값 중 최대값이 되는 경우를 출력한다. 이 때, 단어에 포함되는 알파벳의 갯수는 10개 이하이며, 0~9 사이의 값을 적절하게 배치했을 때의 최대값을 구하는 문제다. 처음에는 각 알파벳이 가질 수 있는 값의 모든 경우의 수를 DFS를 통해 저장했다. 입력 받을 때, HashMap에 각 char의 index를 저장하는 식으로 문제를 풀었는데, 메모리와 시간이 매우 비효율적이었다. 생각 덜하고 빠르게..
-
BOJ) 암호 만들기알고리즘/백준 2020. 7. 18. 21:47
암호 만들기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 C 개의 문자 중 L개를 선택해서 만들 수 있는 암호를 출력하는 문제다. 이 때, 암호는 모음(a,e,i,o,u)이 최소 하나 이상 자음이 두개 이상인 조합만 가능하다. 또한, 모든 암호의 경우를 사전순서대로 출력해야한다. 위의 두 조건을 충족하기 위해 C개 중 L개를 선택하는 것은 DFS를, 사전 순서대로 하기 위해 정렬을 선택했다. DFS이후에 정렬을 하기에는 너무 많은 시간과 메모리를 낭비할 것 같아서 입력 받자마자 정렬을 해주었다. DFS에서..
-
BOJ) 체스판 위의 공알고리즘/백준 2020. 7. 11. 20:55
체스판 위의 공 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙�� www.acmicpc.net 풀이 체스판의 크기가 500x500이지만, 공들이 옮겨가면서 0인 부분이 많이 생길거라고 생각하고 DFS로 진행했다. 하지만, 6%에서 시간초과가 떴고 DFS로는 풀 수 없는 문제라고 생각이 들었다. 그래서 인접한 칸들 중 가장 작은 숫자로 이동한다는 조건을 보고, find-union을 응용하면 풀 수 있을거라고 생각했다. 일단, union부분은 필요가 없다고 생각을 했다. 생각하기도 복잡해지고, 타고 타고 이동해야하는 특성상 paren..
-
BOJ) 유기농 배추알고리즘/백준 2020. 7. 8. 19:53
유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 풀이 이 문제도 grouping 문제여서, find-union을 써볼까 했지만, 크게 효율적일 것 같다는 느낌이 없었고, 이 문제에 적용하기에는 조금 복잡해질 것 같다고 생각했다. 그래서 그냥 BFS로 풀었다.. ㅎㅎㅎ 총 세번을 제출했고, BFS, BFS, DFS 순으로 제출했다. 첫번째는 평소에 풀던 것 처럼 grouping을 해주면서, gourping이 끝난 이후 저장된 groupIdx를 출력해줬다. 하지만, group을 지어서 값을 변경하거나 이용하지..
-
BOJ) 파이프 옮기기 1알고리즘/백준 2020. 7. 8. 19:37
파이프 옮기기 1 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 옮길 수 있는 모든 경우의 수를 찾는 문제기 때문에 브루트포스 문제다. 직접 다 돌리는데는 BFS나 DFS만큼 편한게 없다고(?) 생각해서 DFS로 풀었다. 문제를 풀면서 막혔던 부분은 첫째로, 문제 조건을 잘못 이해했다는 것이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수 이 문구에서 N,N을 보지 않고 N,y or x,N으로 이동한 파이프들을 구해줬었다... 두번째로는 실수라기 보다는 기둥의 시작점..
-
BOJ) 숫자판 점프알고리즘/백준 2020. 7. 6. 18:01
숫자판 점프 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 풀이 5x5 크기의 숫자판에서 숫자 6개를 골라, 만들 수 있는 숫자의 갯수를 구하는 문제다. 또한, 000001 or 000000과 같은 숫자가 허용되고 이동할 때는 먼저 거쳐간 칸을 다시 거쳐가도 된다는 조건이 있다. 따라서, int형보다는 String으로 문제를 푸는 것이 적합하다고 생각했고, visit이 필요없는 문제였다. 그래서 처음에는 dfs안에서 좌표 for문을 돌면서 각 좌표 상하좌우에 있는 ..