화분

어제 하루 동안은 거의 알고리즘 문제 하나 푸는데 시간을 거의 다 쏟아부은거 같다. 다른 공부나 해야 할 일들도 조금 한거 같지만. 1. 1931번: 회의실 배정 (acmicpc.net) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 위 문제는 활동 선택 문제( activity selection problem )에 관한 것이다. 일정 시간동안 최대한 많은 활동을 선택하는 문제인데, 이 문제를 풀려면 그리디 접근법으로 풀어야 한다. 종료 시간이 빠를수록 최대한 많은 활동을 선택할 수 있다는 글로벌한 원칙이 적용된다. 그래서 우선 종료시간이 빠른 순으로 정렬을 하고, 종료 시간이 같다면 시작시간이 빠른 활동을 우선적으로 접근할..

이번 문제는 최장 공통 부분수열(LCS:Longest Common Subsequence)이다. 어떻게 동적계획법을 이용해 풀지 고민하다가 테이블에 어떻게 기록할진 떠올렸으나 코드로 구현할 방법은 떠오르지 않아 결국 인터넷을 참고하였다. 이 문제에 어떻게 접근했냐하면 우선 큰 문제를 해결하기 위한 공통된 작은 문제를 찾아내려 했다. 앞에서부터 공통된 문자를 찾기보단 뒤에서부터 찾으려 했다. 그 결과 다음과 같은 테이블을 완성했다. A C A Y K P C 3 A 4 2 P 1 C 3 A 2 2 K 1 가장 우측 하단 위치에서부터 왼쪽 행과 윗쪽 열의 안쪽에 있는 수를 증가시켜 나간다. 이렇게 접근하면 LCS를 만족하는 문자의 개수를 알아내는 실마리를 찾은거 같았다. 하지만 문제가 있었다. 어떻게 저 가장 ..