YANGORITHM

문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 큐를 이용해 문제를 해결할 수 있다. 큐에서 k - 1 번 데이터를 front에서 pop하고 rear에 넣어준다. 이것이 원을 이루면서 앉아있는 것과 같아진다. 그 다음 k 번째에 데이터를 pop한다. 이를 q가 빌 때까지 반복하고 pop한 숫자들을 차례대로 저장해 출력한다. 코드 python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 from collections import deque def solution(n, k): answer = [] q = de..

문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 지도에서 표시된 섬마다 다르게 숫자로 표시한다. 이를 위해 BFS로 탐색하면서 섬마다 값을 부여한다. 각 섬에서 다른 섬으로 연결할 수 있는 에지가 있는지 확인해서 에지 리스트를 만든다. 이를 위해 섬 마다 모든 점에서 상하좌우로 다리를 만들어본다. 만든 에지리스트로 크루스칼 알고리즘을 적용해 최소 신장 트리를 만든다. 코드 java import java.io.Bu..

문제 문제 링크 풀이 트리인지 확인하기 위해서 다음 2가지를 검사한다. Root가 1개인지 검사한다. V로 들어오는 간선이 2개 이상인지 확인한다. 트리는 Root가 1개이어야한다. 또한 V로 들어오는 간선도 1개이어야 한다. 2개 이상이면 사이클이 발생할 수도 있다. 문제에서는 트리의 노드 번호를 특정할 수 없으므로 배열을 사용할 수 없다. 그래서 Set을 이용해 문제를 해결했다. 코드 java import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); St..

문제 문제 링크 풀이 해쉬맵을 이용해 문제를 해결했다. 인덱스를 키 값으로, 입력 받는 포켓몬 이름을 데이터 값으로 가지는 해시맵을 만든다. 다음과 같은 해시맵을 하나 만든다. (1 : Pikachu) 이어서 인덱스를 포켓몬 이름으로, 데이터 값을 인덱스 값을 가지는 해시맵을 만든다. 다음과 같은 해시맵을 또 만든다. (Pickachu : 1) 두 개의 해시맵을 이용해 간단히 풀 수 잇다. 해시를 사용하므로 시간복잡도는 O(1) 이다. 코드 java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; pub..

문제 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 풀이 투 포인터를 이용한다. l 인덱스 값을 증가시키면 이전 l 인덱스에 있던 값을 지우고 r 인덱스까지의 합을 구한다. 그 후 최대값을 비교하여 답을 구해간다. 수열에 음수도 나올 수 있으므로 처음에 최소값을 설정할 때 주의한다. 코드 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 ..

문제 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 투 포인터를 이용한다. r 인덱스를 늘리면서 합을 구하고 m 값과 같은지 확인한다. l 인덱스가 증가할 때는 이전 l 인덱스에 있던 값을 빼준다. 코드 java import java.util.Scanner; public class Main { static int n, m; static int[] a; public static void main(S..

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