Joonas' Note

링크: https://www.acmicpc.net/problem/2225문제의 예시로 n=20, k=2일 때 나올 수 있는 경우의 수는 0 + 20 1 + 19 2 + 18   ...19 + 120 + 0로 총 21개이다.풀이n=20이고 k=3이라면, 경우의 수는 아래와 같은 모양으로 전개된다.(n=20, k=3) =   (n=20, k=2)+ (n=19, k=2)+ ...+ (n=1, ..

링크: https://www.acmicpc.net/problem/3075문제p개의 은하가 있을 때, n명과 교통비의 합이 최소가 되는 어떤 하나의 은하(미팅 장소)를 찾는 문제이다.조심할 것조건이 특별히 안 적혀있어서 조심해야 할 게 많은 문제였다. 주의해야 할 조건으로는1. 하나의 은하에 여러 사람이 있을 수 있고2. 은하와 은하 사이에는 여러 개의 길이 존재할 수 있다(doju님의 데이터 추가 글)나는 외딴 섬에 대한 케이스를 처리 못해..

링크: https://www.acmicpc.net/problem/15686문제 설명 마지막 줄에 다 요약되어있다. 도시에 있는 치킨집 중에서 최대 \(m\)개를 골라야한다.문제 조건에서 치킨집의 개수는 최대 13개이고, 도시에 있는 치킨집 \(k\)개 중에 \(m\)개를 고르는 경우의 수는 $$C(k, m) = \frac{k!}{m!(k-m)!}$$숫자가 작아서 많아봐야 1500개가 좀 안되므로 치킨집을 선택하는 ..

링크: https://www.acmicpc.net/problem/15685문제알고스팟의 JM북에 그려진 그 드래곤 커브가 맞다. 간단한 수학 규칙으로 그려지는 그림인데, 이 문제에서는 드래곤 커브가 네 꼭지점을 모두 지나는 칸이 몇 개인지 구하는 거였다.풀이드래곤 커브의 규칙을 미리 만들어놓고, 드래곤 커브의 시작점과 시작 방향이 주어졌을 때 규칙에 맞게 이동하면서 주변 칸에 해당 꼭지점이 지나갔음을 기록한다.드래곤 커브는 이전 세..

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

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

백준 온라인 저지를 운영하는 스타트링크에서 사용하는 알고리즘 정기 강의 커리큘럼이다.https://offline.startlink.help/hc/ko/articles/2172451581. 알고리즘과 입/출력2. 자료구조 1- 큐/스택/데크- 문자열3. 다이나믹 프로그래밍 14. 알고리즘 수학 1- GCD/LCM- 소수5. 정렬6. 그래프 1- 정의와 표현방법- 탐색 (DFS/BFS)- 모델링7. 트리 1- 순회- 저장- 트리와 관련한 알고리즘8. 그..

2017 ACM-ICPC 대전 예비소집과 본선을 위해 11월 10일에 팀원들과 함께 대전으로 갔다. (대회는 11일)PS 공부를 시작한 건 오래되었지만 항상 깊게 공부하지 못했다. 특히 3년 전에 참가했을 때보다 더 못한 실력으로 참가하게 되어서 자괴감이 너무 심했다.특히 올해는 킹갓갓갓엠페러분들이 너무 많이 참가하셔서 정신 못 차리고 사람들 구경하느라 바빴다.예비소집 때 기본적인 세팅을 확인하는데, 이번 대회는 특이하게 우분투 16.04 ..

링크: https://www.acmicpc.net/problem/2887 모든 행성을 터널로 연결할건데, 그 비용의 합이 최소가 되게 만드는 최소 스패닝 트리 문제이다. 문제는 \(N\)이 너무 커서, 행성 사이의 간선을 전부 살피는 건 힘들다는 것이다. 두 행성 A와 B의 거리를 \(min(|x_A - x_B|, |y_A - y_B|, |z_A - z_B|)\) 로 정의했기 때문에 어떤 행성에서 가장 가까울 행성의 후보가 확 줄어든다. ..

링크: https://www.acmicpc.net/problem/2718[이전 게시글로부터 글 옮김]2x1 크기의 타일로 4xN 크기의 타일을 채우는 경우의 수를 구하는 문제이다.문제를 작은 문제로 쪼개야하는 데 발상보다는 과정이 쉽게 떠오르지 않아서 해결하는 데 오랜 시간이 걸렸다.2xN 타일 크기의 문제와 똑같이 왼쪽부터 1줄씩 채워나가면서 완성해나간다. 하지만 이 문제는 높이가 4N이기 때문에 1줄을 채울 때 여러 개의 경우가 나온다...