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

문제 문제 링크 풀이 트리인지 확인하기 위해서 다음 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/3085 3085번: 사탕 게임문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하www.acmicpc.net  풀이양옆으로 바꾸고 보드 전체를 검사하고 위아래로 바꾸고 보드 전체를 검사해야 한다.보드 전체를 검사할 때도 가로 줄 검사와 세로줄 ..

문제https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net 풀이연속된 수열 중 최대 값을 찾아야 하는 문제이다. 수열을 처음부터 차례로 더하면서 더한 결과가 0보다 크면 우선순위 큐에 저장을 한다. 만약 더한 결과가 0보다 작으면 그 수열 조합은 최대값이 될 수 없으므로, 그 다음 값 부터 수열을 시작해서 다시 최대값을 찾는다. 만약 우선순위 큐가 비었다면 배열에는 0보다 큰 값이 없는 것이다. 따라서 배열을 내림차순으로 정렬하면 된다.  코드c++123456789..

문제https://www.acmicpc.net/problem/1969 1969번: DNA문제 DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다. 만약에 Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine로 이루어진www.acmicpc.net 풀이 열끼리 비교해서 다를 때 Hamming Distance가 발생한다.따라서 각각의 DNA 문자열에서 열끼리 비교해서 가장 많이 나온 알..

문제https://www.acmicpc.net/problem/2217 2217번: 로프N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을www.acmicpc.net 풀이입력받은 N개의 수를 정렬하여 저장한다.최대 중량을 구해야 하므로 정렬된 값들을 골라서 최대로 만들면 된다. 정렬된 다음 인덱스 로프는 이..

문제https://www.acmicpc.net/problem/1449 1449번: 수리공 항승첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.www.acmicpc.net 풀이테이프의 수가 최소가 돼야 하니 한 개의 테이프로 겹쳐서 막을 수 있는 곳을 최대한 찾아야 한다.물을 막을 때 좌 우로 0.5만큼 간격을 필요로 하니 쓸 수 있는 테이프의 길이는 L - 1 이 된다.물이 새는 곳의 위치를 덱에 정렬하여 저장하고, 덱에 있는 처음 데이터에서 사용 가능한 테이프의 길이를 더 했을 때 나온 값 보다 이하인 것 들은 테이프 하나로 막..