이마닷의 블로그

0. 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. 문제분석 - 외판원 순회(TSP, Traveling Salesman Problem)라는 유명한 알고리즘에 관한 문제이다. - 그래프 내 각각의 노드의 방문 상태를 알아야 하고 또 이전의 방문 상태 및 현재 방문 노드를 기준으로 다음 방문하는 노드와 상태가 정해진다는 점에서 각 노드의 방문 상태를 나타내기 위한 bitmask와 dynamic pr..

0. 문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 문제분석 - 트리라는 자료구조의 특성을 잘 알고 있다면 어렵지 않게 풀 수 있는 문제로, 트리가 가지고 있는 특성을 통해 리프노드를 찾기 위해서는 dfs를 사용해 문제를 풀어야 함을 알 수 있다. 트리는 cycle이 존재하지 않는 그래프이다. 하나의 트리는 하나의 루트만 존재한다. 루트가 여러 개라면 그것은 트리가 여러 개인 forest. 트리는 방향성이 존재하는(부모-자식)..

0. 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 문제분석 - 기존의 상태(기존에 배낭에 넣은 다른 물건들로 인해 결정된 무게)에 대해서 기존의 상태를 바꿀 수 있는 경우의 수(기존 배낭에 새로운 물건을 넣는 것) 중, 그 최댓값을 찾는다는 점에서 Dynamic Programming을 사용해 문제를 풀어야 함을 알 수 있다. - dp[n][w] : n번째 물건까지 ..

0. 문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 1. 문제분석 - 한 칸(노드)에서 시작해서 상하좌우로 인접한 칸을 연속해서 탐색한다는 점에서 DFS 또는 BFS 알고리즘을 사용..

0. 문제 https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 주사위의 전개도에서 A, B, C, D, E, F 의 순서로 입력된다. 입력되는 숫자 사이에는 빈 칸이 하나씩 있다. 주사위의 개수는 10,000개 이하이며 종류가 같은 주사위도 있을 수 있다. www.acmicpc.net 1. 문제분석 - 이 문제는 주사위 번호가 증가할 수록, 조건을 만족하는 면들 중 가장 값이 큰 면을 선택하면 된다. 따라서 단순한 그리디 알고리즘 문제이다. 또한 조건을 만족하는 모든 경우의 수를 ..

0. 문제 https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 작은 자연수이다. www.acmicpc.net 1. 문제분석 - 이 문제는 색종이들을 쌓아올렸을 때, 해당 색종이를 위에 올려 놓을 수 있느냐 없느냐의 여부가 여태까지 쌓아올린 색종이 더미 중 가장 위에 있는 색종이의 가로 세로 길이에 따라 달라진다. 즉, 현재의 경우가 직전의 경우에 영향을 받게 되므로, 동적 계획법(dynamic programming)을 사용해서 문제를 풀어야 했다. - 또한 색종..

0. 문제 https://www.acmicpc.net/problem/1162 1162번: 도로포장 문제 준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다. 문제는 N개의 도시가 주어지고 그 사이 도로들과 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 여기서 도로를 포장하게 되면 도로를 지나는데 걸리는 시간이 0이라 하자. www.acmicpc.net 1. 문제 분석 - 이 문제는 양방향 그래프에서 정해진 정점(1번 도시, 서울)을 기준으로 다른 정점(N번 도시, 포천)까지의 ..

0. 문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다. www.acmicpc.net 1. 문제 분석 이 문제는 우선 그리드가 주어지고, 조건을 만족하기 위한 이동 횟수의 최솟값(최단 경로)를 찾는다는 점에서 BFS 알고리즘을 이용해 문제를 풀어야 한다. 2. 유의할 점 - 각각 여섯 개의..