개요
11주차 스터디는 주제는 특별히 없고, 재밌게 풀 수 있을 것 같은 문제를 골랐다.
A번
문제 요약
- P1: IOI
- P2: IOIOI
- P3: IOIOIOI
위와 같은 형태의 문자열을 PN이라고 하자.
문자열과 N이 주어졌을 때, 문자열 안에 PN이 몇 군데 있는지 구하는 문제다.
설명
이 문제의 핵심 아이디어는 N<=M인 PM을 찾는다면 그 PM 안에는 M-N+1개의 PN이 있다는 것이다.
즉 IOIOIOI라면 IOI가 3개 있는 것이다.
그래서 지속적으로 현재 몇개의 연속 IOI를 마주쳤는지를 세 주면서, 끊길 때 세 주면 된다.
B번
문제 요약
전화번호의 목록이 주어졌을 때, 이 목록이 일관성이 있는지 구하는 문제이다.
일관성은 한 번호가 다른 번호의 접두어인 경우가 없어야 하는 것이다.
설명
이 문제는 트라이 기초 문제로 볼 수도 있는데 정렬로 더 쉽게 풀 수 있다.
문자열 정렬이 어떻게 동작하는지만 잘 알고 있다면 정렬해서 바로 다음 문자열이 현재 문자열의 접두어인지만 확인하면 된다는 것을 이해할 수 있을 것이다.
C번
문제 요약
장애물이 있는 그리드에서, 상하좌우 인접 칸으로 움직이거나 최대 K번 나이트처럼 움직여서 (0,0)에서 (H-1,W-1)로 가는 최소 이동 횟수를 구하는 문제다.
설명
단순히 BFS로 풀 수 있는 문제이다.
나이트처럼 움직일 수 있는 횟수 K번을 Z축으로 잡고, 3차원에서 BFS를 돌린다고 생각하면 된다.
단 Z축은 아래로만 움직일 수 있을 것이다. (횟수는 감소해야 하니까)
D번
문제 요약
이진 트리의 후위 순회와 중위 순회가 주어졌을 때, 전위 순회를 구하는 문제다.
설명
이 문제는 트리의 순회를 잘 알고 있다면 재밌게 풀 수 있는 문제다.
첫 번째로, 인오더는 결국 노드의 순서를 나타내고 있다. 따라서 키가 정렬된 트리가 주어졌을 때 포스트오더를 동해 트리를 만드는 문제로 환원시킬 수 있다. BST라고 생각하자.
두 번째로, 포스트오더의 마지막은 항상 루트다. 그럼 루트를 제거하고 서브트리는 어떻게 나눌 수 있을까?
키가 정렬되어 있기 때문에 키가 더 작으면 왼쪽, 키가 더 크면 오른쪽으로 보낼 수 있고, 또한 두 그룹은 각각 인접할 것이다. 따라서 구간 (s, e)가 주어지면 e가 루트고, 키를 기준으로 나눌 수 있는 점 m을 찾아 (s, m-1)과 (m, e-1)로 나누면 된다.
이제 각 서브트리를 분할 정복한다고 생각하고 재귀로 풀면 끝이다.
후기
재밌었다. 내가 재밌어 보이는걸 골랐으니 당연한가?