![]()
문제 2186번: 문자판 (acmicpc.net) 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 풀이 문자판을 십자 방향으로 DFS 탐색하며 DFS 탐색의 깊이가 영단어의 길이와 일치할 때 주어진 영단어와 일치하는지 확인하는 작업이 필요합니다. 하지만 DFS 탐색만으로 해결하려 한다면 불필요한 경우도 중복 탐색하게 되어 연산 시간이 오래 걸리게 됩니다. 중복은 다이나믹 프로그래밍으로 줄일 수 있습니다. DFS 탐색을 한다면 메모이제이션으로 불필요한 재귀 호출을 줄일 수 ..
문제 3584번: 가장 가까운 공통 조상 (acmicpc.net) 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 두 노드의 공통 조상을 찾는다면 부모 노드로 하나씩 거슬러 올라가며 부모가 같은 노드인지 확인하는 방법이 가장 간단합니다. 우선 부모가 같기 위해서는 루트로부터의 깊이가 같아야 합니다. 그렇기 때문에 주어진 두 노드의 깊이가 다르다면 깊이를 맞춰주는것이 우선입니다. 두 노드의 깊이가 같다면 동시에 하나씩 부모로 거슬러 올라가며 비교를 합니다..
