Oneulog

크루스칼 알고리즘 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘 -> 여러 개의 도시가 있을 때 각 도시의 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하기 위해 적용되는 알고리즘 핵심 개념 간선을 거리가 짧은 순서대로 그래프에 포함시키면 어떨까? 주의 사항 사이클이 발생하지 않아야 한다. 사이클이란 그래프가 서로 연결되어 사이클을 형성하는 경우 최소 비용 신장 트리에서는 사이클이 발생하지 않아야 한다. 사이클 발생 여부는 Union-Find 알고리즘을 적용하면 된다. 동작 과정 모든 간선들을 '거리(비용)' 기준으로 먼저 오름차순 정렬 수행 정렬된 순서에 맞게 그래프에 포함시킨다. 포함시키기 전에 사이클 테이블을 확인한다. 사..

Union-Find 알고리즘 '합집합 찾기'라는 의미를 가진 알고리즘 서로소 집합 알고리즘이라고도 부름 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 위와 같이 여러 개의 노드가 있다고 가정한다. 이와 같이 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 즉 모든 값이 자기 자신을 가리키도록 만든다. 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 이 때 노드 1과 2가 연결되었다고 가정한다. 이러한 '연결성'을 우리가 프로그래밍 언어로 어떻게 표현할 수 있을지에 대한 내용이 Union-Find 알고리즘 1 2 3 4 5 6 7 8 1 1 3 4 5 6 7 8 위 표와 같이 2번째 인덱스의 값에 1..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 100..

LCS 알고리즘 LCS는 주로 최장 공통 부분 수열(Longest Common Subsequence)을 말한다. LCS는 최장 공통 문자열(Longest Common Substring)을 말하기도 한다. 최장 공통 부분 수열과 최장 공통 문자열의 구분 최장 공통 부분 수열(Longest Common Subsequence) 점화식 두 문자가 다를 경우 LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]) 두 문자가 같을 경우 LCS[i][j] = LCS[i-1][j-1] + 1 동작 과정 1. 문자열 A, 문자열 B를 한 글자씩 비교한다. 2. 두 문자가 다르다면 LCS[i-1][j] 와 LCS[i][j-1] 중 큰 값을 표시 3. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아..

https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 문제 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔..

https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 문제 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다. 이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원..

https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 문제 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 출력 첫째 줄에..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들..