Coding Test

# 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net # 풀이 과정 한 칸씩 이동하면서 '루피'를 최소로 잃어야 한다 static class Rupee implements Comparable { //좌표 int y; int x; //루피의 합 int count; Rupee(int y, int x, int count) { this.y = y; this.x = x; this.count = count; } @Override pu..

# 문제 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net # 풀이과정 for(int i = 1; i 1) { int a = que.poll(); int b = que.peek(); if(parent[a] != parent[b]) { System.out.println("NO"); return; } } System.out.println("YES"); 큐를 생성하여 여행 계획으로 주어지는 도시를 순서대로 넣어준다 큐에 넣은 도시들 중 두 개씩 연결되..

# 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net # 풀이 과정 1. 같은 집합인데도 다른 집합으로 인식하는 틀린 코드 더보기 왜 그랬을까! static int find(int x) { if(arr[x] == x) return x; return find(arr[x]); } static void union(int a, int b) { //내가 속한 집합의 대표 노드를 먼저 찾아야 한다 a = find(..

# 문제 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net # 풀이 과정 두 자연수의 곱 = 최소 공배수 * 최대 공약수 MOD 연산으로 최대 공약수를 구해서 최소 공배수를 구한다 static long euclidean(long a, long b) { //1.두 수의 나머지 값을 구한다 long rest = a % b; //2. 나머지 값이 0이 될 때까지 아래의 연산을 반복한다 while(rest != 0) { long sa..

# 문제 https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net # 풀이 과정 유클리드 호제법으로 최대 공약수를 구했다(MOD 연산) static long euclidean(long a, long b) { //1.두 수의 나머지 값을 구한다 long rest = a % b; //2. 나머지 값이 0이 될 때까지 아래의 연산을 반복한다 while(rest != 0) { long save = rest; rest = b % rest; ..

# 문제 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 # 풀이 과정 ArrayList adj = new ArrayList(); adj.add(new ArrayList()); check = new boolean[N+1]; for(int i = 0; i < N; i++) { adj.add(new ArrayList()); } 인접 리스트의 인덱스 번호와 정점 번호를 일치시키..

# 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net # 풀이 과정 이진 탐색(Binary Search)을 사용하여 풀어봤다 static int binarySearch(int key, int left, int right) { int mid; while(left key) right = mid-1; else left = mid+1; } return 0; } while문으로 탐색할 수 있을 때까지(..

# 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net # 풀이 과정 DFS 탐색한 결과와 BFS 탐색한 결과를 각각 출력해야 되기 때문에 DFS 먼저 실행한다 1. DFS static void dfs(int n) { //잊지 말고 방문 처리 check[n] = true; sb.append(n + " "); for(int i = 1; i