Gi-Log

문제: SW Expert Academy 1251 하나로 "섬이나 도시, 컴퓨터 등등 어떤 정점들을 모두 잇는 최소 경로가 필요하다!"라는 문제가 나오면 십중팔구 최소 신장 트리(MST) 문제이다. 이 문제 또한 크루스칼 알고리즘을 적용하여 MST를 생성해서 풀 수 있는 문제였다. 본 블로그에서 몇 번 설명을 진행한 풀이가 있는데, 크루스칼 알고리즘을 간단히 설명하면 다음과 같다. 1. 어떤 노드들을 잇는 간선들을, 그 비용을 기준으로 오름차순 정렬한다. 2. 가장 비용이 적은 간선부터 연결을 시작한다. 3. 이 때, 간선을 연결했을 때 싸이클이 발생하게 된다면 해당 간선은 연결하지 않고 건너 뛴다. 위 알고리즘 구현을 위해서는 간선 정보를 어떤 컨테이너에 잘 담고, 정렬할 수 있어야한다. 그리고 싸이클 ..

문제: SW Expert Academy 1256 K번째 접미어 SWEA 1257 K번째 문자열(https://jinho9610.tistory.com/14)과 굉장히 유사하거나 거의 동일한 문제이다. 이번에는 부분 문자열이 아니라 접미어를 모두 구해서 저장하면 되기 때문에, 중복이 발생할 일이 없어서 단순히 벡터를 사용하고 정렬해주면 되는 문제이다. 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 /* SWEQ 1256 k번째 접미어 */ #define _CRT_SECURE_NO_WARNINGS #include #incl..

문제: SW Expert Academy 1257 K번째 문자열 swea에서 문자열 매칭 강의를 듣고 이 문제를 풀게 되는 사람들이 많을텐데, 강의에서 접미어 배열, 트라이, kmp 등등의 고급(?) 알고리즘이 등장한 것에 비해서 꽤나 쉽게 풀리는 문제이다. 굉장히 단순하게 주어진 문자열을 자를 두 위치를 i와 j로 지정하고, 파생되는 있는 모든 경우의 부분 문자열을 생성한다. 그리고 이 부분 문자열들을 저장할 컨테이너가 필요한데, 예시로 주어진 것처럼 food의 경우 o라는 부분 문자열이 중복(2번) 발생할 수 있다. 여기서 중복을 제거하기 위해서 set을 써야함을 눈치챌 수 있었다면 굉장히 쉽게 풀 수 있다. 특히나 해당 문제는 "k번째" 부분 문자열 출력을 위해서 정렬이 필요한데, set을 쓸 경우 ..

문제: SW Expert Academy 1248번 공통조상 (효율적인 풀이인지 검증이 필요한 풀이입니다) 주어진 트리 정보를 바탕으로, 두 정점의 공통 조상을 파악하고, 그 조상의 자식 노드 수 + 1(=서브 트리 크기)를 구하는 문제이다. 개인적으로 트리 문제가 나오면 긴장하는 편인데, 주어진 정보를 바탕으로 트리를 구현해야하나...라는 고민을 처음에 했고, 배열을 이용해서 트리를 구현하려고 했다. 하지만 공통조상을 찾기 위해서는 트리를 거슬러 올라가야할 필요가 있었기에 단순히 각 노드의 부모가 누구인지 parent라는 배열에 저장하고, 각 노드의 자식 노드는 누구(들)인지 child라는 2차원 배열에 저장하기로 하였다. 이 때 2차원 배열인 이유는, 주어진 트리가 이진 트리이기 때문인데, 그냥 vec..