재귀 23

[BOJ] 14752. 개미굴

Trie와 DFS를 활용한 문제였다. Trie를 활용하기 위해 Node라는 클래스를 만들고, 그안에 child라는 Map구조의 Node를 주었다. 일반 적인 Trie문제와 다르게 배열대신 Map을 활용해보았다. 그렇게 모든 입력들을 root아래 저장 후, DFS를 활용하여 출력을 해주었다. 단, 이때 알파벳순 출력이 필요하기때문에 Map의 keySet을 정렬된 리스트의 형태로 만들고 문제를 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61..

Algorithm 2021.07.20

[BOJ] 12865. 평범한 배낭

유명한 Knapsack 문제이다. Knapsack 대표적인 문제이다. 보통 Knapsack 문제를 접근할때는 크게 두가지 방법이 있다. 크게 브루트포스와 dp로 접근할 수 있다. 브루투포스로 접근은 단순하게 고르고, 안고르고를 반복하며 재귀호출하는 방식이다. 이 방식은 시간복잡도가 2^N 이기에 대다수의 문제에서 적용이 힘들다. 이 문제또한 N의 최대값이 100이기에 적용이 불가하지만 한번 코드는 작성해보았다. 1. 브루트 포스(시간초과) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 package algostudy2..

Algorithm 2021.06.12

[BOJ] 9202. Boggle

Trie와 백트래킹을 이용한 시뮬레이션 문제이다. 이 문제를 맨처음 보았을 때 일종의 사전 개념인 처음 5개의 입력을 보고 Trie 알고리즘을 사용할 생각을 하였다. 그리고 map이 4x4로써 크지 않고, 주어진 시간도 10초로 충분하여서 백트래킹을 통해 만들어질수 있는 모든 단어에 대해 Trie search를 해주는 방식으로 접근하였다. 여러가지 알고리즘이 혼합되어 있는 형태이기때문에 작은 실수만 해도 어려워 질수 있었던 문제였다. Trie와 다른 알고리즘을 같이 사용해볼 수 있던 좋은 문제였던 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ..

Algorithm 2020.09.12

[Programmers] 괄호 변환

2020 카카오 문제였다. 이 문제는 옳은 괄호를 찾는 문제인데, 재귀를 이용해서 푸는 문제였다. 다만 이 문제에서는 재귀의 모든 과정을 문제에서 제공해주었고, 단순 구현만 하면 되는 문제였다. 따라서 문제의 제공되어있는데로 그대로 재귀를 구현하여 쉽게 풀 수 있었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 8..

Algorithm 2020.09.03

[BOJ] 1992. 쿼드트리

재귀를 이용한 분할정복 문제였다. 처음에 문제를 보고 이해하는데 오래걸렸다. 이문제는 전체 그림을 4등분하여 같은 숫자를 가진다면 하나의 숫자로 묶는 문제였다. 찾아야하는 범위의 숫자가 계속 반(나누기2) 되는 성질을 보니 재귀를 이용하여 풀수 있을 것 같았다. 그래서 함수 하나를 만들었고, 조건을 만족하지 못한다면 4방향에 대해 범위를 반으로 줄여서 계속 호출해주었다. 이 문제를 풀면서 100%에서 계속 틀렸었는데, 이유는 N=1, N=2인 경우에 문제와 다르게 푼경우가 생겼기에 계속 틀렸다. 항상 예외처리를 할땐 최대와 최소를 의심하는 습관을 들여야겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 3..

Algorithm 2020.08.27

[BOJ] 13460. 구슬 탈출 2

