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

1. reverse_iterator를 만드는 방법 (constructor) (http://www.cplusplus.com/reference/iterator/reverse_iterator/reverse_iterator/) 다음과 같이 사용한다. ex1) vector::reverse_iterator riter1(iterator iter) // iterator를 사용해서 reverse_iterator 만들기 - 이 때 생성되는 reverse_iterator는, 생성에 사용된 iterator가 가리키는 원소의 바로 이전 원소를 가리킨다. 아래의 코드를 보면 쉽게 알 수 있다. (출처 : 위의 URL) // reverse_iterator example #include // std::cout #include // ..

둘 다 ForwardIterator, 즉 증가 연산 (++) 이 되는 iterator를 가진 컨테이너에 대해 동작한다. 즉, vector, set, multiset, map, multimap ... 등에서 동작한다. * lower_bound는, 첫 원소의 iterator에서 시작하여 iterator을 ++증가시키며 탐색하다가, '비교 결과 주어진 값보다 먼저 나오지 않는(not compare less than) 첫 원소'의 iterator를 반환한다. * upper_bound는, 첫 원소의 iterator에서 시작하여 iterator을 ++증가시키며 탐색하는 것은 동일하나, '비교 결과 주어진 값보다 나중에 나오는(compare greater than) 첫 원소'의 iterator를 반환한다. 두 개가 ..

같은 종류의 두 pair의 크기 비교는, "사전순 (lexicographical order)" 으로 이루어진다. 무슨 말이냐면, first의 element를 먼저 비교하고, 만일 거기서 판가름이 나지 않는 경우에는 second를 비교하여 크기를 정하게 된다. 정확한 크기 비교의 정의는 http://stackoverflow.com/questions/2819245/is-stdpairint-stdstring-ordering-well-defined 위의 정의에 따르면, pair y 가 x 보다 크다는 것은 case 1. y의 first가 x의 first보다 큰 경우이거나, case 2. case 1이 만족되지 않았을 때(short-circuit), x의 first가 y의 first보다 크지 않으면서, y의 se..

Petr의 성적. Easy를 4분만에, Mid를 11분만에, Hard를 31분만에 해서 Submit 했다. 컴파일도 아니고 서브밋 !! 총 1시간의 코딩 시간 동안, 46분밖에 쓰지 않은 것이다. 대단하다. 언젠가는 저곳에 올라가리라.

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

누군가 내가 작성한 코드를 받아서 쉽게 유지보수 할 수 있다면, 나의 할 일은 금방 사라질 것이다. 그런 의미에서 이 책은 유지 보수하기 어렵게 코딩하는 법을 가르친다. 한빛미디어에서 무료로 pdf를 나누어주고 있다. 한번 보시라. 실제로 이렇게 코딩하면 안 되지만, TopCoder에서 챌린지 방지용으로 활용하면 쓸만하겠다??

일단 여행 와서 첫 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로 가는 최단 ..