SY DevLog

1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 정답률에 비해 어려웠던 문제였다. 비트마스크가 아직 익숙하지 않아서 그런지 비트마스크를 이용해서 메모이제이션을 어떻게 해야할지 고민하는데 시간이 오래 걸렸다. n번째 자리에 k라는 수가 오기 위해서는 n-1번째 자리에 k+1 혹은 k-1가 있어야 한다. 만약 비트마스크를 이용하지 않고 메모이제이션을 하면 다음과 같이 점화식을 세울 수 있다. dp[n][k] = dp[n-1][k-1] + dp[n-1][k+1] 그런데 이 문제에서는 해결해야하는 조건이 있다. 0부터 9까지 모든 수를 한번씩 사용해야 한다. 따라서, 0~9중에서 어떤 수를 사용했는가를 비트마스크를 이용하여 기록해야 ..

14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 트라이를 사용하여 문제를 해결하였다. 보통은 트라이노드의 Key값에 char형을 넣지만, 이 문제에서는 두 번째 예제의 경우 문자열이 하나의 노드에 들어가야 하므로 char형이 아닌 String형으로 변경하였다. 또한, 문제에서 알파벳 순서대로 출력해야 하므로 자식 노드들 중 알파벳 순서상 앞에 위치한 노드부터 탐색해야 한다. 따라서 TreeMap을 사용하여서 자동으로 알파벳 순으로 정렬되도록 했다. Map childNodes = new TreeMa..

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..