프로그래민👨‍💻

재귀를 이용하여 분할정복을 하는 문제이다. 아이디어를 생각하기까지 오랜시간이 걸렸다. 삼각형의 가장 꼭대기 점을 기준으로 아래에 있는 두 개의 삼각형을 호출해주는 형식으로 풀었다. 그리고 기저조건으로는 높이로 가져가는 size가 3이 되면 출력해주도록 해주었다. 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 package chap06; import java.io.BufferedReader; import java.io.InputStreamReader; public clas..

재귀를 이용하여 분할정복하는 문제이다. func(int i, int j, int size) 함수를 이용하여 size==1이 될때까지 계속 호출하는 형태로 재귀를 반복하게 된다. 기저조건은 size가 1이 될때 cnt++를 해주고 return을 한다. 재귀는 Z모양으로 4번을 호출하게 된다. 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 package chap06; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public..

재귀를 사용하는 대표적인 문제이다. N개의 원판을 옮기려면 크게 3가지 부분으로 생각하여 접근할 수 있다. 첫번째로 N-1개의 원판을 목적지가 아닌 중간 지점 고리로 옮겨놓고, 두번째로는 가장 밑바닥에 위치한 원판을 목적지로 옮긴다. 마지막으로 중간지점에 위치해있던 N-1개의 원판을 목적지 고리로 옮기는 과정을 반복하다보면 전체 N개의 원판을 목적지로 옮기는 것이 가능하다. 재귀함수의 기저조건으로는 옮길 원판이 없는 경우를 사용하였다. 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 package chap06; import java.io.BufferedReader; import java.io.Inp..

재귀를 이용하는 기초적인 문제이다. 주어진 숫자의 범위가 2,147,483,647이므로 일반적인 방법으로 접근하면 시간초과가 발생할수밖에 없다. 따라서 재귀를 사용해야하는데 위와 같은 성질을 이용하여 재귀를 사용해준다. 즉, 지수를 계속 제곱해준다는 개념으로 접근하여 B의 값까지 도달하는 것을 구하는 방법으로 해결하면 되는 문제이다. 기저조건으로는 B의 값이 0이 될때를 사용하였다. 또한 보통 분할정복을 사용하는 알고리즘은 3가지의 구성요소를 가지고있다. 1. 문제를 더 작은 문제로 분할하는 과정 (divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case) 1 2 3 4 5 ..

두번의 BFS를 이용하였다. 첫번째 BFS로 각 섬마다 번호를 지정해주었고, isEdge라른 함수를 이용하여 현재 위치가 가장 자리인 것이 확인이 되면 두번째 BFS를 사용하여 다른 섬까지의 거리를 구해주는 방식으로 해결하였다. 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 86 87 88 89 90 91 92 93 ..

BFS를 사용하는 문제이다. 다른 숨바꼭질 시리즈와 다르게 몇가지 경로로 목적지에 도달할 수 있냐를 체크해야 함으로 visit 체크를 queue에 offer할 때가 아니라 queue에 poll 할때 체크해주었다. 또한, 처음 도달한 경우가 최솟값이므로 그 값을 이용하는 과정을 거쳤다. 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 package..

BFS를 사용하여 최단 시간을 찾는 문제이다. 단, 일반적인 BFS와는 다르게 움직일때 두가지(일반, 말) 방법으로 움직이게 되고, 말처럼 움직이는 경우는 횟수가 제한이된다. 따라서 visit 배열을 3차원으로 visit[행][열][말처럼 움직일수 있는 남은 횟수] 로 만들어서, 구한다. 그리고 queue에서 poll 할때 도착지점인 경우 result와의 최솟값을 비교해주어서 답을 구한다. 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 6..

BFS를 사용하여 최단 시간을 찾는 문제이다. 이 문제는 일반 BFS와 다르게 풀어야 한다. 일반적인 BFS를 하기 위해선 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하다. 그러나 이문제는 가중치가 0이 존재하므로 단순한 BFS를 사용할 수 없고, 다음과 같은 방법으로 풀수 있다. - 다익스트라 알고리즘 : 모든 간선이 다를 경우 사용하기 용이 - 0-1 BFS : 가중치가 0인 간선에 연결된 정점은 큐의 맨뒤가 아닌 맨앞에 넣는 방법 - *2 를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법 이 문제에선 간선이 0, 1 두가지 종류여서 다익스트라 알고리즘 보단 Deque을 이용하여 가중치가 0일 때, Deque의 addFirst..

최단거리를 구하는 문제이기에 BFS를 사용하는 문제이다. 이 문제에선 신경써야할 점이 두가지 있다. 첫째, visit[][][]을 이용하여 벽을 뚫지 않은 상태에서랑 벽을 이미 한번 뚫은 상태에서 방문이 가능한지 신경써줘야한다. 둘째, queue에서 poll 할때 목적지 지점이면 최솟값으로 갱신 가능한지 확인하는 것 이다. 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 ..

BFS를 사용하는 문제이다. 모든 시작점 1을 queue에 집어넣은 다음 평소 boolean배열 형태로 사용하던 visit를 int배열 형태로 바꾸어 토마토가 익은 날짜로 대신하여 사용하였다. 그리고 이미 visit배열이 갱신되었더라도 더 작은 날짜를 가질 수 있다면 갱신할수 있도록 while문 안쪽에서 구현하였다. 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 7..