SY DevLog

2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 비트마스크를 이용한 동적 프로그래밍 + dfs 방법으로 풀 수 있는 문제이다. 아래는 문제 예제의 도시와 경로를 나타낸 것이다. dp 2차원 배열을 생성한다. 첫번째 인덱스는 현재 위치한 도시, 두번째 인덱스는 여태까지 방문한 도시정보를 비트마스크로 표현한다. dp[1][0001(2)] : 현재 위치한 곳은 1번 도시이고, 여태까지 방문한 도시는 1번 도시일 때, 전체 도시를 순회하기 위해 남아있는 최소비용 dp[2][001..

9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 중위순회한 결과가 주어지면 트리의 구조를 출력하는 문제이다. 중위순회의 특징을 알면 쉽게 문제를 풀 수 있다. 중위순회한 결과에서 가운데 값은 해당 트리의 루트에 해당한다. 1 - 6 - 4 - 3 - 5 - 2 - 7 즉, 전체 트리에 루트 노드는 3번이다. 그 다음 3을 기준으로 왼쪽(1 - 6 - 4)는 왼쪽 자식 트리를 중위순회한 결과이며, 오른쪽(5 - 2 - 7)은 오른쪽 자식 트리를 중위순회한 결과이다. 각각의 자식 트리도 ..

1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 그래프에서 최단거리를 구하는 문제이다. 사용할 수 있는 알고리즘은 다익스트라와 플로이드 워셜 알고리즘이 있다. 이 문제에서는 모든 정점과의 최단거리를 알아야 풀 수 있기 때문에 플로이드 워셜 알고리즘으로 문제를 풀었다. 문제에서 요구하는 경로표를 구하기 위해 ans라는 이차원 배열을 생성하였다. int[][] ans = new int[n+1][n+1]; 각각 배열의 원소에는 두 집하장 간 최단거리에서 가장 먼저 거쳐가는 집하장의 번호가 들어있다. 예를 들어, 1번 집하장..

5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 이번 문제를 트라이를 이용하여 풀 수 있는 문제이다. Trie 의 insert, contain, delete 함수외에 검색횟수를 반환하는 별도의 getCount() 함수를 만들어서 문제를 해결하였다. 트라이 알고리즘에 대해 잘 모른다면 아래 링크를 참조하길 바란다. lotuslee.tistory.com/53?category=965898 트라이(Trie) - 1. 트라이 개념 및 노드 특징 트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열..

2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net dp 2차원 배열을 이용하여 다이나믹 프로그래밍으로 문제를 해결하였다. 이 문제에서의 점화식은 다음과 같다. dp[n][0] : n번째 수열까지 중, 가장 긴 연속하는 증가하는 수열의 길이 dp[n][1] : n번째 수열까지 중, 가장 긴 연속하는 감소하는 수열의 길이 수열의 n번째 수를 n-1번째 수와 비교한다. n-1번째 수 < n번째 수 n-1번째 수가 더 작으므로 오름차순이 유지가 된다. 유지가 된다는 것은 n-1번째까지의 가장 긴 증가하는 수열의 길이(dp..

1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 트리에서 다이나믹 프로그래밍을 이용하여 푸는 문제다. dfs방식으로 루트노드에서부터 리프노드까지 top - down 으로 내려간 후, 다시 리프노드에서부터 위로 올라가면서 dp배열을 업데이트한다. dp배열은 이차원 배열로 생성하여서 n번 마을이 우수 마을인 경우와 그렇지 않은 경우로 나누었다. dp[n][0] : n번 마을이 우수 마을이 아닐 때, n번 마을을 루트노드로 하는 하위트리의 마을 주민 수의 총합 dp[n][1] : n번 마을이 우수 ..

1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 처음에는 문제를 잘못 읽어서 '단순하다 = 한 번 방문한곳을 또 방문한다'라고 이해하는 바람에 계속 답이 안나왔다. 문제를 올바르게 읽는 것의 중요성을 다시 한번 실감했다... 문제 잘못 읽었더니 30분 넘게 소비해버렸다.. 이 문제는 dfs방식으로 visited배열을 사용하여 한 번 방문한 곳을 방문하지 않으면서, 총 N번 이동하면 된다. visited배열은 로봇이 최대 14번 이동이 가능하므로 (15, 15)위치에서 로봇이 출발한다고 할 때, 로봇이 움직..

5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 앞 면, 뒷 면, 왼쪽 면, 오른쪽 면, 윗 면, 아랫 면 6가지 경우의 수와 시계 방향으로 돌릴 때, 반시계 방향으로 돌릴 때 이렇게 2가지 경우 총 12가지의 경우의 수를 구해서 푸는 문제이다. 문제 자체는 어렵지 않으나, 모든 경우의 수를 다 생각해야 하기 때문에 코드도 길어지고 반례 찾는것도 힘들었다. 나는 cube 3차원 배열을 만들어서 첫번째는 어떤 면인지를 의미하고, 해당 면에서 3x3의 수를 넣어주었다. char[][][] cube = new cha..

13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 처음에 각각의 A[n]에 대하여 무조건 총감독 1명은 필요하므로 cnt를 하나 증가시키고, A[n]에서 총감독이 감독하는 B명을 빼었다. -> A[n] - B 그리고 난 후, A[n] - B를 부감독이 감독할 수 있는 응시자 수인 C로 나누어서 몫을 cnt에 더하고, 만약 나머지가 존재하면 그 나머지 응시자도 감독을 해야하므로 cnt를 하나 더 증가시켰다. 그런데 결과는 '틀렸습니다.' 가 떴다. 내가 놓친..

10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 어느 한 도시에서 출발하여 모든 도시를 거친 후, 처음으로 돌아오는 문제이다. 여기서 알아야 할 사실은 어느 도시에서 출발하든 가장 적게 드는 비용은 동일하다는 것이다. 따라서 아무나 한 곳을 시작도시로 정해서 dfs를 사용하여 시작한 곳으로 돌아오면 된다. 모든 도시를 한 번씩만 방문해야하므로 visited 배열을 이용하여 방문 여부를 표시한다. 그런데 문제를 풀면서 한가지 헷갈렸던 점이 있다. 처음 시작한 도시는 이..