deque 썸네일형 리스트형 [Greedy] BJ_21762, 공통부분수열확장, 정올 이 문제는 처음 접했을 때, 어떤 알고리즘으로 문제에 접근해야 하는지 생각하기 난해한 문제다. 제목에서 알 수 있듯이 Greedy 문제로, Greedy 문제는 접근법을 떠올리지 못하면 풀이에 쉽게 다가가지 못한다. 이해를 쉽게 하기 위해 아래 예시를 들어 보자. X, Y를 독립적으로 생각하고, 아래와 같이 주어졌다고 한다면 공통 부분 수열인 w를 중심으로 w의 원소인 w[i]의 사이사이에 어떠한 인자들이 들어갈 수 있는지 계산해 보는 것이 필요하다. 즉 w = da인 아래의 케이스 에는 d의 앞에, d와 a의 사이, a의 뒤에 어떤 알파벳이 들어올 수 있는지를 계산하고 X, Y에 각각 동일한 원소가 있다면 확장 가능한 공통부분 수열이라는 것을 확인할 수 있다. w는 이미 공통 부분 수열이기 때문에 위와 .. 더보기 [BFS]BJ_2146, 다리 만들기 0 또는 1로 이루어진 100 x 100 배열에 대해서 0을 1로 채워가면서 연결되는 최소길이를 구하는 문제이다. 어떻게 접근해야 할까? 일단 격자 형태로 좌/우/상/하를 탐색하는 문제의 경우에는 BFS부터 검토해 보는 것이 좋다. 보통의 BFS 문제가 격자를 바탕으로 이루어지기 때문이다. 이 문제도 확장 형태를 보면 BFS로 풀리는 문제라는 것은 어렵지 않게 유추할 수 있다. 다만, 어려운 점은 시작위치와 도착 위치를 어떻게 잡느냐이다. 시작 위치를 어디로 잡아야 할까? 문제에서 시작 위치와 도착 위치가 정해지는 경우는 시작위치를 queue에 넣고 탐색을 진행하되 도착 위치에서 탐색을 종료하면 된다. 그런데 이 문제는 시작 위치와 도착 위치가 불분명하다. 어떻게 시작해야 할까? 문제에서 제시되어 있는 .. 더보기 이전 1 다음
