이번에는 LCP 배열에 대해 알아보자! LCP 배열을 이해하기 위해서는 이전에 쓴 글인 접미사 배열을 우선적으로 이해해야한다. 2023.03.27 - [Algorithm] - [Algorithm] 맨버-마이어스 알고리즘(Suffix Array) [Algorithm] 맨버-마이어스 알고리즘(Suffix Array) 접미사 배열이란 특정 문자열에 대한 접미사들을 모두 나열한 뒤, 사전 순으로 정렬을 진행한 배열을 의미한다. 일반적으로 접미사 배열을 만드는 방법은 다음과 같다. 문자열에 대해 모든 접미 codable.tistory.com 위의 글에서 들었던 예시인 banana를 사용하자. LCP 배열을 만들기 위해서는 우선 해당 접미사가 정렬된 Suffix 배열에서 어느 위치에 있는지를 기록해야한다. 이를 위..
이번에 풀어볼 문제는 빙산 문제이다. 시간이 지나면서 입력으로 주어진 빙산이 녹아가는데, 빙산이 처음으로 분리되는 시간을 구하는 문제이다. 문제의 조건은 아래와 같다. 빙산이 상하좌우로 맞닿아 있는 바닷물의 칸수만큼 녹는다. 빙산이 차지하는 칸의 개수는 최대 10,000개이다. 배열의 첫 번째 행과 마지막 행, 첫 번째 열과 마지막 열에는 빙산이 존재하지 않는다. 빙산의 높이는 최대 10이다. 기본적인 탐색 문제이다. 먼저 바닷물과 맞닿아 있는 빙산들을 녹이고 나서, 아직 녹지 않은 빙산을 기준으로 탐색을 진행하여 연결된 빙산들을 모두 방문처리 해주는 방식이다. 이렇게 탐색이 한 번 진행된 이후에도 아직 방문하지 않은 빙산이 존재한다면, 빙산이 둘 이상으로 갈라지게 된 것이므로 탐색을 종료한다. 다만 이..
위상 정렬(Topology Sort)이란? 위상 정렬이란 DAG에서 정점을 선형으로 정렬한 것이다. 이때 간선의 정보가 u -> v 형식으로 주어진다면, 위상 정렬의 결과는 항상 정점 u가 정점 v보다 앞에 오게 된다. DAG(Directed Acyclic Graph) DAG는 비순환 방향 그래프를 의미하며, 사이클이 없고 간선에 방향이 존재하는 그래프를 의미한다. DAG가 아닌 그래프, 즉 간선에 방향이 없거나 사이클이 존재하는 그래프에 대해서는 위상 정렬이 불가능하다. 위상 정렬을 활용하는 적절한 예시로 대학교 선수 과목을 들 수 있다. 다음 그림과 함께 살펴보자. 위와 같이 선수 과목들이 정해져 있을 때, 자연어처리와 데이터베이스 시스템 과목을 수강하기 위해서 먼저 들어야 하는 과목을 순서대로 나열..
이번 포스팅의 주제는 최단 경로 알고리즘이다. 그래프 상에서 특정 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘인데, 대표적인 알고리즘으로 오늘 알아볼 다익스트라 알고리즘과, 추후 포스팅 할 예정인 플로이드-워셜 알고리즘, 벨만-포드 알고리즘이 있다. 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 그리디 알고리즘의 한 형태이다. 알고리즘의 진행 과정은 아래와 같다. 초기 distance table의 값을 모두 INF 값으로 설정해 주고, 시작 노드의 값만 0으로 설정한다. 현재 distance table에서 아직 방문하지 않았으며, 남은 경로 중 가장 경로가 짧은 노드에 대해서 검사를 진행한다.(초기의 경우 시작 노드) 현재 노드와 인접한 노드들을 검사한다. 현재 노드까지의 최단 경로..
서로소 집합 먼저 중학생 때 배웠던 서로소를 떠올려보자. 어떤 두 수 A와 B가 있을 때, 두 수의 공약수가 1을 제외하고는 존재하지 않는 수를 서로소라고 부른다. 이를 고등학생 때 배운 집합의 개념을 빌려 그림으로 표현해 보자. 위의 그림은 24와 49의 약수를 벤다이어그램으로 표현한 것이다. 그림을 보면 둘의 공약수가 오직 1만 존재하는 것을 볼 수 있으며, 이런 형태의 수를 서로소라고 부른다. 이제 집합에서의 서로소가 무엇을 의미하는지 알아보자. 정수에서 서로소는 서로의 약수가 1을 제외하고 겹치지 않는 것을 의미했다. 이와 유사하게 서로소 집합은 두 집합의 원소가 겹치지 않는 것을 의미한다. 예를 들면 아래의 그림과 같은 집합을 서로소 집합이라 부를 수 있다. 위의 두 집합 A와 B를 보면, 두 ..
https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 이번에 풀 문제는 아침 산책이라는 문제다. 이전 문제들과는 달리 서브태스크가 있고 각 태스크마다 배점이 부여되어 있는데, 이를 통해 내 풀이가 어떤 조건을 만족하지 못하는지 알 수 있다. 일단 본격적으로 풀이를 하기에 앞서 문제 요구사항을 짚고 넘어가자! 문제에서 장소를 노드로 표현하였으며, 실내인 노드는 1, 실외인 노드는 0으로 표현하였다. 문제에서 구하고자 하는 것은 실내..
그래프 탐색 알고리즘 그래프 탐색 문제는 시작 정점이 주어졌을 때, 시작 정점에서 간선을 타고 이동할 수 있는 모든 정점을 구하는 문제이다. 그래프 탐색 알고리즘에는 대표적으로 너비 우선 탐색(breadth-first-search;BFS)과 깊이 우선 탐색(depth-first-search;DFS) 방식이 있다. 깊이 우선 탐색(DFS) DFS의 경우 이름부터가 깊이 우선 탐색이기 때문에 노드의 깊이가 직접적으로 나타나지 않는 그래프보다는 트리에서 이해하기가 좋다. 만약 다음과 같은 트리의 1번 정점에서 DFS를 진행한다고 하자. 진행 과정은 아래의 그림과 같다. 먼저 현재 노드인 1번 노드를 방문 처리 한다. 이후 1번과 연결되어 있는 간선을 하나씩 조사하는데, 먼저 4번 노드와 연결된 간선을 조사한다..
https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 이번에 풀 문제는 가장 가까운 두 점이다. 2차원 평면상에 n개의 점이 주어졌을 때, 가장 가까운 두 점의 거리를 구하는 간단한 문제이다. 설명은 아주 간단하지만 풀이는 그렇지 않다! n의 범위가 최대 100,000 이기 때문에 완전 탐색으로 문제를 풀게 되면 시간 초과를 피하지 못한다... 나는 이 문제를 분할 정복 방식으로 풀었는데, 풀이가 이전에 풀었던 히스토..
https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 이번에 풀 문제는 철로 문제이다. 문제에서 요구하는 사항은 다음과 같다. 집과 사무실을 통근하는 n명의 사람들이 있고, 각각의 사람들의 집의 좌표와 사무실의 좌표가 정보로 주어진다. 설치할 수 있는 철로의 길이 d가 주어진다. 이때 집과 사무실이 모두 철로의 경로에 포함되는 사람의 수를 최대로 하게끔 철로를 설치하는 프로그램을 작성하라. 문제 풀..
이번 문제는 원영역 문제이다. N개의 원의 중심 좌표와 원의 반지름이 주어졌을 때, N개의 원들로 나누어지는 영역의 개수를 구하는 문제이다. 처음에는 문제 조건이 너무 복잡해 보였지만, 원의 중심이 모두 일직선 위에 있고, 원들이 겹치는 경우는 없다는 제약이 있었기 때문에 생각보다 어렵지 않게 풀 수 있는 문제였다. 문제 풀이 방식은 철로 문제와 유사하니 풀어보고 오면 좋다! 이 문제 또한 $O(n^2)$의 완전 탐색으로 풀 수 있다. 물론 문제 입력값의 최대 크기가 300,000 이기 때문에 시간제한에 걸리지만... 그래도 문제의 정답을 찾기 위해 어떠한 조건을 만족해야 하는지 알아보기 위해 완전 탐색으로 푸는 경우를 생각해 보자. 먼저 원이 영역을 나누는 방식을 생각해봐야 할 것이다. 문제에서 영역이..
