https://www.acmicpc.net/problem/21276문제를 보고 떠올린 방법은 다음과 같다.indegree를 측정하는데, 편하게 측정하기 위해 string -> int로 index를 가지고 있는 map list를 생성하였다.indegree가 0인 노드가 가문의 시조가 되고, 위상 정렬을 하면서 사전순으로 방문해야 한다.위상 정렬을 하면서 하나 방문하고 직계 자식을 구해야 하는데, 직계 자식은 indegree가 1이어야 한다. 즉, 현재 노드와 현재 노드와 연결된 간선을 제거했을 때 indegree가 0인 노드가 직계 자식이다.이 정도로 알고리즘을 생각해 두고 구현해 봤는데 정렬을 하면서 직계 자식을 구하고, 위상 정렬을 수행하고 하는 과정이 너무 번거롭고 시간 복잡도 상으로 비효율적이었다...

20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 7 4 apple ant sand apple append sand sand ans : sand apple append 100,000개의 단어를 기준에 따라 정렬하면 된다. 우선 빈도를 저장해둬야 하는데 최대 O(n log n)으로 저장해야 하므로 맵에 저장을 했다. 그리고 기준에 따라 정렬을 해주면 되는데 우선순위 큐를 사용했다. 정렬 기준을 설정하는 건 항상 헷갈리는데 구조체에 () 연산자 오버..

13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 예제 4 2 3 1 5 2 4 1 ans : 18 4 3 3 4 1 1 1 1 ans : 10 문제를 잘 생각해 보면 기름 값이 가장 싼 도시를 3번 도시라고 하자. 그럼 3번 도시부터 목적지까지의 거리만큼 기름을 3번 도시에서 다 사두고 2번 도시를 다시 목적지로 두고 반복하면 된다. 이렇게 구현한다면 기름 값이 가장 싼 도시를 계속해서 갱신해야 하므로 우선순위 큐를 사용했다. 그리고 목적지를 갱신하는 방법은 좀 번거로워서 방문처리를 하는 방식을 ..

10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 예제 4 1 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 2 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 3 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 900 4 918 917 916..

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 조건제한이 걸린 경로를 찾는 문제이다. 가장 먼저 떠올린 풀이는 dp [i][j]를 (i, j)까지 도달할 수 있는 경우의 수로 두고 네 방향 모두에서 (i, j)로 도달할 수 있으므로 4방향을 순차적으로 채우는 방법이었다. 이 방법은 아래와 같은 케이스를 잡아내지 못했다. 다음에 떠올린 방법은 DFS였다. DFS에서 백트래킹 느낌으로 메모이제이션을 떠올릴 수 있었다. 어떤 점 (i, j)에서 더 이상 갈 수 있는 곳이 없으면 (i, j)에 도달하면 바로 종료하는 방..

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제를 읽었을 때 바로 느껴지는 점은 어째서 암호코드 가짓수를 구하는 거야...? 였다. 농담이고 전에 푼 다른 DP 문제가 떠올랐다. [BOJ] C++ 2193: 이친수 - DP 테이블링 연습하기 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으 jun-n.tistory.com 이 문제랑 굉장히 비슷한 과정으로 테이..