DFS를 이용하여 풀수 있는 문제이다. 일단 문제에서 10번이하로 움직인다는 조건을 주었다. 조건을 가지고 생각해보았을때 현재 구슬을 굴릴수 있는 방향은 4방향이 있고 10번을 굴린다 생각하면 전체가지수는 4^10이 나오게 된다. 4^10은 1,048,576‬ 로써 충분히 완전탐색을 할수 있는 시간이 나온다. 하지만 좀더 최적화가 가능하기에 생각을 해보았다. 맨처음 구슬을 굴릴땐 4방향 다 굴릴수 있지만 그다음부턴 2방향으로만 굴릴수있다. 예를 들어 맨처음 위쪽으로 굴렸다 가정해보자면, 구슬은 벽을 맞닿을때까지 구르기 때문에 다음번엔 위쪽으로 굴리는 것은 무의미한 경우를 가지게 된다. 또한, 반대방향이 아래쪽으로 굴리는 경우는 다시 그 전 상태로 되돌아가기 때문에 그것 또한 무의마하게 된다. 그래서 결론..

Algorithm 2020.06.05

[SWEA] 5215. 햄버거 다이어트

knapsack 유형의 문제이다. 이 문제는 조합을 통하여 풀수 있는데 조합을 구현하는데 두가지 방법을 사용해보았다. 1번은 선택-비선택 재귀호출으로 구현하였고, 2번은 visit배열은 이용한 백트래킹 조합을 사용하여 구현하였다. 또한 두가지 방법모두 가지치기가 상당히 중요한 요소이므로 잘생각할 필요가 있다. 방법1 : 선택,비선택 재귀 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 package swea; import java.io.BufferedReader; import jav..

Algorithm 2020.05.29

[SWEA] 3234. 준환이의 양팔저울

순열 재귀를 이용하여 푸는 문제이다. 주어진 추를 왼쪽에 놓을때, 오른쪽에 놓을때의 경우를 재귀로 호출하며 풀수있는 문제이다. 다만 여기서 주의할점이 있다. 저울이 양쪽이기에 N개의 추가 있다면 2^N * N!을 총가지수로 가지기 때문에 가지치기가 상당히 중요한 문제이다. 따라서 다음과 같은 가지치기를 하였다. 우선 오른쪽저울에 추가해도 왼쪽저울을 안넘을때 오른쪽 저울에 추가하는 가지치기와 만일 현재왼쪽의 총합*2가 sum을 넘는다면 뒤쪽은 다안보고 한번에 모든 경우를 더해주는 방식으로 가지치기를 하여 시간초과를 통과하였다. 단순한 재귀 문제이지만 가지치기를 하는 방식을 곰곰히 생각해봐야하는 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..

Algorithm 2020.05.29

[BOJ] 1987. 알파벳

백트래킹을 이용하여 경로를 찾는 문제이다. 백트래킹 DFS 경로문제는 일반 재귀를 사용하는 DFS와는 다르게 방문체크를 호출전에 해줘야한다는 점이 특징이다. 그후 호출이 끝난다면 당시 방문해제를 해줘야한다. 이점을 유의한다면 쉽게 풀수 있었던 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 package online.practice; import java.io.BufferedReader; import java.io.InputStream..

Algorithm 2020.05.27

[BOJ] 2580. 스도쿠

백트래킹을 이용하여 빈칸의 숫자를 확인해가는 문제이다. 문제를 맨처음엔 행의 개념으로 접근하여 행마다 0의 갯수를 세어주고 다 채우면 다음행으로 가고를 반복하는 방식으로 접근하였는데 시간초과를 해결할수 없었다. 그래서 두가지 방법을 생각해냈다. 0의 위치만 List로 저장하는 방법과 행의 개념이 아니라 칸의 개념으로 depth를 81까지 확인하는 방법을 생각해냈다. 생각해낸 두번째 방법으로 구현을 직접 구현을 해보았고, check라는 함수를 만들어 행,열, 사각형 반경을 체크해주었다. 옛날에 풀었던 문제지만 다시 풀어보았다. 다시 풀어보니 접근법을 너무 어렵게 가져가서 힘든 부분이 있었다. 단순하게 생각하는게 필요할것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..

Algorithm 2020.05.27