프로그래민👨‍💻

처음에 보고 아이디어를 떠올리기 상당히 어려웠던 문제이다. 이 문제에서 전체 경우의 수를 따져본다면 전체 6팀이 경기를 하기때문에 총 15경기가 열리고, 경기마다 승,무,패 의 경우가 있기에 전체 3^15가지의 경우가 생기게 된다. 그러므로 백트래킹을 사용하여 승무패를 계속 재귀적으로 호출하면서 전체경우의 수랑 현재 테이블이랑 같아지는지 확인하여 구할수 있다. 백트래킹 문제라 전혀 생각지 못한 문제였다. 문제를 깊이 생각할 필요가 있다고 느꼈다. 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..

이차원 행렬상에서 특정조건의 최장길이를 구하는 문제이다. 최장길이를 구하는 문제는 DFS와 백트래킹으로 풀면 쉽게 풀 수 있다. 맨처음 이문제를 접근하였을 때 BFS와 3차원 visit배열로 접근하였다. 이 방법으로도 풀리긴 하지만 DFS와 2차원 visit 배열의 백트래킹을 사용하면 훨씬 간결한 코드를 얻을 수 있다. 이 문제에선 주의할점이 두가지 있는데, 첫째 산을 깎을수 있다는 점과 둘째 깎을때 꼭 K만큼이 아니라 K이하 만큼 깎을수 있다는 점이다. 두가지를 유념하여 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 3..

상당히 많은 시간을 투자했던 문제이다. 우선 간단하게 N의크기가 10이하인것을 보고 백트래킹으로 접근하려했다. 하지만 최악의 경우가 10!정도가 나오는데 이것 말고도 안쪽에서의 String 연산때문에 시간초과를 해결할 수 없었다. 그래서 StringBuilder를 사용하여 결국 문제는 해결하였지만 최악의 시간복잡도를 가지고 해결하게 된 셈이 되었다. 아래가 다음 코드이다. 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..

단순구현과 백트래킹이 합쳐진 문제이다. 이문제는 2048을 구하는 단순구현과 4가지 방향으로 5번을 가봐야하는 과정이합쳐진 문제였다. 2차원 배열을 이용하여 재귀를 도는 백트래킹은 처음 구현해봐서 어떻게 해야하는지 고민을 많이했다. dfs()란 함수에서 이차원 배열을 저장할 temp[][] 를 이용하여 해결하였다. 즉 재귀함수호출전 temp에 map을 다 저장하고 재귀함수 호출뒤 map에 temp를 다시 복원시키는 방법을 사용하였다. 간단한 방법이지만 생각하는 부분에 있어서 많은 시간을 사용하였다. 구현뿐만 아니라 전반적으로 다시 봐야할 필요가 있는 문제인 것 같다. 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..

처음 문제를 접했을 때 설계에 상당히 많은 시간을 사용하였다. 단순 문자열 파싱 문제인지 알았는데, 자세히 보니 전혀 다른 문제였다. 출력의 경우의 수를 자세히 보다 보니 특정한 규칙을 찾게 되었다. 이차원 배열이 있고, 가로축을 user_id, 세로축을 banned_id라고 하고 패턴이 매칭되면 1을 둔다고 가정한다면, 맨처음 입력 예시에선 다음과 같이 적용이 된다. "frodo" "fradi" "crodo" "abc123" "frodoc" "fro*d*" 1 1 0 0 0 "abc1**" 0 0 0 1 0 이에 따른 출력은 2가지 경우로 frodo, abc123 과 fradi, abc123 가 나오게 된다. 여기서 찾은 규칙은 패턴이 매칭되는 1에 한해서 각행마다 하나의 열을 선택하게 되고, 다음행에..

인접리스트를 활용한 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을 해..

TSP문제 이다. N의 범위가 10이하이므로 순열을 사용하여 풀었다. perm라는 순열을 구하는 함수를 작성하였다. 여기서 arr라는 배열을 준비하여 각 인덱스 마다 도시의 번호로 지정하고, result라는 배열을 이용하여 도시들을 방문하는 경우의 수를 구하였다. result 배열이 전부 준비되었을 때 서로 도시끼리 갈 수 있는지 여부를 체크하면서 최종적으로 돌아오는 경우까지 계산하여 최종 답을 구하였다. 이 문제는 생각을 달리한다면 시간복잡도를 줄일 수 있는데, 그 경우는 시작 지점을 고정시키는 개념이다. 즉 0 1 2 3 4 0 과 1 2 3 4 0 1 은 동일한 연산이므로 첫번째 시작지점을 고정시켜서 동일한 계산을 반복안하게 하는 방법으로 시간복잡도를 줄일 수 있다. 1 2 3 4 5 6 7 8 9..

여러가지 기법이 혼합되어 있는 문제이다. 우선 전체 25개의 알파벳중 7개를 뽑는 경우의 수를 생각하였다. 백트래킹을 이용한 조합을 사용할 계획으로 7개의 알파벳을 고르는 것을 구현한 후 1차적으로 S가 4개 이상인지를 확인하였다. 그 다음 S가 4개이상임이 확인이 된다면 BFS를 이용하여 7개의 알파벳이 하나의 그룹으로 이루어져있는지 확인하였다. 만일 하나의 그룹이면 최종답을 하나추가 시켰다. 수의 범위가 구현이 가능한 범위임으로 문제에 주어진 대로 구현하는게 중요한 문제였다. 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 4..

기본적인 부분수열의 합문제이다. 두가지 방법으로 풀어보았다. 첫번째로는 비트마스킹을 이용하여 모든 부분수열을 구하는 방식으로 구현하였다. 두번째로는 재귀적인 DFS 방식으로 현재항을 더해주는 경우, 현재항을 더해주지 않는 경우로 나누어 2번씩 호출해주는 방식으로 풀었다. 이때 기저조건으로는 마지막인덱스에 도달하였을 경우 종료시키게 해주었다. 시간은 비트마스킹을 사용하는 첫번째 코드보다 두번째 재귀적인 DFS를 사용한 코드가 빨랐다. 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 ch..

백트래킹의 전형적인 문제인 N-Queen 문제이다. 체스판에 서로 공격할 수 없도록 N개의 Queen을 배치하는 문제인데, Queen의 움직임 특성상 한 행에 한 개의 Queen 만을 가질수 있게 됨으로 한행을 depth로 보고 dfs를 실행하였다. 보통의 백트래킹은 visit함수로만 방문 여부를 결정하였는데 이 문제에선 대각선이랑 같은 열에 Queen이 존재해야하는지 봐야함으로 check함수를 이용하여 방문 가능여부를 한번더 확인해주는 과정을 거쳐 문제를 해결하였다. 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 4..