오랜만에 알고리즘 얘기.
정보 올림피아드 공부를 한 적이 있는 분이라면, 제목에 등장한 용어가 아주 친숙할 것이다. 앞으로 LIS라고 줄여 일컫겠다.

어떤 수열이 왼쪽에서 오른쪽으로 나열돼 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 것이 목표이다.
가령, {3, 2, 1, 4, 5, 2, 3, 5, 3, 6, 4} 같은 수열이 있으면
1, 2, 3, 5, 6이 가장 긴 solution이 된다. {3, 2, 1, 4, 5, 2, 3, 5, 3, 64} OK?
정렬만큼이나 알고리즘 기초를 다지는 데 도움이 되는 흥미로운 문제이다.

이 문제는 간단하게 생각하면 다이나믹 프로그래밍(동적 계획법)을 적용한 O(n^2)의 시간 복잡도로 풀 수 있다. 작은 set에 대한 답을 구한 뒤 그 결과를 저장해 놓고, 그 set의 크기를 차츰 키우면서 작은 solution들을 종합하여 최종 solution을 구하는 방식.

매 원소에 대해서 자기까지 왔을 때 존재 가능한 subsequence의 최대 길이와, 그 subsequence 상에서 자기 앞 원소의 위치를 적어 놓는다. 그러면 다음 원소 차례가 됐을 때는 자기 앞 원소들을 일일이 탐색하여, 자기보다 값이 작으면서 잠재적 subsequence 길이가 최장으로 설정되어 있는 원소에다 자기를 연결해 놓는다. 물론 자기의 subsequence 길이는 1 증가시켜 놓고 말이다.

오프셋 0 1 2 3 4 5 6 7 8 9 10
n 3 2 1 4 5 2 3 5 3 6 4
LIS길이 1 1 1 2 3 2 3 4 3 5 4
이전오프셋 -1 -1 -1 0 3 2 5 6 5 7 6

위와 같은 표가 완성되고 나면, 그 후 개수가 5로 가장 큰 9번 오프셋부터 시작하여 이전 참고 위치를 따라 역추적을 하면 LIS가 구해진다.

그런데 이걸 구하기 위해서 꼭 O(n^2)이나 되는 계산량이 필요할까? 더 효율적인 알고리즘은 없을까?
답은 ‘있다’이다. 물론 메모리 복잡도도 아까처럼 O(n)으로 완전히 동일하고 말이다.
이 새로운 알고리즘은 역시 길이가 n인 버퍼에다가 작업을 하는데, 버퍼의 용도가 아까와는 살짝 다르다.

이 버퍼 A[i](1<=i<=n)의 의미는, 길이가 i인 LIS를 구한다고 쳤을 때 존재 가능한 가장 작은 LIS 마지막 원소(와 그 원소의 위치)이다. 즉, 이 버퍼는 구해진 LIS의 길이만큼만 사용된다.

위의 예제 수열에서 매 원소가 들어올 때마다 버퍼는 다음과 같이 바뀌게 된다. 뒤에 새로운 원소가 추가되거나 이미 있는 값의 업데이트만 발생하지(O(1)), 배열 원소들을 전부 하나씩 밀어야 하는 삽입이나 삭제(O(n))가 발생하지는 않음을 염두에 두기 바란다.
3: 3
2: 2
1: 1
4: 1 4
5: 1 4 5
2: 1 2 5
3: 1 2 3
5: 1 2 3 5
3: 변화 없음
6: 1 2 3 5 6
4: 1 2 3 4 6

즉, 버퍼가 가리키고 있는 것은 각 길이별로 가장 작은 수일 뿐이다. 그러나 버퍼가 가리키는 순서대로 배열을 참조하면 수열이 언제나 오름차순, 즉 정렬이 돼 있다는 게 보장된다.
최소값을 갱신할 위치를 찾는 것은 이분 검색(binary search)으로 할 수 있다. 이 덕분에 작업이 O(n^2)에서 O(n log n)으로 줄어들 수 있게 된다. 정확하게 말하면 O(n log k)(k는 LIS 길이)이니 더욱 빠르다. worst case로 증가 수열을 만들 수가 없는 내림차순 수열을 던져 주면, 거의 O(n)이나 다름없는 속도로 금방 실행이 끝난다는 뜻이다.

