링크: https://www.acmicpc.net/problem/1525 비트마스크로 해결하는 BFS이다. 3*3 퍼즐을 123 456 780 의 9자리 정수로 본다. 여기서 123456780이 문제에서 말하는 정리된 상태, 즉, 목표이다. 각 칸마다 퍼즐을 이동 시킬 수 있는 주변 4방향이 다르다. 구현하는 방법은 각 칸마다 인접 리스트를 만들거나, 행렬로 표현하든지 if문으로 하는 등 다양하다. 아래 코드에서는 반대로 이동이 불가능한 방향을 저장해서 구현했다. 문제는 "123456780" 과 같은 상태를 방문 했는지 여부를 확인하기에는 visit[876543210]를 수용할 수 있는 배열 크기가 필요하다. 하지만 실제로 나타날 수 있는 상태의 개수는 \(9! = 362,880\) 이다. 방문했음을 저..

링크: 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, k=2)+ (n=0, k=2) 3개의 수를 n=20 내에서 고르는 경우의 수 = 첫 번째 수로 0을 사용하고, 나머지 2개의 수를 n=20 내에서 고르는 경우의 수+ 첫 번째 수로 1을 사용하고, 나머지 2개의 수를 n=19 내에서 고르는 경우의 수+ .... 작은 문제로 쪼개어 해결이 가능하다. dp 테이블을 두고 메모이제..

링크: 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)..