YANGORITHM

문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. www.acmicpc.net 풀이 결정 문제로 바꾸어 문제를 해결한다. 이분 탐색으로 길이를 찾아가면서, 찾은 길이를 간격으로 C 개의 공유기를 설치할 수 있는지 확인한다. 코드 c++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 3..

문제 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 서브트리를 이용해 문제를 해결한다. 서브트리로 더 이상 나눌 수 없을 때 까지 나누면, 그 때 리프 노드가 된다. 리프 노드는 자식이 더 없으므로 dfs 탐색을 통해서 더 이상 탐색이 불가능 할 때 리프노드로 규정한다. 위 그림에서 3번 노드에서 더 이상 dfs 탐색을 못하므로 3번 노드는 리프 1개가 된다. 4번 노드도 마찬가지로 리프 1개가 된다. 3번과 4번의 부모인 1번 노..

문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 재귀탐색을 통해 모든 경우의 암호를 만든다. 하나의 암호를 만들었을 때 모음과 자음의 수를 세서 문제 조건에 맞는지 확인한다. 정렬된 문자열을 얻기위해 처음 입력을 받는 배열을 정렬해서 재귀 탐색을 시작한다. 코드 java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..

문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 결정 문제로 바꿔 랜선이 몇 센치미터 이상부터 문제 결과를 만족하는지 찾는다. 랜선의 최대 길이가 int 값의 최대 값이므로 long 변수를 사용해서 중간 계산을 진행한다. 코드 java import java.util.Scanner; public class Main { static int k, n; static int[] a; public static voi..

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 풀이 1, 2, 3을 이용해서 더한 후 N을 구하는 문제이다. 마지막에 더해지는 숫자에 따라서 N을 구하는 방법을 알 수..

문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net 풀이 위상 정렬을 이용하면 간단히 풀 수 있는 문제이다. https://terms.naver.com/entry.nhn?docId=3579618&cid=59086&categoryId=59093 위상 정렬 알고리즘 우리가 일상생활에서 하는 모든 행동은 순서가 정해져있다. 외출을 하려고 신발을 신기 위해선 먼저 양말 먼저 신어..

문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 각 노드의 부모를 저장하기 위해 p[] 배열을 만들어서 여기에 저장한다. 트리도 그래프이므로 그래프의 탐색을 이용해서 노드의 부모를 찾는 과정을 가진다. 문제에서 루트 노드가 1이므로 1부터 그래프 탐색을 시작하면 1과 연결된 다음에 방문할 노드들은 부모가 1이 된다. 따라서 다음에 방문할 노드의 부모 노드는 현재 노드가 된다. 코드 c++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 숫자를 찾을 때 이분 탐색을 이용해 빠르게 찾을 수 있다. 같은 숫자를 여러 개 찾아야하는데 이분 탐색을 이용해 상한선과 하한선을 찾는다. 코드 java import java.util.Arrays; import java.util.Scanner; public class Main { static int N, M; static int[] a, b; stati..

문제 https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 풀이 A 배열에서 한 개씩 B 배열에 대해 탐색을 진행하면서 작은 값을 찾아야 한다. 이 때 2중 for문을 이용해서 A의 한 원소에 대해 B의 원소 전부를 탐색하면 시간초과가 발생한다. 따라서 B를 정렬 후 A 보다 작은 값의 개수를 이분 탐색으로 찾으면 된다. 일반적인 이분 탐색으로는 A 보다 작은 값의 개수를 찾을 수 없으므로 이분 탐..

문제 https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 풀이 각 점에서 다른 점으로 가는 가장 가까운 거리는 왼쪽 점으로 가는 것 또는 오른쪽 점으로 가는 거리다. 색깔 별로 점들을 정렬한 후 거리를 계산한다. 코드 import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Main ..