SY DevLog

5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이(Trie)를 이용하여 문제를 해결하였다. 트라이(Trie) 자료구조에 대한 기본적인 이해가 선행되어야 한다. 트라이(Trie) - 1. 트라이 개념 및 노드 특징 트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 트 lotuslee.tistory.com 전화번호에 일관성이 없는 경우는 트라이에..

2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 다이나믹 프로그래밍과 위상정렬을 이용하여 푸는 문제 먼저, 위상정렬을 이용하여 작업간의 순서를 빠른 순서대로 큐에 저장해둔다. Queue order = new LinkedList(); 그리고 dp 일차원 배열에는 작업의 최소 완료시간을 저장한다. dp[n] : 작업 n을 완료하기 위해 필요한 최소 시간 큐에서 가장 먼저 실행되는 작업(n)부터 하나씩 꺼낸다. dp[n] = dp[n] + time[n] 으로, dp[n]에 해당 작업의 소요시간(time[n..

2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 다이나믹 프로그래밍을 이용하여 풀이하였다. dp 배열을 3차원 배열로 만들었다. int[][][] dp = new int[T+1][3][W+1] int[][][] dp = new int[자두가 몇번째 떨어지는가][자두(사람이름)이 어느 위치에 있냐][이동횟수] dp[t][1][w] : t번째 자두가 떨어질 때, 1번 나무에서 떨어지는 경우 여태껏 w만큼 이동했을 때의 얻을 수 있는 자두 최대값 dp[t][2][w] : t번째 자두가 떨어질 때, 2번 나무에서 떨어지는 경..