알고리즘 - Baekjoon

[백준] 2263번 : 트리의 순회 Gold1(골드1) - JAVA[자바]

[Gold I] 트리의 순회 - 2263 문제 링크 성능 요약 메모리: 62368 KB, 시간: 1280 ms 분류 분할 정복, 재귀, 트리 제출 일자 2024년 1월 23일 00:39:00 문제 설명 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력 첫째 줄에 프리오더를 출력한다. 접근 방법 1. PostOrder(LRV)는 루트 노드가 가장 오른쪽에 위치한다. -> 트리의 루트를 알 수 있다..

[백준] 4256번 : 트리 Gold2(골드2) - JAVA[자바]

[Gold II] 트리 - 4256 문제 링크 성능 요약 메모리: 37252 KB, 시간: 304 ms 분류 분할 정복, 재귀, 트리 제출 일자 2024년 1월 22일 22:45:38 문제 설명 이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다. 아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드..

[백준] 3425번 : 고스택 Gold4(골드4) - JAVA[자바]

[Gold IV] 고스택 - 3425 문제 링크 성능 요약 메모리: 39856 KB, 시간: 388 ms 분류 자료 구조, 구현, 스택 제출 일자 2024년 1월 20일 00:22:38 문제 설명 고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다. 편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 하고, 그 다음은 차례대로 두 번째 수, 세 번째 수라고 한다. NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109) POP: 스택 가장 위의 숫자를 제거한다. INV: 첫 번째 수의 부호를 바꾼다. (42 -> -42) DUP: 첫 번째 숫자를 하나 더 스택의 가장 위에 저장한다. SWP: 첫 번째 숫자와 두..

[백준] 2448번 : 별 찍기 - 11 Gold4(골드4) - JAVA[자바]

[Gold IV] 별 찍기 - 11 - 2448 문제 링크 성능 요약 메모리: 234796 KB, 시간: 476 ms 분류 재귀 제출 일자 2024년 1월 19일 00:23:23 문제 설명 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 접근 방법 1. 주어진 예시를 본다면 N이 3일 때 3층짜리 삼각형이고 맨 아랫줄은 6개의 공간이 생기는 것을 알 수 있다. 2. 출발점에서 시작하여 밑변의 길이를 2로 나누면 아래층의 시작점을 나눌 수 있다. 3. 밑변의 길이를 2로 나눈 것을 한번 더 나눠준다면(높이는 N이고 너..

[백준] 17073번 : 나무 위의 빗물 Gold5(골드5) - JAVA[자바]

[Gold V] 나무 위의 빗물 - 17073 문제 링크 성능 요약 메모리: 131348 KB, 시간: 480 ms 분류 그래프 이론, 그래프 탐색, 수학, 트리 제출 일자 2024년 1월 17일 22:07:48 문제 설명 트리란, 사이클이 없는 연결 그래프를 의미한다. 위 그림은 1번 정점을 루트로 하는 어떤 트리를 나타낸 모습이다. 사실 이 트리는 영훈이가 뒷마당에서 기르고 있는 나무이다. 어제는 비가 왔기 때문에, 트리의 1번 정점에는 W만큼의 물이 고여 있다. 1번 정점을 제외한 모든 정점에는 아직 물이 고여 있지 않은 상태이다. 이제 매초마다 모든 정점은 아래의 작업을 순서대로 반복한다. 물을 가지고 있으며, 자식 정점이 있다면 자식 정점 중 하나를 골라 물을 1 준다. 자식 정점이 여러 개라면..

[백준] 11404번 : 플로이드 Gold4(골드4) - JAVA[자바]

[Gold IV] 플로이드 - 11404 문제 링크 성능 요약 메모리: 42752 KB, 시간: 344 ms 분류 플로이드–워셜, 그래프 이론, 최단 경로 제출 일자 2024년 1월 17일 00:19:23 문제 설명 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발..

[백준] 1389번 : 케빈 베이컨의 6단계 법칙 Silver1(실버1) - JAVA[자바]

[Silver I] 케빈 베이컨의 6단계 법칙 - 1389 문제 링크 성능 요약 메모리: 11952 KB, 시간: 92 ms 분류 너비 우선 탐색, 플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로 제출 일자 2024년 1월 16일 23:22:42 문제 설명 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되..

[백준] 11403번 : 경로 찾기 Silver1(실버1) - JAVA[자바]

[Silver I] 경로 찾기 - 11403 문제 링크 성능 요약 메모리: 17864 KB, 시간: 296 ms 분류 플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로 제출 일자 2024년 1월 16일 22:37:22 문제 설명 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 총 N개의 줄에 걸쳐서 문제..