http://moogi.new21.org/tc/ 그런즉 이제 애호박, 단호박, 늙은호박 이 셋은 항상 있으나, 그 중에 제일은 늙은호박이니라. 2024-06-23T20:08:42+09:00 Textcube 1.7.8 : Con moto (김기윤) http://moogi.new21.org/tc/421#comment1124 2010-11-30T09:25:13+09:00

LIS 라길래 이게 뭐지? 했는데, 문제를 보니까 접한 적이 있는 문제. (...........) 저런 해법을 선배한테 강의받은 기억이 있습니다......만... 까먹고 있었다는게 문제 (......) 알고리즘의 세계는 끝이 없는 것 같다..는 생각이 듭니다.

(사무엘) http://moogi.new21.org/tc/421#comment1125 2010-11-30T16:48:09+09:00

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

(김재주) http://moogi.new21.org/tc/421#comment1126 2010-12-01T11:51:17+09:00

양수와 음수가 뒤섞인 n개의 수열이 있을 때 합이 가장 큰 구간을 O(n) 시간 만에 구하기 이 문제 말인데... Q개의 쿼리를 통해서 수열의 임의 위치의 값을 바꿀 수 있고, 그 때마다 합이 가장 큰 구간을 갱신해서 구하는 문제로 바꾸면 상당히 재미있는 문제가 됩니다. 할 일이 상당히 많이 늘어난 것 같지만 O(N + Q lg N)에 해결이 되죠.

(사무엘) http://moogi.new21.org/tc/421#comment1127 2010-12-01T18:03:35+09:00

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