알고리즘개론 과제 모음
2학년 2학기 때 들었던 알고리즘개론 수업 프로그래밍 과제를 정리했다.
Assignment 1
큐, 스택을 사용해 문제를 풀면 된다. 구글에 소스도 많고 메이져한 문제들이기 때문에 어렵지 않게 풀 수 있다.
1-1. Queue, BFS (Silver 1)
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
1-2. Stack (Gold 4)
실제로는 괄호, 사칙연산이 포함된 식을 계산하는 문제였다.
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net
Assignment 3
간단한 정렬 과제처럼 보이지만 배열의 크기, 배열의 값이 한정되어 있고, 어떤 TC로 채점할지 모르며, 수강생들의 실행 속도로 상대평가를 매겼기 때문에 모든 TC 경우의 수에서 빠르게 돌아가도록 케이스를 잘 나눠야 한다.
실제 제출은 이 Assignment 3 포스팅의 소스코드로 했지만, 지금이라면 $ N $ 이 $ 10^8 $ 근처일 때 counting sort로 풀었을 것이다.
Assignment 4
본격적으로 그래프를 다루는 과제들이 나왔다. Second Minimum MST는 우리 학교 국룰문제인 듯 하다. 자료구조개론 때는 $N, M$ 범위가 작아서 $logN$ LCA를 쓰지 않아도 풀 수 있었다. (그래도 자료구조에 이 문제를 내는거 자체가..) 이번에는 $N, M$ 범위가 백준이랑 똑같아서 얄짤없다. 그 때는 LCA가 뭔지도 몰랐기에 코드를 봐도 이해를 못했지만, 지금은 스스로 풀 수 있게 됐다.
4-1. Union-Find (Gold 4)
1717번: 집합의 표현
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는
www.acmicpc.net
4-2. MST (Gold 4)
1197번: 최소 스패닝 트리
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이
www.acmicpc.net
4-3. MST, sparse tree를 활용한 LCA (Diamond 5)
1626번: 두 번째로 작은 스패닝 트리
첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100,
www.acmicpc.net
4-4. Dijkstra (Gold 4)
10282번: 해킹
최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면
www.acmicpc.net
4-5. Dijkstra (Gold 3)
1810번: 징검다리 달리기 2
(0,0) - (1,2) - (3,2) - (4,1) - (6,3)의 경로를 따라 가면 8.4787...의 길이를 갖는 경로가 되며, 이것이 최단 경로이다.
www.acmicpc.net
Assignment 5
이번 과제도 5-3 빼고 다 그래프 문제이다. 5-3과 5-4는 수강생들의 실행시간 상대평가로 점수를 매겼다. 5-4를 정해로 푼 사람이 거의 없다는 것이 포인트다. (bitmask DP를 아는 4학기 재학생이 몇 명이나 될까,,)
5-1. Topological Sort (Gold 3)
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
5-2. Dijkstra (Gold 1)
1486번: 등산
첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000
www.acmicpc.net
5-3. Sort
백준에서 $K$ 값은 $K \leq N$이지만, 과제에서는 $N$ 범위보다 훨씬 작게 설정되어 있었다. 전략적으로 효율적인 풀이 방법을 잘 찾아야하는 문제
16455번: K번째 수 찾는 함수
C++17, Java 8, C11, PyPy3, C99, C++98, C++11, C++14, Java 8 (OpenJDK), Go, C99 (Clang), C++98 (Clang), C++11 (Clang), C++14 (Clang), C11 (Clang), C++17 (Clang)
www.acmicpc.net
5-4. Dijkstra, Bitmask DP (Platinum 5)
$O(P^22^P+PNlogN)$에 풀리는 문제이다. Bitmask DP를 안쓰고 기본 순열로 풀면 $O(P!)$ 단위로 올라가 만점은 못 받는다. (근데 이렇게 푸는 사람도 거의 없었다.)
23840번: 두 단계 최단 경로 4
첫째 줄에 정점의 수 N(10 ≤ N ≤ 100,000), 간선의 수 M(10 ≤ M ≤ 300,000)이 주어진다. 다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를
www.acmicpc.net
수업 후기
개인적으로 그래프 문제들이 많이 나와서 아쉬웠다. 5-4처럼 Bitmask DP를 써야 하는 문제나, Segment Tree, DP, String에 관해서도 가르쳐줬으면 좋았을 것 같다.
저 때는 LCA, Bitmask DP는 물론이거니와 MST, Dijkstra도 이해하기 힘들었던 때이다. 확실히 1년 반 전의 과제 코드를 보면서 지금 많이 성장했음을 느끼고 있다.
'대학 과제 복기' 카테고리의 다른 글
| [AL] 비트연산을 이용한 Radix Sort (0) | 2022.06.24 |
|---|