SH

BOJ Link https://www.acmicpc.net/problem/1036  풀이 과정정렬 + 트리(트라이) 문제다. 일반적인 구현이라면 길이를 기준으로 내림차순 정렬하고, insert 동작 이후 마지막 노드가 리프노드가 아닐 시 No임을 체크할 수 있다. (이는 문제에서 일관성이 없는 전화번호 목록이라고 표현한다.) 나는 정렬을 사용하지 않았다. 그러려면, 다음과 같은 케이스를 고려해야 한다. 12123 이는 insert시 12의 경우 마지막 수가 리프 노드(123의 insert를 수행하기 전 이므로) 이며123의 경우 또한, 마지막 수가 리프 노드가 된다. 그러므로 이를 고려하여, 123의 insert 도중 노드가 이미 존재했고, 리프 노드라면(isEnd, 위의 경우 2번 노드)No 로 체크한..

BOJ Link https://www.acmicpc.net/problem/1036 풀이 과정그리디 + 큰 수 연산 + 구현 문제이다.정답률이 시사하듯이 어렵고 엣지케이스도 많은 문제였다. 1. 다루는 수의 범위가 매우 크다. 때문에 이는 i번째 자리수를 i번째 인덱스로 치환하는 배열로 구현한다. 2. 조합으로 K를 구성하며 브루트포스할 경우, 최대 O(36!*50*50)이다. 그리디하게 접근해야한다.어떤 알파벳을 Z로 바꿨을 때의 기대 값을 저장하여 기대 값이 가장 높은 K개의 알파벳을 구성한다. 3. 모든 문자열을 탐색하며 선택한 K개의 알파벳들을 Z로 치환한 후, 36진수로 변환하여 출력한다. 또한, 답을 도출할 땐 문자열의 앞이 36이상일 경우를 고려해야 하지만, 기대 값이 높은 알파벳을 K개 구성..

BOJ Link https://www.acmicpc.net/problem/1082  풀이 과정각 방 숫자별로 비용이 다를 때, 가지고 있는 돈으로 가장 큰 숫자를 구성하는  그리디 + DP문제다.해당 풀이에서는 DP를 사용하지 않았다. 단순히 그리디하게 생각하면, 앞자리는 가능한 가장 큰 수여야 한다. 그러나, 반례가 있다.2번의 비용이 10, 1번의 비용이 5라면, 10원으로 2혹은 11을 구성할 수 있다. 그러므로 마냥 앞자리가 가장 큰 수여선 안된다. 이를 해결하기 위해 now = (현재 남은돈 - i번째 숫자의 비용) / 숫자 비용의 최소값 으로 놓았다.이는 곧 최소값만 사용했을 때,  i번째 숫자를 앞에 놓는다면 그 뒤로 now길이의 숫자를 놓을수 있다는 것을 의미한다.이것으로 같은 길이의 숫자..

BOJ Link https://www.acmicpc.net/problem/1786  풀이 과정스탠다드한 KMP 문제이다.  문제 또한 KMP의 기본 개념을 그대로 설명하고 있다. 헤맨 부분반례 하나를 고려하지 못해서 오답이 있었다. input :ABABAABA answer :21 3 wrong answer :11 해당 문자열에서 ABA라는 문자열은 idx 0~2에 위치한다.탐색 이후 idx 3번부터 재탐색을 하게 되면, idx 2~4에 위치한 케이스를 고려하지 못한다. 이후 수정하여 정답을 받았다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;class Main { publi..

BOJ Link https://www.acmicpc.net/problem/1005  풀이 과정위상 정렬 + DP 문제이다.스타크래프트 처럼 건물들 사이에 선행 건물이 존재할 때, 건물 G를 짓기 위한 총 비용을 구하는 문제이다. (동시에 지을 수 있다.) 선행 건물이 존재한다. 건설순서는 모든 건물이 건설 가능하도록 주어진다. 라는 조건은 이 조건은 방향그래프이며, 사이클이 없다는 것을 보장한다.(A->B, B->A 형태의 사이클이라면, 건물이 건설 불가능하게 주어진 것이다.)이로 인해 위상 정렬을 수행할 수 있다. 건물 A를 짓는데 필요한 총 비용은 DP로 구현한다.단순히 생각하면, A의 비용 = 선행 건물을 짓는 최소 비용 + A 건물의 비용 이다. A를 짓는데 B와 C가 필요하다 가정하면,dp[a]..

