백준

문제 3584번: 가장 가까운 공통 조상 (acmicpc.net) 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 두 노드의 공통 조상을 찾는다면 부모 노드로 하나씩 거슬러 올라가며 부모가 같은 노드인지 확인하는 방법이 가장 간단합니다. 우선 부모가 같기 위해서는 루트로부터의 깊이가 같아야 합니다. 그렇기 때문에 주어진 두 노드의 깊이가 다르다면 깊이를 맞춰주는것이 우선입니다. 두 노드의 깊이가 같다면 동시에 하나씩 부모로 거슬러 올라가며 비교를 합니다..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리에서의 지름은 원과 마찬가지로 내부의 두 점 사이의 거리가 가장 먼 길이를 말합니다. 원에서 가장 먼 두 점은 원 둘레 위의 한 점에서 가장 먼 둘레위의 점입니다. 트리에서도 마찬가지로 적용할 수 있습니다. 리프노드에서 리프노드까지의 거리중 가장 먼 것을 구하면 됩니다. 한 노드에서 가장 먼 (리프)노드를 구하고, 그 노드에서 다시 가장 먼 (리프)노드까지의 거리를 ..

문제 4991번: 로봇 청소기 (acmicpc.net) 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 위의 문제를 해결하기 위한 여러가지 방법이 있습니다. 우선 각각의 더러운 곳과 로봇의 위치를 노드로하는 그래프를 구하는 것이 좋습니다. bfs 탐색으로 각각의 거리를 간선의 가중치로하는 완전 그래프를 얻을 수 있습니다. 문제에서의 방 크기가 최대 20 x 20이고 최대 노드의 개수는 11개로, 큰 비용없이 그래프를 얻을 수 있습니다. 이제 이 그래프를 활용하여 문제를 해결해봅시다. 방법1 (완전 탐색) 문제에서..

문제 2749번: 피보나치 수 3 (acmicpc.net) 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 피보나치를 풀기 위해 대표적으로 다이나믹 프로그래밍을 활용할 수 있습니다. 메모이제이션을 활용한 재귀호출로 원하는 수 까지 $O(n)$의 속도로 빠르게 구할 수 있지만 이번 문제는 n 은 최대 1,000,000,000,000,000,000로 굉장히 크기 때문에 $O(n)$ 으로는 시간초과가 발생합니다. 더 빠른 속도로 문제를 해결하기 위해 점화식을 수정해 봅시다. 우선 기본적인 피보나치 수열의 점화식을 살펴봅시다. $$ F_{n+1} = F_{n} + F_{n-1} $$ 여기서 ..

문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 bfs를 사용하는 구현문제 입니다. 알고리즘은 복잡하지 않아 구현만 잘하면 풀 수 있었네요. 문제의 오토플레이가 요구하는 4가지 기능을 구현해야 합니다. 가장 큰 블록그룹 찾기 찾은 블록그룹 삭제하기 중력 작용하기 격자 반시계로 90도 회전하기 1. 가장 큰 블록그룹 찾기 bfs탐색을 통해 같은 색상 블록의 그룹을 찾으면 되겠습니다. 무지개 블록은 주의해야 하는데, 크기가 같은 블록..

문제 13460번: 구슬 탈출 2 (acmicpc.net) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 십자 방향으로 구슬을 움직이며 도착지점까지의 최단거리를 찾는 문제입니다. 최단거리를 찾는 문제이므로 bfs 탐색을 통해 물제를 해결해 보겠습니다. 구현 문제와 살짝 짬뽕되어 문제의 조건도 많고 구현과정도 길어지지만 큰 알고리즘은 bfs 탐색으로 하나씩 정리해나가면 이해할 수 있습니다. 먼저 bfs 탐색 종료 조건부터 알아봅시다. 종료조건 1 - 구슬 ..

문제 11657번: 타임머신 (acmicpc.net) 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 1번 노드에서 시작해서 각 노드까지의 최단거리를 구하는 문제입니다. 하지만 음의 가중치를 갖는 간선이 있기 때문에 다익스트라 대신 벨만-포드 알고리즘을 활용해야 합니다. 벨만-포드 알고리즘을 이용하여 음수 사이클이 발생하는지 검사한 후 음수 사이클이 발생한다면 -1을 아니라면 각 도시의 최단 경로를 출력해주면 됩니다. 한 가지 주의해야 할 점은 ..

문제 1655번: 가운데를 말해요 (acmicpc.net) 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 간단하게 문제를 푼다면 입력을 받을 때마다 배열을 정렬하고 그 중앙값을 출력하여 해결할 수 있습니다. 하지만 입력을 받을 때마다 정렬을 하게 되고 0.1초의 시간제한 안에 해결할 수 없습니다. 그래서 필요한 방법은 최소 힙, 최대 힙 두 개를 활용하여 관리하는 것입니다. 중앙값을 기준으로 작은 값들은 최대 힙에, 큰 값들은 최소 힙에 넣습니다. 이때 중앙값이 정말 중앙값이기 위해선 ..