전체 글 (251) 썸네일형 리스트형 [백준 JAVA] 1167번: 트리의 지름 (두가지 풀이 방법 1967번과 비교) https://www.acmicpc.net/problem/1167 1167번을 풀면서 처음에는 예전에 풀었던 1967번 트리의 지름 풀이를 그대로 가져와도 되지 않을까 생각했다. 실제로 아이디어 자체는 꽤 비슷하다. 각 정점에서 아래로 내려가는 가장 긴 경로와 두 번째로 긴 경로를 구하고, 그 둘의 합으로 지름 후보를 갱신하는 방식이다. 1967번: 트리의 지름 풀이 링크https://dwshin-dev.tistory.com/257 그런데 1967에서는 잘 되던 코드가 1167에서는 바로 통하지 않았다. 처음에는 단순히 방문 배열을 안 써서 그런가 싶었고, 더 생각해보니 그 차이가 맞긴 했지만 실제로는 입력으로 주어지는 트리의 형태 자체가 달랐다. 이 글에서는 그 과정에서 어떻게 생각이 바뀌었는지, 그리.. [백준 JAVA] 1865번: 웜홀 (벨만-포드 풀이 + 플로이드 워셜 풀이) https://www.acmicpc.net/problem/1865 문제 접근문제를 처음 보면 단순한 최단 경로 문제처럼 보이지만 실제로는 음수 사이클의 존재 여부를 판별하는 문제다. 도로는 양방향으로 이동할 수 있고 시간이 양수로 흐르지만 웜홀은 단방향이며 시간을 되돌리는 효과가 있어 음수 가중치로 처리된다. 결국 어떤 지점에서 출발하든 다시 자기 자신으로 돌아왔을 때 전체 시간이 음수가 되는 경로가 존재하면 시간 여행이 가능하다고 볼 수 있고, 이 경우 정답은 YES가 된다. 풀이 방법음수 사이클이 존재하는 최단거리 문제는 다익스트라로 풀 경우 무한 사이클이 돌아 오류가 발생하기 때문에 벨만-포드나 플로이드 워셜로 풀어햐한다. 먼저 플로이드 워셜로 접근한 이유부터 정리해보면 이 문제는 특정 시작점에서 .. [백준 JAVA] 1629번: 곱셈 https://www.acmicpc.net/problem/1629 처음 보면 단순 반복문으로 B번 곱하면 될 것 같지만, B의 범위가 매우 크기 때문에 그렇게 하면 시간 초과가 발생한다.그래서 필요한 개념이 분할 정복 기반의 거듭제곱이다.핵심 아이디어는 다음과 같다.B를 절반으로 나누어 계산한다.예를 들어A¹¹ = A⁵ × A⁵ × A즉,A^B = (A^(B/2))²이 된다.여기서 B가 홀수라면 A를 한 번 더 곱해주면 된다.이 방식으로 계산하면 시간 복잡도가 O(B) → O(log B)로 줄어든다. 이 문제에서 중요한 포인트는 하나 더 있다.바로 모듈러 연산이다.(a × b) % C = ((a % C) × (b % C)) % C이 성질을 이용해서 중간 계산 값이 커지는 것을 방지해야 한다. 풀이 흐름을.. [백준 JAVA] 5639번: 이진 검색 트리 https://www.acmicpc.net/problem/5639 이진 검색 트리 문제는 처음 보면 트리를 직접 만들어야 할 것 같지만 실제로는 배열만으로 해결할 수 있는 문제다. 입력으로 주어지는 값은 트리의 전위 순회 결과이며 이를 이용해 후위 순회를 출력해야 한다. 전위 순회의 특징은 항상 첫 번째 값이 루트라는 점이다. 이 문제의 핵심은 이 성질과 이진 검색 트리의 규칙을 함께 사용하는 것이다. 이진 검색 트리는 루트보다 작은 값은 왼쪽 서브트리로 들어가고 큰 값은 오른쪽 서브트리로 들어간다. 전위 순회 배열을 보면 첫 번째 값은 루트이고 그 다음 값들 중에서 루트보다 작은 값들은 모두 왼쪽 서브트리에 해당한다. 그리고 어느 순간 루트보다 큰 값이 처음 등장하는데 그 지점부터는 모두 오른쪽 서브트.. [백준 JAVA] 2448번: 별 찍기 - 11 https://www.acmicpc.net/problem/2448 문제를 처음 보면 단순 구현처럼 보이지만 실제로는 재귀 구조를 이해해야 풀리는 문제였다.나도 처음에는 감이 잘 안 잡혀서 막히는 느낌이 있었는데 핵심은 삼각형을 어떻게 쪼개느냐였다. 이 문제는 높이 N의 큰 삼각형이 있다고 할 때, 이걸 한 번에 그리는 게 아니라 작은 삼각형 3개로 분할해서 생각해야 한다.높이 N짜리 삼각형은 다음과 같이 구성된다.위에 높이 N/2짜리 삼각형 1개아래에 높이 N/2짜리 삼각형 2개 (왼쪽, 오른쪽)즉 하나의 삼각형을 계속 절반으로 쪼개면서 그리는 구조다.이걸 재귀로 표현하면 자연스럽게 해결된다. 좌표를 어떻게 잡느냐도 중요하다.이 문제에서는 (x, y)를 삼각형의 꼭대기 좌표라고 정의한다.처음 시작은 전체.. [백준 JAVA] 1967번: 트리의 지름 https://www.acmicpc.net/problem/1967 이번 문제는 “트리의 지름”인데, 아이디어는 맞았지만 구현에서 틀린 케이스였다. 문제 접근트리의 지름은 “가장 먼 두 노드 사이의 거리”다.이걸 DFS로 풀 때 핵심 아이디어는 다음이다.각 노드에서아래로 내려가는 최대 경로 길이들을 구하고그 중 가장 긴 두 개를 더해서 지름 후보를 만든다그리고 부모에게는 “가장 긴 하나만” 반환한다.이 구조를 재귀로 구현하면 자연스럽게 트리 DP 형태가 된다. 내 풀이 아이디어나는 다음과 같은 방식으로 접근했다.maxLength(u) : u에서 시작해서 아래로 내려가는 최대 길이 반환각 노드에서 자식들을 순회하면서가장 긴 경로 (first)두 번째로 긴 경로 (second)를 구한다first + secon.. [백준 JAVA] 1504번: 특정한 최단 경로 https://www.acmicpc.net/problem/1504 처음엔 N 이 800정도여서 플로이드 워셜로 한번 풀어보았다. 800^3 = 5억 정도여서 시간초과가 예상되었지만 이정도에 시간 초과가 나나 궁금하기도 하였다. 그래프는 인접 배열로 풀이하였다. import java.io.*;import java.util.*;public class Main { static int N, E, v1, v2; static int[][] graph; static final int INF = 1_000_000; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader.. [백준 JAVA] 1043번: 거짓말 https://www.acmicpc.net/problem/1043 처음 풀이import java.io.*;import java.util.*;public class Main { static int N, M, count; static int[] truth; static int[][] graph; static List[] party; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine.. 이전 1 2 3 4 ··· 32 다음