BOJ Link https://www.acmicpc.net/problem/12851  풀이 과정N에서 N-1, N+1, N*2 각각의 경우를 탐색하여, K에 도달하는 최소 depth와, 경우의 수를 출력하는 완탐 + 그래프 탐색 문제이다.  방문 체크 배열에 depth를 기록한다. 탐색 순서에 따라 똑같은 값에 도달하더라도, depth가 더 작은 경우가 있을 수 있다. 이를 체크하기 위함이다. (또한 N+1 => N-1 => N+1 => N-1 무한 루프를 막는다.) 똑같은 값에 도달할 때, depth가 같더라도 탐색한다. 정답에서 최소 depth와 함께 "경우의 수"도 요구하기 때문이다. depth만 요구한다면, 방문 체크 배열보다 depth가 작을때만 탐색해도 된다. 굳이 최적화 하자면, 같은 값이고..

BOJ Link https://www.acmicpc.net/problem/1495  풀이 과정0이상 M이하의 범위를 지키면서,처음 값 S에서 V[0]...V[N-1]을 가감하며 탐색할 수 있는 지 찾는 문제이다. 할 수 있는 경우가 여러개라면 최대값을 출력한다. 현재 dp[i][j]를 P비용으로 연주하려면, dp[i-1][j-P]나 dp[i-1][j+p]가 true면 된다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;class Main { public static void ..

BOJ Link https://www.acmicpc.net/problem/1991  풀이 과정BST의 순회법 3가지를 구현하는 문제다. left, right가 자식노드의 레퍼런스를 가리키는 일반적인 방법에서 조금 바꿔서 인덱스 기반으로 풀었다. 입력이 노드의 순서대로 주어지지 않기 때문에 이점만 유의하면 된다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;class Main { static Node[] tree; static StringBuilder sb = new St..

BOJ Link https://www.acmicpc.net/problem/1497  풀이 과정일반적인 부분집합 + 브루트포스로 풀 수 있다. 문제에서 N  또한, 다음과 같은 최적화를 할 수 있다. 입력 범위가 작아서 나는 쓰지 않았다. 1. A기타가 B기타가 칠 수 있는 곡을 모두 포함한다면 (B가 A의 부분집합이면), B기타를 탐색에 고려할 필요가 없다. 2. 백트래킹비트마스킹을 쓸 때, 탐색 중인 기타와 OR 연산을 해도 bitCount(= 연주할 수 있는 곡 수) 가 같다면 제외한다. (1번과 같은 논리이다. 현재까지 탐색한 기타들이 A가 되고, 탐색 중인 기타가 B가 된다.) (마찬가지로, 현재까지 어떤 기타들을 포함했는지 기록하지 않아도 된다. 어차피 B(부분집합)가 되면서 알아서 제외한다.)..

BOJ Link https://www.acmicpc.net/problem/17471  풀이 과정dfs/bfs 두번 + 조합 문제이다.  문제에선 요구하진 않지만, 비트마스킹으로 풀이했다. N  1. A선거구에 포함될 구역을 조합으로 뽑는다. -> bit의 dep번째 자리에 0 또는 1을 쌓아가며 뽑는다.pick(bit, dep + 1);pick(bit | (1  2. A선거구에 포함되지 않은 B선거구 구역을 XOR 연산으로 뽑는다.int a = bfs(bit);int b = bfs(compbit ^ bit); 여기서 combit는 왼쪽 기준으로 2~N+1번째 자리가 모두 1인 비트이다.(1번째 비트는 padding 을 위해 비웠는데 더 불편했다..)for (int i = 1; i  3. 비트 마스킹한 변..