Sweep 썸네일형 리스트형 [Greedy] BJ_21762, 공통부분수열확장, 정올 이 문제는 처음 접했을 때, 어떤 알고리즘으로 문제에 접근해야 하는지 생각하기 난해한 문제다. 제목에서 알 수 있듯이 Greedy 문제로, Greedy 문제는 접근법을 떠올리지 못하면 풀이에 쉽게 다가가지 못한다. 이해를 쉽게 하기 위해 아래 예시를 들어 보자. X, Y를 독립적으로 생각하고, 아래와 같이 주어졌다고 한다면 공통 부분 수열인 w를 중심으로 w의 원소인 w[i]의 사이사이에 어떠한 인자들이 들어갈 수 있는지 계산해 보는 것이 필요하다. 즉 w = da인 아래의 케이스 에는 d의 앞에, d와 a의 사이, a의 뒤에 어떤 알파벳이 들어올 수 있는지를 계산하고 X, Y에 각각 동일한 원소가 있다면 확장 가능한 공통부분 수열이라는 것을 확인할 수 있다. w는 이미 공통 부분 수열이기 때문에 위와 .. 더보기 이전 1 다음