백준 9248번 문제 [문제 설명] [문제 풀이] LCP를 구하기 전에 Suffix Array를 구해야 한다. Suffix Array를 구하는 방법은 멘버- 마이어스의 알고리즘을 이용해야 한다. 문제에서 주어진 조건이 문자열의 최대 길이가 50만까지 증가할 수 있고 또한 문자열을 처리하는 함수들은 그 동작 속도가 느린 편이기 때문이다. 멘버-마이어스의 알고리즘은 기수 정렬을 이용한다. banana에 대해서 적용 과정을 보면 b a n a n a \0 index 0 1 2 3 4 5 SA 98 97 110 97 110 97 -1 처음 입력을 받고 SA를 정하면 다음과 같다. (SA의 값들은 ASCII 코드 값을 적은 것임) 이 표의 SA를 가지고 정렬을 수행한다. 같은 값을 가지는 SA들이 문제가 되는데(예를 들면 1,3,5 .. 백준 14444번 문제 [문제 설명] 알파벳 소문자로만 이루어진 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 구하는 프로그램을 작성하시오. [처음 문제를 다뤘던 방법] 문제를 처음 봤을 때는 단순히 문자열의 길이만큼 for 문을 돌리면서 부분문자열과 하나씩 비교하면 해결되겠지 하는 생각이였지만... 문자열에 직접적인 처리를 하는 함수들은 생각보다 속도가 많이 느리다. [문제 풀이 관련 알고리즘 - Manacher's Algorithm] 가장 긴 팰린드롬을 찾는 강력한 알고리즘으로 알려져 있다고 한다. 알고리즘을 다른 블로그나 위키를 보고 이해하는 데 조금 오래 걸렸다. 수학적 표현으로만 되어 있을 뿐 그에 대한 설명은 부실(?!)하다는 느낌이 많이 들었기 때문이다. Manac.. 백준 11724번 연결요소 문제 [문제] 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. [연결요소 (Connected Component)의 의미] [문제 해결 방식] 연결요소를 세는 문제는 처음에는 이해하기 어려웠으나, 인터넷에서 여러 가지 예제를 참고하다 보니 연결요소의 개수는 결국 DFS나 BFS를 호출하는 횟수를 의미한다는 것으로 귀결된다는 것을 알게되었다. [코드] https://github.com/papayetoo/baekjooon_swift/blob/master/baekjoon_swift/11724.swift 백준 14502번 연구소 문제 [문제 설명] 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. [문제 해결 방식] 14502번 문제는 벽을 세우는 문제와 벽을 세운 뒤 바이러스가 퍼지는 문제로 나눠진다. 벽을 세우는 문제는 완전 탐색을 통해 구현할 수 있다고 생각해서 .. 이전 1 다음
