프로그래민👨‍💻

C에서 C까지의 최단경로를 찾는 BFS문제이다. 최단경로를 찾을때 다익스트라 알고리즘 또한 사용가능하지만, 이 문제에선 BFS를 사용하여 구현하였다. 이 문제는 자신의 방향과 방향전환횟수를 알고있어야해서 Pos라는 class에 담아둔 상태로 구현하였다. 맨처음엔 일반 visti[][] 배열을 사용하여 방문하지 않았으면 방문하고, 만일 방문했더라도 갱신이 가능하다면 다시 방문하는 방식을 사용하였다. 하지만 어느부분에서 처리가 잘되지않아 다른방법을 사용하였다. 벽을 부수고 이동하기 처럼 visit[][][] 3차원 배열을 사용하였다. 즉 visit[row][col][조건]으로 두고 풀었다. 이 문제에선 조건 부분이 방향을 뜻하는 4가지방법을 의미하여 이와같이 풀어 해결하였다. 1 2 3 4 5 6 7 8 9..

모든 경우를 다해보는 브루트포스 문제이다. 브루트포스는 기본적으로 다음4가지로 구현할 수 있다. 1. for문 2. 순열 3. 재귀 4. 비트마스크 이 문제에서는 만들 수 있는 숫자를 모두 해봐야하 알 수 있는 브루트포스 문제여서 숫자를 만들때 재귀를 이용하여 풀었다. 그리고 모든 숫자의 경우에서 answer를 계속 갱신해주는 방식으로 해주었다. 이 문제는 특히 주의할 점이 상당히 많다. 시작점이 100이라는 것과 또한 2번째 입력이 0 일수도 있다는 것 그리고 재귀를 호출할때 0을 제외하므로 맨마지막에 0을 한번 비교해주는 것과 같은 여러가지 주의할점이 있다. 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..

인접리스트를 활용한 DFS문제이다. 맨처음 문제접근을 BFS로 하였는데, 이 문제에선 5개의 이어진 노드를 찾는 것이여서 DFS를 활용하여 depth가 5가 될때까지를 찾는게 맞는 방향이라 생각해 DFS로 바꾸어 풀었다. 이 문제에서는 주의할 것은 다양한 방법으로 여러갈래로 찾을 수 있기에 visit[i]=false로 다시 바꾸어 주는 작업이 필수적이다. 이것을 해주지 않아 계속 틀렸었다. 예를 들어 위와 같은 그래프가 있고 1번 정점부터 탐색한다고 생각하자. 첫번째 DFS를 실행시킨 결과가 1-2-4-5-3 이라고 생각한다면 depth는 최대 4까지 밖에 찾지를 못한다. 그렇기에 종료조건을 만족하지 못하고, 재귀가 끝나면서 다시 재귀호출을 하게 된다. 1-2 이상황에서 4를 방문했었기네 1-2-3을 해..

그래프를 사용하여 DFS와 BFS를 하는 기본 문제이다. 그래프를 인접리스트로 구현하여 DFS와 BFS각 각 구현하였다. DFS를 구현할 때는 stack을 사용하는 대신 재귀의 형태로 구현하였다. BFS를 구현할 때에는 queue를 사용하여 구현하였다. DFS에서는 방문할때 바로 visit 체크를 해주었고, BFS에서는 queue에 offer하는 동시에 visit 체크를 해주었다. 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 ..

BFS를 활용하는 문제이다. 그러나 일반적인 BFS를 사용한다면 틀린 답을 출력할 것이다. 왜냐하면 클립보드라는 개념을 이문제에선 가지고 있는데 S개의 아이콘을 만드는데 걸리는 시간을 T라고 한다면, 같은 S개를 만들더라도 클립보드의 수에 따라 각 각 다른 T를 가지게 된다. 이 이유는 그래프에서 예를 찾을 수 있는데, 정점 A에서 B를 가고 싶을때, 간선1을 선택해서 가는 경우랑 간선2를 선택해서 가는경우가 있다 가정하자. 같은 B를 도달했더라도 다른 간선을 선택하여 왔기때문에 다른 경우의 수라 생각할 수 있다. 즉, 문제로 다시 돌아와본다면 클립보드의 수에 따라 같은 S개를 만들더라도 다른 T시간을 가질 수 있기 때문에 시간을 저장하는 배열 visit를 2차원의 배열의 형태로 작성하였다. 즉 visi..

재귀를 사용해야만 풀수있는 문제이다. 14888.연산자 끼워넣기 와 비슷한 문제이지만 이문제는 연산자의 갯수가 최대 4N개가 주어질 수 있으므로 순열 또는 조합의 방법을 사용할 수 가 없다. 따라서 재귀를 사용해야하는데, 재귀의 조건은 연산자의 종류인 총 4가지가 될 수가 있다. 즉, 숫자와 숫자사이에서 가지고 있는 연산자의 갯수에 따라 4개중 어떤것을 호출하냐를 결정할 수 있다. 기저조건으로는 마지막 index까지 도달했을 경우로 두었다. 보통 재귀는 '했다', '안했다'를 재귀의 요소로 두지만, 이 경우는 '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 3..

이 문제는 재귀를 사용하는 문제이다. 재귀를 함에 있어 1)선택하고 , 2)선택하지 않고를 기준으로 재귀를 반복하였다. 기저조건으로는 날짜 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 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 package online.base; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public cl..

최단경로를 구하는 문제이다. 이 문제에서 그래프의 가중치가 음을 가지지 않으므로 Dijkstra알고리즘을 사용하여 해결하였다. Dijkstra알고리즘은 Prim알고리즘 기법과 동일하지만 단한가지 차이점을 가진다. 그차이점은 단순 d값의 비교가 아니라 d[dest]와 weight+d[start]를 해주는 것이다. 즉, 단순거리가 아니라 누적거리를 비교해준다. 이렇게 되면 d배열에는 출발점에서 각 index까지의 최단 거리가 저장이 된다. 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..

최소신장트리를 찾는 MST문제이다. 이문제를 해결함에 있어 간선중심의 Kruskal 알고리즘 대신, PriorityQueue를 활용한 Prim 알고리즘을 사용하였다. Edge라는 클래스를 만들어서 weight를 기준으로 빠른 값이 올수있게 최소힙을 사용하는 PriorityQueue를 사용하였다. 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 8..

N의 범위를 확인해본 결과 11이므로 nextPermutation()또는 백트래킹을 이용한 순열을 사용하는 문제이다. 하지만 이문제에서 주의할점은 순열을 구해하는 수,기호 에는 중복이 되는 것이 있으므로 무조건 nextPermutation()을 직접 구현해야 풀 수 있는 문제이다. 연산자들을 모아놓은 op배열을 생성후 모든 number에 대하여 연산을 해주면 쉽게 풀어지는 문제이다. 관건은 nextPermutation()의 직접 구현이다. 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 ..