YANGORITHM

문제 https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net 풀이 확장자만 가져오기 위해 substring 메소드를 사용한다. 확장자를 오름차순으로 정렬 후 앞에서 부터 개수를 세면 된다. 코드 java import java.util.Arrays; import java.util.Scanner; public class Main { static int N; static String[] arr; static StringBuilder sb = new StringBu..

문제 https://www.acmicpc.net/problem/1015 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 풀이 아래 그림에서 P 배열을 구하는 문제이다. A 배열을 정렬해 B 배열을 만들고, A와 B를 이용해 P배열을 구하면 된다. B 배열이 정렬돼 있으므로 B 배열에 있는 값과 A 배열에 있는 값을 비교해 P 배열에 값을 넣을 수 있다. B 배열에 있는 값을 A 배열에서 찾은 후, 찾은 A 배열의 인덱스를 그대로 몇 번째로 찾았는지 P 배열..

문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 최소 힙을 이용한다. 우선순위 큐를 이용해 최소 힙을 만들고 데이터를 추가할 때 정렬 기준을 추가한다. 정렬 기준은 다음과 같다. - 절댓값이 같으면 오름차순 - 절댓값이 다르면 절댓값 오름차순 코드 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 ..

문제 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 풀이 문제에 나와있는대로 코드를 짠다. 위에서 삭제하고 아래에 다시 붙이는 작업이 Queue의 offer와 poll과 비슷하니 Queue 를 이용해 문제를 푼다. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int N; static Queue ..

문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(conc www.acmicpc.net 풀이 스택을 이용하는 간단한 문제이다. '('일 때 스택에 push 하고 ')'일 때 스택에서 pop 한다. 스택에서 pop을 할 수 ..

문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 다익스트라 알고리즘을 이용하여 최소비용을 구한다. 노드 간의 최단거리가 갱신될 때 부모 노드를 갱신해줘서 도착점과 시작점 사이의 길을 알 수 있게 만든다. 코드 python 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 36 37 ..

문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 www.acmicpc.net 풀이 특정 정점에서 모든 정점까지의 최소 거리를 구하는 문제이므로, 다익스트라 알고리즘을 이용하는 문제이다. https://..

문제 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 모든 간선의 비용이 동일하기 때문에 bfs 탐색을 통해 최단 거리를 찾을 수 있다. 시작점 x에서부터 bfs 탐색을 통해 모든 도시까지의 최단 거리를 구한 후에 k 값과 비교하여 답을 구한다. 코드 java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..

문제 https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 풀이 0이 연속되는 부분의 개수와 1이 연속되는 부분의 개수를 구해서 비교를 한다. 코드 python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 s = input() zero = 0 one = 0 state = s[0] if state == '0': zero += 1 else: one += 1 for i in s: if i != state: state = i if ..

문제 https://www.acmicpc.net/problem/1793 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. www.acmicpc.net 풀이 사용할 수 있는 타일이 2 * 1(가로), 2 * 1 (세로), 2 * 2 세 종류이다. 왼쪽부터 차례대록 타일을 채운다고 생각하면서 점화식을 생각해본다. 길이가 i인 타일을 채워야 하고, i-1까지 타일이 채워져 있다면 2 * 1(세로)를 사용하면 된다. 길이가 i인 타일을 채워야 하고, i-2까지 타일이 채워져 있다면 2*1(가로) 두개를 사용하는 방법과 2*2 타일을 사용하는 방법이 있다. 따라서 다음과 같은 점화식을 만들 수 있다. a[i]..