인생은 여행, 즐기며 살렵니다

[결과] - 이지를 빠르게 풀지 못해서 레이팅이 떨어졌다. 1339 -> 1241 (약 -100). - 이지 제출 점수는 100점, 챌린지 실패로 75점. 나머지 문제는 손대지 않음. - 전체 약 700명 중 654등........ [과정] - Easy 문제를 먼저 열고 풀었다. 그러나 처음에 알고리즘을 생각하는 것과, 그것을 적절히 구현하는 데에 시간이 많이 걸렸다. 또한 나중에 보니 비효율적인 구현이라(비트 이용) 코드가 더 길고, 따라서 제출이 늦게 될 수밖에 없었다. - Easy를 푸는데 너무 오랜 시간을 소비했다. 풀고 나니 40분이 지나가서 남은 시간은 20분이었다. 따라서 Mid 문제를 시간 내에 풀기가 어려울 것으로 예상되어, 남은 시간은 Challenge Case를 만드는 데에 주력했다...

일단 여행 와서 첫 SRM을 도전하게 된 것이 참 느낌이 이상하다. 결국 게으름에 지지 않고 도전하게 되어서 기분 좋다. 3시간 전 등록. 기다리고, 잠 좀 자다가 20분 전에 일어나서 기다렸다. 이번 SRM에서 느낀 점은, 1. 쉬운 문제를 submit하기 전에, 확실히 반례가 있는지 확인해보고 넘길 것. (250, 특히 550) - 이번 문제의 경우, 550 문제를 빨리 풀고 1000점을 열었는데, 1000점은 풀지 못했고 끝부분에 와서야 550의 오류를 발견했다. 시간이 매우 많이 흘렀기 때문에 165.00의 최하점을 맞았고, submit을 바로 하지 말고 이런저런 예를 더 넣어서 확인해보는 것이 훨씬 더 좋은 점수를 받을 수 있었을 것이라 예상된다. 2. Challenge Set의 아이디어들을 미..

여기까지 푸느라 수고했다 !! 앞으로는 더 힘차게 나아가보자 !! (2013. 05. 10 ~ 05. 29) - SRM 8개 (DIV 1, 2) / 20일 [ 결과 정리 ] SRM 번호 / DIV 번호 Easy Medium Hard 313 DIV 1 O ㅡ (미시도 문제) ㅡ DIV 2 O O (DIV 1의 Easy와 같음) O 314 DIV 1 O O (DIV 2의 Hard와 같음) ㅡ DIV 2 O O (DIV 1의 Easy와 같음) X -> △ (editorial 참조) 315 DIV 1 O (DIV 2의 Mid와 같음) △ (editorial 참조) ㅡ DIV 2 O O X -> △ (editorial 참조) 316 DIV 1 O (DIV 2의 Mid와 같음) ㅡ ㅡ DIV 2 O O O 317 ..

(앞의 (상) 에 해당하는 글을 보지 못하신 분은, 먼저 보고 오시면 좋겠습니다.) (다시 한 번 적습니다만, 이 책은 [알고리즘 문제 해결 전략] 의 책 내용을 정리한 것입니다,) 저번 글에서는, u에서 v까지 가는 경로 중에, S의 원소를 경유점으로 사용하는 최단 경로의 길이는 [1번 식] 로 나타나짐을 살펴보았다. 이제 이 식을 점화식 형태로 나타내기 위해서, 형태를 살짝 바꾸어 보자. 그래프의 노드의 개수가 V개라면, 각각의 노드들을 0부터 V-1 까지 번호를 붙일 수 있다. 인 원소 k에 대해서, 이라 하자. 다른 말로 하면, 는 0부터 k까지의 정수를 원소로 갖는 집합이다. 이렇게 표현하는 경우, 는 0부터 k까지의 노드의 집합이 되며, 우리가 구하고자 하는 u에서 v까지의 최단 거리는, '모..

플로이드의 모든 쌍 최단 거리 알고리즘 (이 내용은 '알고리즘 문제 해결 전략' 의 내용을 정리한 것입니다.) 1. 플로이드의 최단 쌍 알고리즘의 기본적인 개념 그래프 내의 어떤 두 점을 u와 v라고 할 때, u에서 v로 가는 경로가 있다고 하자. 이 두 점을 잇는 경로는, u와 v를 직접적으로 연결하는 하나의 간선일 수도 있고, 아니면 다른 점들을 거쳐서 가는 경로일 수도 있다. 후자의 경우, 예를 들면 u - a - b - c - v 와 같은 형태가 될 것이다. 이렇게 u에서 v로 가는 경로가 다른 점을 경유해서 가는 경우, 이 경유하는 점들을 경유점이라 하자. 즉, 위에 예로 든 경로에서는 a, b, c가 경유점이 된다. 정점 집합 S에 포함된 정점만을 경유점으로 사용해서, u에서 v로 가는 최단 ..

(http://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot) 퀵 정렬에서의 피봇 선택에 따라서, 퀵 정렬의 실행 시간은 O(NlgN)에서 최대 O(N^2) 까지 걸릴 수 있다. 나쁜 (worst-case)의 경우의 예를 들면, - 이미 정렬이 되어 있는 배열 (또는 거의 정렬된 배열) - 반대로 정렬이 되어 있는 배열 을 정렬하고자 할 때, pivot을 가장 첫 번째 원소나 가장 마지막 원소로 지정하는 것이다. 이 경우, 각 단계마다 '원소 1개'와 '나머지 원소 전부' 로 쪼개지기 때문에, divide-and-conquer 방식의 이점을 살리지 못하게 된다. 효율적인 Quick Sort를 위해서는, pivot을 잘 선택할 필요가 있다..