![]()
문제 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 문제 풀이 앞에서 풀었던 1197 최소 스패닝 트리에서 입력형식만 바뀐 거지 문제 풀이는 똑같다. 앞선 문제에서 주어졌던 입력 형식인 from->to->value가 배열 형식으로 i -> j -> input값으로 바뀐것이다. 따라서 해당 입력형식에 따라 노드를 생성하고, 크루스칼 알고리즘을 사용하면 쉽게 풀 수 있다. 전체 코드 package MST.`16398_행성_연결`.LJH impor..
![]()
문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 풀이 MST를 구현하는 기본적인 문제이다. 우선 MST가 무엇인지에 대해서 알아야 한다. MST는 Minimum Spanning Tree이다. Spanning Tree의 조건은 V개의 정점이 있다면 V-1개의 간선을 이용해서 모든 정점을 연결할 수 있어야 한다. 그렇다면 MST는 모든 정점을 연결하면서 가중치의 합이 최소가 되어야 한다. 물..
![]()
문제 https://www.acmicpc.net/problem/15659 15659번: 연산자 끼워넣기 (3) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 풀이 정말 까다로운 문제였다. 연산자들의 우선순위를 해결해줘야 했기에, 그 부분에서 사람들이 많이 어려움을 느꼈을 것이라고 생각한다. dfs를 이용해서 모든 경우의 수를 탐색하고, 해당 식의 최솟값과 최댓값을 구한다. 초기 풀이 방식에서는 숫자와 연산자들을 모두 포함하는 배열을 하나 생성했지만, 숫자들은 고정이고, 연산자들의..
![]()
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 풀이 최적화에 신경 쓰지 않는다면 엄청난 시간초과를 맛볼 수 있는 문제이다. 최대한 경우의 수를 줄여서 최소한의 탐색으로 해결해야 한다. 학생들은 K개의 글자를 배우고, K개의 글자로 이루어진 단어만 읽을 수 있다. 즉 우리는 N개의 단어 중에서 K개의 글자를 골라서 주어진 N개의 단어들 중에서 최대한 많이 읽어야 한다. 문제에서는 친절하게 반드시 배워야 할 글자들을 제시해 준다..
![]()
문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 문제 풀이 전형적인 백트래킹 문제의 예시라고 할 수 있다. 백트래킹에 대해 간단히 얘기하자면 사전적 정의는 되추적 알고리즘이라고 불린다. 결과를 찾는 도중 막히면 다시 되돌아가서 결과를 찾고, 모든 노드를 탐색해서 만드는 DFS와 비슷하다. DFS와 다른 점은 노드를 탐색하기 전에 특정한 조건을 걸고 해당 조건에 부합하지 않는다면 탐색을 진행하지 않는다. 해당 문제에서 특정한 조건이 이제 인접한 두 개의..
![]()
문제 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제 풀이 문제는 정말 간단하다. 주어진 순서에서 최소한의 변경을 통해 오름차순으로 정렬하는 문제이다. 접근방법에 대해서 정말 많은 고민을 했었다. 최소한의 변경을 위해서는 기존 배열에서 최대한 고정시켜야 하는 부분을 길게 해야 한다고 이해했다. 그렇다면 고정시키는 번호를 어떻게 정할까? 문제 보기에서만 봐도 움직이는 번호들은 정해져 있는것을 보면 유추할 수 있다. 3 7 5 2 6 1 4 -> 1..
![]()
📕문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 🔎문제 설명 트리의 지름을 구하는 문제입니다. 여기서 트리의 지름이란 가장 먼 거리의 노드를 쫙 늘려서 원형태로 만들면 가장 먼 노드 2개가 양 끝점으로 지름을 이루는 형태가 될 것입니다. 해당 그림에서는 9와 12를 꼭짓점으로 쫙 늘리면 그 경로의 길이가 트리의 지름이 될 것입니다. 이렇게 우리는 각 노드들 사이의 경로의 길이를 구해서, 그 길이가 최댓값이 되는 경우를..
![]()
문제 https://www.acmicpc.net/problem/9489 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 🔎문제 설명 K의 사촌을 구하는 문제입니다. 사촌의 정의는 이제 부모가 다르지만, 할아버지, 할머니가 같은 사람들입니다. 부모를 저장하기 위해서 parent 배열을 사용했습니다. parent [idx]는 idx의 부모의 숫자가 저장되어 있습니다. 같은 부모인지 아닌지를 판단하기 위해서는 숫자의 차이를 비교하면 알 수 있습니다. 연속된 입력이 아니라면 다른 부모라는 뜻입..
![]()
문제 크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다. 이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그러고 나서 0행 1열에 숫자 2를 쓴다. 거기서부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다. -3 -2 -1 0 1 2 3 -------------------- -3 |37 36 35 34 33 32 31 -2 |38 17 16 15 14 13 30 -1 |39 18 5 4 3 12 29 0 |40 19 6 1 2 11 28 1 |41 20 7 8 9 10 27 2 |42 21 22 23 24 25 26 3 |43 44 45 46 47 48 49 이 문제는 위와 ..
