최근 풀면서 재미있거나 기억나는 문제 모음.
알고리즘 : 깊이 우선 탐색, check 배열을 두 개를 돌리면서 사이클을 검사해야하는 문제(위상정렬로도 가능)
https://www.acmicpc.net/problem/9466
9466번: 텀 프로젝트
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을
www.acmicpc.net
알고리즘 : DFS, BFS, 구현(섬의 높이를 어떻게 구해나갈지 생각하기가 힘들었음)
https://www.acmicpc.net/problem/1109
1109번: 섬
첫째 줄에 높이가 0인 섬의 개수, 높이가 1인 섬의 개수, …, 높이가 M인 섬의 개수 까지 공백으로 구분해서 출력한다. 만약 섬이 하나도 없을 때는 -1을 출력한다.
www.acmicpc.net
알고리즘 : 애드 혹(각 장소에서 가장 강한 두 용의 차이가 M 이하이면 다른 용들의 순서는 의미가 없다는 것을 생각해내면 풀 수 있는 문제)
https://www.acmicpc.net/problem/26599
26599번: 용 조련사 룰루
첫째 줄에 $N$과 $M$이 공백을 사이에 두고 주어진다. $(1 \leq N \leq 1\,000\,000;$ $1 \leq M \leq 10^{9})$ 둘째 줄에 용의 힘 $P_{i}$가 번호 순으로 공백을 사이에 두고 주어진다. $(1 \leq P_{i} \leq 10^{9})$ 용을 한
www.acmicpc.net
알고리즘 : 비트마스킹, BFS(bit 열쇠, 그냥 재밌었음)
https://www.acmicpc.net/problem/1194
1194번: 달이 차오른다, 가자.
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,
www.acmicpc.net
알고리즘 : 구현, 시뮬(시뮬 종료 조건이 재미있었던 문제)
https://www.acmicpc.net/problem/31404
31404번: 아리스, 청소합니다! (Easy)
첫 번째 줄에 방의 크기를 나타내는 $H, W$가 주어집니다. $(1 \le H, W \le 64)$ 두 번째 줄에 아리스의 처음 위치를 나타내는 $R, C, D$가 주어집니다. 아리스의 좌표는 $(R,C)$이고, 위쪽을 기준으로 시계
www.acmicpc.net
알고리즘 : 다익스트라(Softeer에서 봤었는데, 재미있는 문제, 이전 활자그래프는 무향그래프라는 것에 유의하자)
https://www.acmicpc.net/problem/30881
30881번: 활자 그래프
첫 번째 줄에 $T$번 활자 그래프에서, $1$번 정점에서 $2$번 정점으로 가는 최단 경로를 출력한다. 만약 $1$번 정점에서 $2$번 정점으로 가는 경로가 없거나, 이 값이 $10^{18}$보다 크다면 $-1$을 대신
www.acmicpc.net
알고리즘 : BFS, 시뮬, 구현(체비쇼프 거리, 실패 조건을 잘 생각하자)
https://www.acmicpc.net/problem/28452
28452번: 탄막 게임
두 점 $A(x_1, y_1)$과 $B(x_2, y_2)$ 사이의 맨해튼 거리는 $|x_2 - x_1| + |y_2 - y_1|$으로 정의된다.
www.acmicpc.net
알고리즘 : 구현, 시뮬(뱀 플래티넘 버전, t의 값이 억 단위로 주어지지만, 회전 명령은 1000 이하인것을 잘 이용하자)
https://www.acmicpc.net/problem/10875
10875번: 뱀
가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는
www.acmicpc.net