거창한 시작

알고리즘 종류 - 구현 - 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..

알고리즘 종류 - MST 사고 과정 - (잠깐의 읽기입니다)몇 달만에 풀어보는 문제였습니다. 두 그룹으로 나누기 위한 경우의 수를 순열조합으로 계산했습니다. 그런데 1억개가 넘어서 다른 방법을 찾아야 할 것 같았습니다. 하지만, 일단 해보기로 했습니다. 너무 오랜만이라서 vector를 사용하는 방법도 잊었습니다. 그렇게 잘 때가 다 되었습니다. 그래서 해설을 보기로 했습니다. - 목표는 마을을 두 개로 나누고 집을 잇는 경로의 최소 비용을 구하는 것입니다. 가장 먼저 떠오르는 방법은 아마도 다음과 같을 것 입니다. 1. 마을을 2개로 나눈다. 2. 마을에서 MST 알고리즘을 한다. 그런데, 이렇게 생각해 보면 어떨까요? 모든 집을 연결하는 최소 스패닝 트리를 먼저 구합니다. 이후, A집과 B집을 잇는 경..

병원에서 소견서를 받았으니 빨리 다른 나라로 이동하기로 했다. Macedonia로 가는 버스는 오후 늦게 있어서 잠시 시내를 둘러보기로 했다. Nis에서 가볼만한 곳이라고 검색하면 skull tower가 나온다. 진짜 사람의 해골로 만들어진 탑이다. 1804~1813년에 세르비아의 니스는 오스만 제국으로부터 독립하기 위해서 반란을 일으켰다. 이때 오스만 제국의 지휘관 Hurshid Pasha는 반란군을 모두 제압하고 그들의 목을 잘랐다. 그리고 가죽을 벗겨서 해골 탑을 쌓았다고 한다. 이 타워의 목적은 반란을 일으키지 못하게 하기 위한 경고의 상징물이다. 952개의 해골이 있었지만 지금은 30개가 있다고 한다. 나도 이곳을 가볼까라고 생각했다. Nis에서 정말 볼 것이 없었기 때문이다. 버스를 타고 이동..

오늘 이동할 도시는 Nis입니다. Serbia에서 3번째로 큰 도시입니다. 이곳으로 온 이유는 그리스 쪽으로 이동하기 위해서 입니다. 호스텔을 나와서 버스 터미널로 이동했습니다. Nis에 도착해서 호스텔까지 약 30분을 걸었습니다. 여느 때와 마찬가지로 호스텔 숨바꼭질을 하고 있었습니다. 간판 같은 것이 없어서 booking.com에 나와있는 이미지로 찾아야 했습니다. 가는 길에 개들이 많았습니다. 지나갈 때마다 흠칫했지만 개들은 조용히 지나갔습니다. 어느 골목을 들어가고 있었습니다. 앞에서 부녀와 반려견 1마리가 오고 있었습니다. 저는 그들에게 호스텔의 위치를 물어 보기로 했습니다. 아버지에게 위치를 물어보고 있는데 시츄로 보이는 작은 반려견이 자꾸 옆에서 짖었습니다. 저는 개의치 않았지만 잠시 후에 ..