물론, 이 버퍼에는 각 길이별로 가장 작은 증가 수열을 구하는 힌트만 들어있을 뿐, 가장 긴 LIS를 추적하는 정보는 전혀 들어있지 않다. 그렇기 때문에 추적 순서는 역시 별도의 배열에다 따로 보관해 놔야 하며 이 역시 그리 어렵지 않게 구현할 수 있다. 심심하신 분은 이 알고리즘을 직접 코딩해 보기 바란다.

정보 올림피아드를 공부하던 시절엔 이런 유형의 문제도 재미있었다. 뭐, 본인은 머리싸움에 쥐약인 타입인지라 경시 부문에서는 별 재미를 못 보고, 대박은 공모 부문에서 다 냈지만 말이다.

- 양수와 음수가 뒤섞인 n개의 수열이 있을 때 합이 가장 큰 구간을 O(n) 시간 만에 구하기
- 위와 비슷한 예로, 0.x와 n.x가 뒤섞인 n개의 수열이 있을 때 곱이 가장 큰 구간을 역시 O(n) 시간 만에 구하기
- x*y 2차원 배열이 있을 때, 이런 조건을 만족하는 가장 넓은 면적을 구하기 (1999년도 IOI의 공항 건설 부지 찾기 같은)

알고리즘이라는 게 OR(operations research)과 밀접한 관계가 있는 것 같다. 선형 계획법, 동적 계획법 같은 개념도 원래는 그 분야에서 유래되었기 때문에 용어에서 그다지 전산학적인 어원은 찾을 수 없다.
덧. algorithm인데 왜 다들 알고리듬이라고 적지 않고 알고리즘(=algorism?)이 보편화해 있는 걸까?

Posted by 사무엘

2010/11/30 09:00 2010/11/30 09:00
, , ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/421

Trackback URL : 이 글에는 트랙백을 보낼 수 없습니다

Comments List

  1. 김기윤 2010/11/30 09:25 # M/D Reply Permalink

    LIS 라길래 이게 뭐지? 했는데,
    문제를 보니까 접한 적이 있는 문제. (...........)

    저런 해법을 선배한테 강의받은 기억이 있습니다......만... 까먹고 있었다는게 문제 (......)

    알고리즘의 세계는 끝이 없는 것 같다..는 생각이 듭니다.

    1. 사무엘 2010/11/30 16:48 # M/D Permalink

      이 문제는 오늘날과 같은 형태로 동작하는 컴퓨터로 동작할 때 최소한 이 정도의 계산량이 동원되는 알고리즘이 필요하다...는 것을 직관적으로 알아챈다는 건 정말 대단한 능력이 아닐 수 없죠.
      LIS만 해도.. O(n^2)보다 더 낫게 만들 수 있다는 걸 선뜻 이해하기가 쉽지 않았답니다.

  2. 김재주 2010/12/01 11:51 # M/D Reply Permalink

    양수와 음수가 뒤섞인 n개의 수열이 있을 때 합이 가장 큰 구간을 O(n) 시간 만에 구하기


    이 문제 말인데...
    Q개의 쿼리를 통해서 수열의 임의 위치의 값을 바꿀 수 있고, 그 때마다 합이 가장 큰 구간을 갱신해서 구하는 문제로 바꾸면 상당히 재미있는 문제가 됩니다.

    할 일이 상당히 많이 늘어난 것 같지만 O(N + Q lg N)에 해결이 되죠.

    1. 사무엘 2010/12/01 18:03 # M/D Permalink

      실시간 갱신이라.. 마치 2001년과 2003년 IOI의 1번 문제를 떠올리게 하네요.
      어휴, 그래도 옛날에 알고리즘 공부하려고 시늉이라도 한 게 나중에 시간이 흐르고 나니 다 프로그래머 인생에 피가 되고 살이 된 것 같습니다. ^^

Leave a comment
« Previous : 1 : ... 1202 : 1203 : 1204 : 1205 : 1206 : 1207 : 1208 : 1209 : 1210 : ... 1571 : Next »

블로그 이미지

철도를 명절 때에나 떠오르는 4대 교통수단 중 하나로만 아는 것은, 예수님을 사대성인· 성인군자 중 하나로만 아는 것과 같다.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2019/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

Site Stats

Total hits:
1293613
Today:
264
Yesterday:
499