WASD BLOG

문제들(링크) 영어로 된 문제 세트들입니다. ICPC 같은 국제대회에선 거의 모든 문제가 영어로 출제되기에 감을 익혀볼 겸 풀어보는 것도 좋은 것 같습니다. A번 - Cap Size(17659번) 0부터 1000 사이의 모자 크기를 주고, 주인공에게 딱 맞거나 맞을 것 같은 모자의 개수를 찾는 문제입니다. 모자의 크기와 숫자가 주어지는데, 의미는 다음과 같습니다. 숫자가 1 -> 주인공의 머리가 그 모자보다 크다. 숫자가 0 -> 딱 맞는 모자이다.(단, 딱 맞는 모자는 이 모자밖에 없습니다.) 숫자가 -1 -> 주인공의 머리가 그 모자보다 작다. capSize[1001] 의 배열을 선언하고 1과 -1 사이의 모자 개수를 세주면 됩니다. 단, 논리적으로 말이 안되는 입력이면 "Inconsistent feedback" 을 출력해야 하는데,  예외 상황이 좀 많습니다. 1. 숫자 0이 각각 다른 모자에 주어질 때 -> 딱 맞는 모자는 하나 뿐 2. 숫자가 이미 주어졌는데 다른 숫자가 또 주어질 때 3. 숫자 0이 주어진 모자보다 큰 모자가 1을 가질 때 4. 숫자 0이 주어진 모자보다 작은 모자가 -1을 가질 때 5. -1이 1 보다 앞에 올 때 6. 같은 모자에 같은 숫자가 계속 주어질 때 -> 맞는 입력입니다. 코드 import java.io.*; import java.util.*; public class Main { public static int N, T; public static void main (String[] argc) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader(System.in)); BufferedWrit

문제(링크) 범위가 모두 15이하이기 때문에 재귀호출을 이용한 완전 탐색으로 풀 수 있습니다. 먼저 준식이가 말한 알파벳에 맞게 전체 단어에서 sub 단어를 분리해줍니다. -> isCorrect() 시작 인덱스(s) 와 종료 인덱스(e) 가 주어지면 해당 위치만 역순으로 바꾸는 swap() 함수를 구현합니다. 그리고 재귀 함수를 돌면서 앞쪽을 바꾼 경우(front), 뒤쪽을 바꾼 경우(back)에 따라 인덱스를 조절해가며 재귀 호출해줍니다. 역순으로 바꿀 단어가 홀수인 경우엔 시작 인덱스(s)를 1 증가시켜 한번 더 재귀 호출합니다. 중복 확인은 해쉬맵을 이용합니다. import java.io.*; import java.util.*; public class Main { public static int N, sum; public static String str; public static HashMap<String, Boolean> hm = new HashMap<>(); public static int [] alpha = new int [ 26 ]; public static void main (String[] argc) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br.readLine()); sum = 0 ; st = new StringTokenizer(br.readLine()); for ( int i = 0 ; i < N ; i++) { su

문제(링크) 기본적인 유니온-파인드 알고리즘의 findI(), union() 함수는 그대로 사용하는데, 어떤 걸 노드로 정하고 언제 union 할지가 까다로운 문제였습니다. 가장 최선의 방법은 gi = n 일 때,  n번째 공항에 가장 먼저 도킹하는 것입니다. 만약 n번째 공항이 이미 도킹되었다면 n - 1, n - 1 번째도 도킹되었다면 n - 2 ... 과 같은 식으로 도킹해주면 최대값을 구할 수 있습니다. 즉, n -> n-1 -> n-2 -> n-3(Root) 이런 식으로 union을 해주면 다음 n 이라는 노드가 들어왔을 때 n의 Root 노드를 찾고, 그 노드의 -1 번째 노드와 다시 union을 해주는 식으로 풀이하면 됩니다. 만약 Root가 0 이라면 비어있는 게이트가 없는 것이므로 중단합니다. import java.io.*; public class Main { public static int G, P; public static int [] parent; public static void main (String[] argc) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader(System.in)); G = Integer.parseInt(br.readLine()); P = Integer.parseInt(br.readLine()); parent = new int [G + 1 ]; for ( int i = 0 ; i <= G ; i++) { parent[i] = i; } int cnt = 0 ; for ( int i = 0 ;

문제(링크) 유니온-파인드와 해쉬맵을 적절히 사용하여 해결할 수 있는 문제였습니다. 다른 문제들과 다르게 입력값이 문자열로 주어지므로 새로운 이름이 등장할 때마다 각각 index를 부여해 주어야 합니다. HashMap을 이용하여 index를 부여해 주는데, 이때 중복없이 사람이름이 나오면 총 N * 2명의 사람이 나올 수 있습니다. 따라서 유니온-파인드에서 사용할 parent, p_cnt 배열은 N * 2 개로 선언해 줘야 합니다. p_cnt[Root] 값은 항상 그 집합의 크기를 나타냅니다. union 할 때 기존 집합의 p_cnt[Root] 값에 붙는 집합의 p_cnt[Root]값을 더해주면 그 집합의 총 크기를 구할 수 있습니다. 코드 import java.io.*; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static int N; public static HashMap<String, Integer> hm; public static int [] parent; public static int [] p_cnt; public static BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out)); public static void main (String[] argc) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader(System.in)); StringTokenizer st; int T = Integer.parseInt(br.readL

다익스트라 알고리즘이란? 점과 점 사이의 최단 거리를 구하는 알고리즘으로 한 점에서부터 모든 점까지의 최단 거리 를 구할 수 있습니다. (물론 모든 정점에 대해 다익스트라 알고리즘을 사용하면 모든 점-> 모든점도 가능합니다.) 또한 그리디 기반의 알고리즘이기 때문에 음수 가중치 가 있다면 사용이 불가능합니다. 기본적인 아이디어는 다음과 같습니다. dist[i] 는 시작점 -> i 까지의 거리 1. 시작점을 선택한다.(현재 노드) 2. 연결된 노드(다음 노드)들에 대해 다음 작업을 수행한다. 3. dist[ 다음 노드 ] = min(dist[ 다음 노드 ] , dist[ 현재 노드 ] + 가중치[ 현재 노드 ][ 다음 노드 ]) 4. 연결된 노드 중 시작점과의 거리가 가장 가까운 노드를 현재 노드로 바꾸고 2번부터 수행한다. 위 방법을 이용해 모든 노드에 대한 탐색을 완료하면, 시작점에서 모든 노드에 대한 최단 거리가 dist[] 배열에 담기게 됩니다. 4번째 작업에서 가장 가까운 노드 를 뽑는 방법에 따라 시간 복잡도가 변하게 됩니다. 1. 우선순위 큐를 이용한 다익스트라 알고리즘 public static int Dijkstra( int start, int dst){ PriorityQueue<tuple> pq = new PriorityQueue<>( new Comparator<tuple>() { @Override public int compare(tuple tuple, tuple t1) { return tuple. second >= t1. second ? 1 : -1 ; } }); dist = new int [N + 1 ]; for ( int i = 1 ; i <= N ; i++) { dist [i