본문 바로가기

Java82

[백준] 2250: 트리의 높이와 너비 - 중위 순회로 열 번호 구하기 (Java) 문제 바로가기트리를 직접 격자에 그릴 필요는 없다이진 트리를 문제의 규칙대로 격자에 배치했을 때, 너비가 가장 넓은 레벨과 그 너비를 구하는 문제다.처음에는 각 서브트리의 크기를 구한 뒤 노드의 열을 계산해야 한다고 생각했다. 하지만 배치 규칙을 살펴보면 왼쪽 서브트리의 노드는 부모보다 왼쪽에 있고, 오른쪽 서브트리의 노드는 부모보다 오른쪽에 있다.이 순서는 중위 순회의 방문 순서와 같다.왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리중위 순회로 노드를 방문하면서 1부터 열 번호를 부여하면, 별도의 격자를 만들지 않고도 각 노드가 놓일 열을 구할 수 있다.입력 순서와 노드 번호로 루트를 판단하면 안 된다입력은 각 노드의 번호, 왼쪽 자식과 오른쪽 자식을 알려 준다. 첫 번째로 입력된 노드나 번호가 1인 .. 2024. 5. 14.
[백준] 3025: 돌 던지기 - 스택으로 낙하 경로 재사용하기 (Java) 문제 바로가기매번 위에서 탐색하니 시간 초과가 발생했다돌을 지정한 열의 첫 번째 행에서 떨어뜨리고, 이동 규칙에 따라 최종 위치에 쌓은 뒤 전체 보드 상태를 출력하는 문제다.처음에는 돌을 던질 때마다 첫 번째 행부터 한 칸씩 내려가도록 구현했다. 이동 규칙 자체는 그대로 옮기면 됐지만, 같은 열로 돌을 반복해서 던질수록 이미 확인했던 긴 경로를 계속 탐색했다.보드의 높이를 R, 던지는 돌의 수를 N이라고 하면 단순 구현은 최악의 경우 O(RN)만큼 이동할 수 있다. 이동 규칙보다 이전에 지나간 경로를 어떻게 다시 사용할지가 시간 초과를 해결하는 핵심이었다.시작 열마다 이동 경로를 저장한다돌이 출발하는 열마다 별도의 스택을 만들었다.Stack[] stack = new Stack[C + 1];for (int.. 2024. 5. 14.
[백준] 1300: K번째 수 - 개수를 세어 답을 찾는 이분 탐색 (Java) 문제 바로가기배열을 직접 만들 수 없는 이유N × N 배열 A는 A[i][j] = i × j로 정의된다. 이 값을 일차원 배열에 넣어 정렬했을 때 K번째 수를 구해야 한다.처음에는 배열을 직접 만든 뒤 정렬하는 방법을 생각했다. 그러나 N은 최대 100,000이므로 원소 수가 최대 100억 개다. 배열을 저장하는 것부터 불가능하다.필요한 것은 전체 배열이 아니라 K번째 값 하나다. 그래서 특정 값 x를 기준으로 다음 질문에 답하는 방식으로 접근했다.배열 안에 x보다 작거나 같은 수가 몇 개 있는가?이 개수를 빠르게 구할 수 있다면 값의 범위를 이분 탐색해 K번째 수를 찾을 수 있다.각 행에서 x 이하인 수의 개수를 센다i번째 행은 i의 배수로 구성된다.1행: 1, 2, 3, 4, ...2행: 2, 4, .. 2024. 5. 14.
[백준] 25307: 시루의 백화점 구경 - 다중 시작점 BFS와 최단거리 BFS (Java) 문제 바로가기이동하기 전에 위험한 칸부터 구한다격자에는 빈칸, 기둥, 의자, 마네킹과 시작 위치가 있다. 시작 위치에서 도달할 수 있는 의자까지의 최소 이동 거리를 구해야 한다.이동할 때는 다음 조건을 지켜야 한다.기둥이 있는 칸으로 이동할 수 없다.마네킹과의 맨해튼 거리가 K 이하인 칸을 사용할 수 없다.상하좌우로 한 칸 이동할 때마다 거리 1이 증가한다.출발 지점은 위험 범위에 포함돼도 출발할 수 있다.바로 시작점에서 BFS를 하면 이웃 칸마다 주변 마네킹과의 거리를 다시 검사해야 한다. 마네킹이 많으면 같은 거리 계산을 반복하게 된다.나는 문제를 두 단계로 나눴다.1단계: 모든 마네킹에서 동시에 BFS → 위험한 칸을 미리 표시2단계: 시작 위치에서 BFS → 안전한 칸만 지나.. 2024. 5. 14.
[백준] 28703: Double It - 최소 힙으로 최댓값과 최솟값의 차이 줄이기 (Java) 문제 바로가기두 배로 만들 수만 있는 수들의 범위를 줄인다배열에서 수 하나를 골라 2를 곱하는 연산을 원하는 만큼 수행할 수 있다. 연산 과정에서 만들 수 있는 배열 중 최댓값과 최솟값의 차이가 가장 작은 경우를 구해야 한다.각 수 a가 가질 수 있는 값은 다음과 같다.a, 2a, 4a, 8a, ...값을 줄이는 연산은 없고 두 배로 키울 수만 있다.처음에는 어떤 수를 몇 번씩 두 배로 만들어야 하는지 모든 조합을 생각할 수 있다. 하지만 최댓값과 최솟값의 차이를 줄이려면 현재 최솟값이 아닌 수를 먼저 키울 이유가 없다.현재 최솟값을 그대로 둔 채 다른 값을 키우면 최솟값은 바뀌지 않는다. 최댓값은 유지되거나 더 커지므로 현재 범위는 줄어들지 않는다.따라서 매 단계에서 가장 작은 값을 꺼내 두 배로 만드.. 2024. 5. 14.
[백준] 11562: 백양로 브레이크 - 방향별 비용과 플로이드 워셜 (Java) 문제 바로가기도로를 바꾸는 횟수를 경로 비용으로 본다여러 건물 사이에 일방통행 또는 양방향 도로가 있다. 출발지에서 목적지까지 이동하려면 일방통행 도로를 몇 개나 양방향으로 바꿔야 하는지 최솟값을 구해야 한다.질의마다 출발지와 목적지가 달라지므로 모든 건물 쌍에 대한 최소 변경 횟수를 미리 계산할 수 있다.이 문제에서 중요한 것은 이동 거리나 지나가는 도로 수가 아니다. 경로를 따라갈 때 원래 허용되지 않은 방향으로 지나야 하는 도로의 개수가 비용이다.원래 갈 수 있는 방향은 비용 0일방통행 도로의 역방향은 비용 1양방향 도로는 어느 방향으로 가도 비용 0이 비용으로 그래프를 만들면 “몇 개의 도로를 양방향으로 바꿔야 하는가”를 최단 경로 문제로 바꿀 수 있다.같은 도로도 방향에 따라 비용이 다르다입력 .. 2024. 5. 14.
[백준] 13325: 이진 트리 - 후위 순회로 루트와 리프 사이 거리 맞추기 (Java) 문제 바로가기모든 루트에서 리프까지의 거리를 같게 만든다포화 이진 트리의 각 간선에 가중치가 있다. 간선 가중치를 증가시켜 루트에서 모든 리프까지의 거리를 같게 만들고, 변경한 뒤 전체 간선 가중치의 합을 최소화해야 한다.가중치는 줄일 수 없고 늘릴 수만 있다. 따라서 한 노드의 왼쪽과 오른쪽 경로 길이가 다르면 긴 쪽을 줄이는 것이 아니라 짧은 쪽을 긴 쪽에 맞춰야 한다.왼쪽 경로 길이 = 7오른쪽 경로 길이 = 10최소 증가량 = 10 - 7 = 3맞춘 뒤 길이 = 10이 판단은 자식 서브트리 안의 경로가 먼저 같은 길이로 정리돼 있어야 가능하다. 그래서 리프부터 루트 방향으로 결과를 올리는 후위 순회를 사용했다.간선 가중치를 자식 노드에 저장한다문제에서는 간선에 가중치가 있지만, 배열에서는 해당 .. 2024. 5. 14.
[백준] 1613: 역사 - 플로이드 워셜로 사건의 전후 관계 구하기 (Java) 문제 바로가기직접 주어진 관계만으로는 답할 수 없다여러 사건의 전후 관계가 주어지고, 두 사건 중 무엇이 먼저 일어났는지 판단해야 한다.입력으로 사건 a가 사건 b보다 먼저 일어났다는 정보가 주어지면 다음과 같이 저장할 수 있다.table[a][b] = true하지만 질의에는 입력에서 직접 연결되지 않은 사건도 나온다.사건 1 → 사건 2사건 2 → 사건 3입력에는 1 → 3이 없더라도 사건 1은 사건 3보다 먼저 일어났다. 직접 관계만 확인하면 이 질의에 0을 출력하게 된다.처음에는 입력받은 관계만 이차원 배열에 표시하면 된다고 생각할 수 있다. 실제로 필요한 것은 한 단계를 건너 이어지는 모든 간접 관계까지 포함한 도달 가능 여부다.그래서 플로이드 워셜의 반복 구조를 사용해 관계의 전이 폐쇄를 구했다.. 2024. 5. 14.
[백준] 2011: 암호코드 - 한 자리와 두 자리 해석을 더하는 DP (Java) 문제 바로가기숫자를 어디에서 나눌지가 경우의 수를 만든다알파벳 A부터 Z까지를 1부터 26에 대응시킨다. 숫자 문자열이 주어졌을 때 이를 알파벳으로 해석하는 방법의 수를 구해야 한다.예를 들어 121은 다음 세 가지로 해석할 수 있다.1 / 2 / 1 → A B A12 / 1 → L A1 / 21 → A U각 위치에서 마지막 숫자 한 자리를 독립된 문자로 볼 수도 있고, 마지막 두 자리를 하나의 문자로 볼 수도 있다.처음에는 0이 나올 때마다 별도 분기를 만들어 처리했다. 하지만 상태를 “앞에서부터 i자리까지 해석하는 방법의 수”로 정의하면 한 자리와 두 자리 조건을 독립적으로 검사해 같은 점화식으로 처리할 수 있다.dp는 앞에서부터 해석한 경우의 수다다음과 같이 상태를 정의했다.dp[i.. 2024. 5. 14.
[자바] Stream API - 생성, 중간 연산, 최종 연산으로 데이터 처리하기 반복문을 데이터 처리 단계로 바꾸기Java 8부터 Stream API를 사용해 컬렉션과 배열의 데이터를 선언적인 파이프라인으로 처리할 수 있다.반복문에서는 데이터를 어떻게 순회할지 직접 작성한다.List result = new ArrayList();for (String name : names) { if (name.length() >= 4) { result.add(name.toUpperCase()); }}Collections.sort(result);Stream API에서는 어떤 조건으로 고르고, 어떻게 바꾸고, 어떤 결과로 만들지를 연결한다.List result = names.stream() .filter(name -> name.length() >= 4) ... 2024. 5. 14.

티스토리툴바