전체 글
백준 1967 - 트리의지름
1. 유형 트리 2. 문제 분석 2-1. 문제 설명 트리에서 가장 긴 두 점은 리프 노드끼리의 거리임을 직관적으로 알 수 있습니다. 따라서 리프노드에서 재귀의 리턴 값을 사용해서 문제를 풀어야 합니다. [그림 1]에서 지름은 9->5->3->6->12입니다. 저 케이스를 예시로 들어봅시다. DP [k] = n => 노드 k를 기준으로 한 가장 긴 지름은 n이다.라고 정의 우선은 리프 노드까지 dfs를 진행합니다. 9에서 15를 리턴하고, 10에서 4를 리턴합니다. 노드 5에서는 15와 4중 더 긴 큰 값을 리턴합니다. 노드 3 에서는 왼쪽에서 오는 가장 큰 값 26, 오른쪽에서 오는 가장 큰 값 19를 DP [3]에 저장 2-2. 주의할 점 자식 노드가 3개 이상일 수 있습니다. 따라서 둘 중에 최댓값이..
백준 1613 - 역사
[문제 바로가기] 1. 유형 프롤이드 와샬 2. 문제 분석 2-1. 해설 플로이드 와샬을 쓰는 문제였습니다. N=400이기 때문에, 3중 for문을 돌려도 시간안에 들어옵니다. 플로이드를 사용해서 출발점에서 도착지점 까지의 최단거리를 구해서 저장합니다. 맵 초기화 알고리즘 적용 후 S개의 인풋값이 (1,5) (2,4) (3,1)이 주어집니다. (1,5)는 무한대 이니깐 0출력 (2,4)는 1이니깐 관계를 알 수 있음, -1 출력 (3,1)는 무한대이지만 (1,3)은 관계를 알 수 있음. 1 출력 2-2. 설계 2차원 배열을 INF로 초기화 -> 플로이드 와샬 -> 인풋 쌍을 보면서 출력 3. 코드 import java.io.*; import java.util.*; //https://www.acmicpc...
백준 17255 - N으로 만들기
[문제 바로가기] 1. 유형 DFS 2. 문제 분석 2-1. 설계 시작 위치를 탐색 -> 함수 시작 -> 현 위치에서 왼쪽, 오른쪽으로 재귀 진행 -> 총 N-1개를 탐색하면 종료 2-2. 설명 투포인터를 사용했습니다. [그림1]은 "521"중 2를 시작위치로 설정했을 때의 경우 입니다. 왼쪽, 오른쪽에 포인터를 두고 path변수에 만든 루트를 저장합니다. 그리고 Set 컬렉션에서 중복을 제외해주면 됩니다. 3. 코드 import java.io.*; import java.util.*; public class Main { static char[] arr; static Set set; public static void main(String[] args) throws IOException { BufferedR..
백준 9548 - 무제
[문제 바로가기] 1. 유형 문자열 2. 문제 접근 더 좋은 풀이법이 있는 것 같지만, 생각이 안나서 StringBuffer를 사용했습니다. 3. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int T = stoi(st.nextToken()); while (T-- > 0) { st = new StringT..
백준 17141 - 연구소2
[문제 바로가기] 1. 유형 BFS, 조합 2. 문제 접근 2-1. 설계 일단 설계부터 해봅시다. 위치의 조합 찾기 문제에서 2는 바이러스를 퍼트릴 수 있는 곳 입니다. 따라서 List에 2의 위치를 모두 넣어주고, 그 중에서 M개를 선택합니다. List에 위치를 넣는 방법은 (r,c)를 넣어줘도 되고, 저는 인덱스 값만 넣어줬습니다. 예를들어 N=3이라면, 아래 그림처럼 나올 것이고. 인덱스8은 의 좌표는 (8/N, 8%N)이 됩니다. 0 1 2 3 4 5 6 7 8 bfs로 퍼뜨리기 bfs구현에서 특별한것은 없습니다. 총 탐색한 칸수를 카운트해주고, bfs가 끝나고 카운트해준 값이 바이러스를 퍼뜨릴 칸수와 일치하면 정답을 갱신합니다. M=1일때, 아래 인풋값을 가정합시다. 바이러스를 유출해야하는 칸수..
백준 1622 - 공통 순열
[문제 바로가기] 1. 유형 정렬 2. 문제 분석 문자열 최대 길이가 1000입니다. 따라서 딕셔너리를 만들어서 두 문자열을 비교해줬습니다. Map {문자, 문자가 나온 횟수} 예를들어 "abccc"라는 문자가 있다면, {a=1,b=1, c=3} 형식으로 됩니다. 두 문자열을 딕셔너리로 만들고, 공통 요소가 있을 경우 더 더 낮은 횟수만큼 정답에 넣어주면 됩니다. 아마도 이 문제의 가장 어려운 점은 EOF입니다. Scanner를 사용해서, 아래처럼 다음 문자열이 존재하는지를 판단했습니다. Scanner sc = new Scanner(System.in); while(sc.hasNextLine()) { // } BuffredReader를 이용해 보려고 했지만 계속 런탐에러가 나와서 포기...왜 안될까요.....
백준 1937 - 욕심쟁이 판다
[문제 바로가기] 1. 유형 DFS, 메모리제이션 2. 문제 접근 처음으로 든 풀이법은 배열을 완전탐색하면서 DFS를 한번씩 사용하는 것 입니다. 하지만 이러면 500^4의 시간이 걸리기 때문에 시간초과가 날 것입니다. 따라서 이 문제에선 DFS+DP를 써야됩니다. 9 10 1 11 위와 같은 원본 테이블이 있습니다. 최대 길이는 1->9->10->11으로 4가 나옵니다. DP[r][c] = val val은 현재 좌표에서 최대 길이를 의미. DP테이블을 구해봅시다. 그림1은 DP테이블 초기화. (0,0)에서 DFS를 한번 돌립니다. 그럼 그림2와 같은 테이블이 될것입니다. 그 다음 (1,0)에서도 DFS를 돌려야 할까요? 아닙니다. (1,0)에서 4방향을 탐색합니다. 원본배열에서 1 < 9 이니깐, 본인..
leetcode - 350. Intersection of Two Arrays II
[문제 바로가기] 1. 유형 구현, 정렬 2. 문제 분석 두 배열의 교집합을 구하는 문제였습니다. 요즘 Stream을 공부 중인데, for을 최소한으로 사용을 연습을 위해 풀어봤습니다. 3. 코드 static public int[] solution(int[] nums1, int[] nums2) { List list = new ArrayList(); Map n = new HashMap(); Map m = new HashMap(); Arrays.stream(nums1).forEach(x -> n.put(x, n.getOrDefault(x, 0) + 1)); Arrays.stream(nums2).forEach(x -> m.put(x, m.getOrDefault(x, 0) + 1)); for (int k : n..
백준 2146 - 다리 만들기
[문제 바로가기] 1. 유형 BFS 2. 문제 접근 2-1. 설계 2-2. 해설 BFS를 사용해서 섬을 구합니다. 섬의 개수를 구하는 문제는 아래와 같습니다. [문제 바로가기 - 백준, 섬의 개수 - 4963] 섬의 개수를 구했으면, 섬에서 다른 섬까지의 최단거릴 구하기 위해 다시 BFS를 돌립니다. bfs를 돌릴 때, 그림 1처럼 조건을 정해줘야 합니다. 맵을 이탈할 경우 예외처리, 그리고 다름 섬을 만났으면 그 자리에서 거리를 리턴해주면 됩니다. 3. 코드 import java.io.*; import java.util.*; public class boj_2146_다리만들기 { static int map[][], N, d[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -..
백준 19542 - 전단지 돌리기
[문제 바로가기] 1. 유형 깊이 우선 탐색, 트리 2. 문제 접근 2-1. 해설 우선 저는 현재 위치와 leaf노드까지의 깊이를 탐색했습니다. 그림 1처럼 만드는 것은 재귀를 사용해서 return값에 +1을 해주면 됩니다. 하지만 저기서도 문제가 있습니다. 2,3,4 노드 같은 여러 가지로 뻗어나가는 부분이 까다롭습니다. 그래서 그림2 처럼 여러 가지로 뻗어나가는 경우는 리턴 값 중 최댓값을 노드의 깊이로 선택하면 됩니다. 그림 1처럼 노드의 최대 깊이를 탐색했으면 D보다 큰 녀석들의 갯수를 카운트해주고, 왕복이니깐 *2를 해주면 정답이 나옵니다. 2-2. 설계 3. 코드 import java.io.*; import java.util.*; public class Main { static boolean ..