프로그래민👨‍💻

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 ..

시뮬레이션 문제이다. 주사위는 10번을 굴리고, 말은 4개를 가지고 있으므로 전체 경우의 수는 4^10을 가지게 된다. 따라서 이 문제는 백트래킹을 통한 완전탐색을 할 수 있는 문제이다. 다만 주의할점은 윷놀이판을 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 31 32 33 34 35 36 37 38 39..

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

백트래킹을 이용하여 경로를 찾는 문제이다. 백트래킹 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..

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

이문제는 순열을 사용하여 접근하는 문제이다. 처음엔 간단히 단순 순열로 접근하여 푸는 문제 인지 알았다. 하지만 최악의 경우 21P10을 가지게 되므로 가지치가 상당히 중요한 문제로 생각하였다. 일단 문제를 쉽게 접근하기 위해 -,+,0으로 주어진 문자열을 2차원 배열의 형태로 만들어주었다. 행을 0부터 N까지로 잡고, 열을 현재행부터 N까지로 주어서 삼각형모양의 2차원배열을 만들었다. 그 후 순열로 접근하였다. 일단 순열을 0부터 N-1까지 정해줄때 해당 index는 2차원배열의 행과열이 같을때의 index의 부호와 같기때문에 크게 경우의 수를 줄일 수 있었고, 그 후 check라는 함수를 만들어 2차원배열의 해당 열의 원소들을 체크해주는 식으로 가지치기를 하였다. 푸는데 상당히 오랜시간이 걸렸고, c..

이문제는 복잡한 구현 문제이다. 문제에 주어진 대로 구현을 하면 되는데, 구현을 함에 있어 재귀와 다양한 함수를 활용하였다. 재귀와 백트래킹을 같이 사용하였는데 2차원 배열의 백트래킹을 할땐 재귀함수 안에서 지역변수로 temp[][] 를 선언하고 원래 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53..

구현하는데 있어 상당히 복잡하게 구현을 이룬 문제였다. 이문제는 최소성과 유일성을 만족시키는 후보키를 구하는 문제이다. 맨처음 컬럼의 수를 확인했는데 최대 8이기 때문에 조합으로 풀생각을 하였다. 전체 N개에서 1개부터 N개까지 선택하는 모든 경우를 다따져보았다. 그리고 그 상황에서 hashSet을 이용하여 유일성을 확인하였고, 또다른 hashSet을 이용하여 최소성을 만족하는지 확인하였다. hashSet이 상당히 여러개가 쓰였기에 구현하는데 있어서 많이 복잡하였다. 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..

해밀턴 순환회로, A정점에서 시작하여 모든 정점을 최소비용으로 돌아 A정점으로 돌아오는 문제이다. 다른 말로는 TSP, 외판원 순환 문제라고 한다. 이 문제는 다양한 풀이 방법으로 접근 할 수 있지만 N의 값이 12 이하로 주어졌으므로 백트래킹을 이용한 완탐을 사용해보았다. 단, 순열의 완탐을 돌때 첫번째 점(0)을 제외한 N-1개의 순열을 구하고 이때 마지막에 해당하는 점에서 첫번째점(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 31 32 33 34 3..

이 문제는 여지껏 배운 다양한 알고리즘을 거의다 사용해야 풀 수 있다. 다음과 같은 로직으로 구현하였다. 1. BFS 또는 DFS 를 이용하여 섬을 찾고, 1부터 차례대로 섬에 대해 인덱싱을 해주기 2. 섬의수C2 인 조합을 이용하여 두개의 섬을 고르고, 가장 자리에 대해서 DFS를 이용하여 직선경로 찾기 3. 찾은 직선 경로에 대해 그래프의 형태를 만들기 4. 만든 그래프에 대해 모든 정점을 포함하며 정점보다 하나 적은 간선을 선택하게 되는 MST를 만들기 4-1. UnionFind를 이용한 간선 기준 Kruskal알고리즘 사용 4-2. PriorityQueue를 이용한 정점 기준 Prim 알고리즘 사용 다양한 알고리즘을 한번에 적용 시켜야 했던 문제이고, 여러가지를 다시 복습할 수 있어던 기회여서 좋..