PS2 [서평 23년- 24] 알고리즘 트레이닝(초록이) | 두 번째 읽음 독서기간_2023년 5월 26일~6월 2일 저자_안티 라크소넨 출간일_2019년 5월 9일 예전에 읽다가 어려워서 후반부에 포기했었다. 그때보다 실력이 상승해서 다시 읽어보고자 꺼내 들었다. 정확히는 PS에 관심이 생겼다고 해야 하나. 목차를 보니 딱 절반 읽었었다. 작년에 읽을 당시엔 코테용 알고리즘만 공부했어서 고오급 알고리즘이 머선 말이고 했는데 그래도 조금 읽힌다. 몰랐는데 종만북 다음 가는 알고리즘 대회 입문서라고 한다. 일명 ‘초록이’라 불리는 책이다. 실전용 ‘파랑이’도 있다. 다음엔 파랑이를 읽어보겠다. 모듈러 연산부터 기하까지 기본적인 수학 조차 몰랐다는 게 부끄럽기도 하다. 벡터를 코드로 구현하고 외적을 계산한다라 흥미로웠다. 특히 트리를 공부하면 할수록 재미있다. 그래프와는 다른 매력.. 2023. 6. 8. [백준] 2261번: 가장 가까운 두 점 | C++ 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 브루트포스로 O(N^2) 시간에 해결할 수 있지만, O(NlogN)으로 푸는 방법을 알아보고자 한다. 정답코드 1. x좌표 기준으로 오름차순 정렬한다. 2. 0번째와 1번째 거리를 최소 거리(min_d)라고 가정한다. 3. 현재 살펴보는 좌표가 i번째 (x, y)라고 하면 [x - min_d, x] 범위에 해당하는 좌표를 "더 가까울 수 있는" 좌표 후보에 추가한다. 4. [y - min_d, y + min_d] 에 해당하는 좌표.. 2023. 6. 5. 이전 1 다음
