[이전 블로그]에서 글 옮김 링크: https://www.acmicpc.net/problem/1766풀이처음에는 문제의 접근 방향을 후위순회처럼 생각했다. 어떤 x번째를 하기 위해서 그 이전것을 무조건 해결해야하는 방식. 틀리고 나서 문제를 다시 이해했는데, 깨달은 테스트 케이스부터 말하자면 아래와 같다.5 3 4 1 2 3 5 3 내가 생각한 이 입력의 정답은 아래와 같다.2 4 1 5 3 1번보다 4번을 먼저 풀어야하고, 3번보다 2, 5번을 먼저 풀어야한다. 1번을 풀기 위해서 4번을 풀어야하는데, 같은 우선순위에서 4번보다는 2번이 쉽다. (둘 다 1개의 문제 앞에 있음)2번을 풀고 4번을 풀면, 1번이 풀리고 남은 5번을 풀면 3번이 풀린다. 처음에 생각한 대로라면 4 1 2 5 3 이 나와야하..

링크: https://www.acmicpc.net/problem/3075 문제p개의 은하가 있을 때, n명과 교통비의 합이 최소가 되는 어떤 하나의 은하(미팅 장소)를 찾는 문제이다. 조심할 것조건이 특별히 안 적혀있어서 조심해야 할 게 많은 문제였다. 주의해야 할 조건으로는1. 하나의 은하에 여러 사람이 있을 수 있고2. 은하와 은하 사이에는 여러 개의 길이 존재할 수 있다(doju님의 데이터 추가 글) 나는 외딴 섬에 대한 케이스를 처리 못해서 틀렸었다. 풀이미팅 장소가 될 은하를 하나 잡고, 그 은하로부터 나머지 사람들과의 거리의 합을 구한다. 이 때, 거리의 합이 최소가 되는 은하가 정답이다. 은하의 개수 \(p \lt 100\) 로 작은 크기이기 때문에, 플로이드-와샬 알고리즘으로 구현하면 간단..

링크: https://www.acmicpc.net/problem/15686 문제 설명 마지막 줄에 다 요약되어있다. 도시에 있는 치킨집 중에서 최대 \(m\)개를 골라야한다.문제 조건에서 치킨집의 개수는 최대 13개이고, 도시에 있는 치킨집 \(k\)개 중에 \(m\)개를 고르는 경우의 수는 $$C(k, m) = \frac{k!}{m!(k-m)!}$$숫자가 작아서 많아봐야 1500개가 좀 안되므로 치킨집을 선택하는 모든 경우의 수를 시도해 볼만 하다. 정해진 \(m\)개의 치킨집마다 모든 사람들의 집에 도달하는 최소 거리를 사람이 사는 집 기준으로 저장해둔다. 즉, 어떤 조합에 대해 \(j\)번 집은 가장 가까운 치킨집과의 거리를 저장하고 있다. 매 조합마다 모든 거리를 구하면 오버헤드가 심하므로 미리 ..

링크: https://www.acmicpc.net/problem/15685 문제알고스팟의 JM북에 그려진 그 드래곤 커브가 맞다. 간단한 수학 규칙으로 그려지는 그림인데, 이 문제에서는 드래곤 커브가 네 꼭지점을 모두 지나는 칸이 몇 개인지 구하는 거였다. 풀이드래곤 커브의 규칙을 미리 만들어놓고, 드래곤 커브의 시작점과 시작 방향이 주어졌을 때 규칙에 맞게 이동하면서 주변 칸에 해당 꼭지점이 지나갔음을 기록한다. 드래곤 커브는 이전 세대의 드래곤 커브를 이용하기 때문에 반복적인 구조이다. 각 방향과 관련된 변수들을 잘 설정하면 쉽게 구현할 수 있다. 나는 문제에 맞춰 우,상,좌,하 순서로 0,1,2,3을 사용했다. 원소들은 진행 방향, 드래곤 커브를 \(G_0 = \{\dots, a, b, c, d\}..

링크: https://www.acmicpc.net/problem/12755 2016 전북대학교 프로그래밍 경진대회 A번 비슷한 문제로는 BOJ 1748 - 수 이어 쓰기 1이 있는데, 거기에 조건을 하나 더 얹었다. 앞에서부터 \(N\)번째 자리에 있는 수를 출력하는 것이다. 1부터 \(N\)까지 전부 확인하는 건 시간적으로도 메모리적으로도 무리다. 따라서 탐색 범위를 좁힐 필요가 있는데 이 문제에서는 자리수별로 인덱스를 자르면 좀 낫다. 1자리 수는 1부터 9까지 9개가 있으며, 전부 이어 붙이면 길이가 9이다.2자리 수는 10부터 99까지 90(=99-10+1)개가 있으며, 전부 이어 붙이면 길이가 180(=90*2)이다.3자리 수는 100부터 999까지 900(=999-100+1)개가 있으며, 전부..

[이전 블로그에서 글 옮김] https://www.acmicpc.net/problem/2022 https://uva.onlinejudge.org/...&problem=1507 \(a, b, c\) 가 주어지면 \(k\) 를 구해내는 문제이다. 피타고라스로 A, B를 구해서 기울기를 구하고, 두 직선의 교점 방정식을 이용했다. 그리고 교점의 y 위치가 \(c\) 가 되는 순간을 구하도록 이분 탐색을 했다. 우선 a가 포함된 직선을 g(x), b가 포함된 직선을 f(x)라 한다면 아래와 같은 정보가 나온다. \( \begin{cases} A = \sqrt{a^2 - k^2} \\ B = \sqrt{b^2 - k^2} \end{cases} \) \( \begin{cases} f(x) = \frac{B}{k}x..

백준 온라인 저지를 운영하는 스타트링크에서 사용하는 알고리즘 정기 강의 커리큘럼이다.https://offline.startlink.help/hc/ko/articles/217245158 1. 알고리즘과 입/출력2. 자료구조 1- 큐/스택/데크- 문자열3. 다이나믹 프로그래밍 14. 알고리즘 수학 1- GCD/LCM- 소수5. 정렬6. 그래프 1- 정의와 표현방법- 탐색 (DFS/BFS)- 모델링7. 트리 1- 순회- 저장- 트리와 관련한 알고리즘8. 그리디9~10. 분할 정복- 이분 탐색- 머지 소트/퀵 소트- 가장 가까운 두 점11~12. 완전 탐색- 비트마스크- 순열- 부르트 포스- 백트래킹13. 자료구조 2- 스택 2- 서로소 집합(Disjoint-Set)- 힙과 힙 소트- 이진 탐색 트리 (BST)..

4년 만이다. 2017 ACM-ICPC 대전 예비소집과 본선을 위해 11월 10일에 팀원들과 함께 대전으로 갔다. (대회는 11일) PS 공부를 시작한 건 오래되었지만 항상 깊게 공부하지 못했다. 특히 3년 전에 참가했을 때보다 더 못한 실력으로 참가하게 되어서 자괴감이 너무 심했다.특히 올해는 킹갓갓갓엠페러분들이 너무 많이 참가하셔서 정신 못 차리고 사람들 구경하느라 바빴다. 예비소집 때 기본적인 세팅을 확인하는데, 이번 대회는 특이하게 우분투 16.04 LTS 환경으로 진행됬다. 미리 공지를 확인하고 이미지를 받아서 사용해봤지만 팀원 한 명이 우분투 사용을 힘들어해서 세팅에 신경을 많이 썼다. 예비소집이 끝나고 숙소를 잡으러 택시를 잡으려는데 택시가 진짜 1도 안보였다. 겨우 찾아도 빈차가 아니었고 ..