거창한 시작

알고리즘 종류 - MST 사고 과정 - 일반적인 MST으로 해결하면 될 것 같았다. 1. 입력된 간선의 비용을 오름차순으로 정렬한다. 2. 사이클인지 확인하고 아니면 간선을 선택하여 연결 비용에 추가한다. 3. 2번에서 MST를 구하면, 총 비용에서 연결에서 구한 최소 비용을 뺀다. 구현(C++) 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 ..

알고리즘 종류 - MST 사고 과정 - 첫 번째 시도(메모리 초과) 1. 조합을 이용해서 두 정점들 사이의 비용 구하기 (완전 그래프) 2. 비용을 기준으로 오름차순 정렬 3. Union-Find으로 MST 구하기 - 무엇이 문제인가? * 완전 그래프를 사용하면 메모리 초과가 발생한다. n은 최대 10^5이다. 완전 그래프로 만들면, (n-1)(n-2)/2이므로 10^9가 넘는다. 10^6이 1mb인 것을 감안하면, 1000mb가 넘는다. * 완전 그래프를 사용하지 않고 MST를 만들어야 한다. 여기 정점들은 x축, y축, z축으로 따로 표현될 수 있다. 즉, x축, y축, z축에서 각각 거리를 구해서 최소 거리로 정렬하여 MST를 만들면 될 것이다. 그러면, 공간 복잡도는 3n이 될 것이다. - 두 번..

알고리즘 종류 - 구현 - BFS 사고 과정 1. (0,0)에서 시작해서 BFS로 치즈인 부분을 찾으면, map 자료형에 좌료를 넣고 개수를 센다. 2. map에 넣은 것 중에 value가 2이상(공기 중에 노출된 면이 2개 이상)이면 좌표의 치즈를 없앤다. 3. 치즈의 총 개수가 0일 될 때까지 1번과 2번을 반복한다. 구현(C++) 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..

알고리즘 종류 - 구현 - BFS 사고 과정 1. 궁수의 배치를 조합으로 구한다. 2. 궁수가 공격할 적군의 위치를 구하고(중복 가능) 제거한다. 그리고 적군을 이동시킨다. 3. 2번을 한 세트로 해서 계속 돌리다가 적군이 0이 되면 반복을 멈춘다. 4. 궁수가 죽인 적군의 수를 갱신한다. 5. 1번에서 구한 다른 궁수의 배치로 2번부터 시작한다. 구현(C++) 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..

알고리즘 종류 - 플로이드 와샬 사고 과정 - 정점들 간에 비교를 나타내는 문제이다. A가 B보다 무겁고, B가 C보다 무거우면 A가 C보다 무거운 관계를 나타낼 수 있어야 한다. 관계의 표현이 '무겁다', '강하다', '빠르다' 등으로 표현 가능한 것을 다른 문제들에서 봤다. 각 정점들이 모든 다른 정점들과 비교를 할 수 있는 알고리즘이 필요하다. - 플로이드 와샬을 사용할 수 있을 것 같다. 플로이드 와샬은 선택한 정점을 거쳐서 목적지로 가는 알고리즘이다. 거쳐 가면서 무거운지 비교하면 쉽게 풀 수 있을 것 같다. 구현(C++) 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 3..

알고리즘 종류 - 다익스트라 사고 과정 - 출발지점에서 목표지점까지의 모든 경로들 중에서 벽의 개수가 가장 적은 경로를 선택하면 될 것 같았다. - 출발지점이 하나이므로 다익스트라를 사용해보자. - 경로에 있는 벽의 개수는 어떻게 기록할까? 다익스트라는 최소비용을 기록했는데, 여기서는 벽의 개수를 비용이라고 생각하면 최소 벽의 개수를 dist라는 배열에 기록하면 될 것 같다. 구현(C++) 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..

알고리즘 종류 - 문자열 - 트라이(Trie) 사고 과정 - 보아하니 트리를 구현하여 문자열을 저장하면 될 것 같았다. 이진트리만 만들어 봤지 어떻게 만들지 고민했다. 트리 종류를 찾아보니 트라이(Trie)라는 것이 문자열을 저장하는데 효과적인 자료구조라는 것을 알게 되었다. 트라이를 이용해서 해결하는 문제였다. - 트라이를 공부할 필요성이 생겼다. 여기에 적어보았다. - 입력된 문자열을 vector에 담아 주고, vector를 이용해서 트리를 만들어 준다. - 완성된 트리에서 DFS를 실행하여 출력하면 알파벳 순으로 출력됩니다. map는 key를 기준으로 오름차순 정렬을 자동으로 합니다. 따라서, key는 string이므로 알파벳 순으로 자동 정렬됩니다. 구현(C++) 1 2 3 4 5 6 7 8 9 ..

알고리즘 종류 - 문자열 사고 과정 - LCS이 뭐지? Longest Common Subsequence에서 subsequence의 뜻은 연속되지 않은 문자열이다. 즉, 문자열이 연속되지 않아도 공통되는 것 중에 가장 긴 것을 찾으면 된다. 아래에 subsequence와 substring을 비교한 예시가 있다. - 문자열 내의 모든 문자를 방문하면서 비교해야 한다. 비교하는 과정에 같은 문자를 찾았다면 어떻게 저장하고 숫자를 기록할까? 이 부분에 대해서 정형화된 방법이 있을 것 같아서 찾아보니 LCS 알고리즘이 있었다. (이 문제 자체가 LCS 알고리즘을 묻는 문제였다) 방법은 DP를 이용해서 저장하고 최대 공통 문자열의 길이를 기록한다. 본인은 이 블로그에서 시각적인 정보를 참고하여 이해할 수 있었다. ..

알고리즘 종류 - 구현 - BFS, DFS 사고 과정 1. 치즈의 개수 구하기 2. 가장자리를 표시하기 3. 가장자리를 제거하기 4. 1~3 반복 구현(C++) 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 94 95 96 97 98 99 100 101 102 103 104 ..

알고리즘 종류 - 위상 정렬 사고 과정 - 순서가 있는 정렬이기 때문에 위상 정렬을 떠올렸다. - 이전 건물들 A, B의 다음 건물이 C일 때, C의 최종 시간은 아래와 같다. max(A가 지어지기 까지의 누적 시간 + C가 지어는 시간, B가 지어지기 까지의 누적 시간 + C가 지어지는 시간) - 개별 건물이 지어지는 시간을 저장하는 배열 1개가 필요하다. - 누적 시간을 기록하는 배열 1개가 필요하다. 구현(C++) 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..