Oneulog

위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 예시) 선수과목을 고려한 학습 순서 결정 위 세 과목을 모두 듣기 위한 적절한 학습 순서는? 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 자료구조 -> 고급 알고리즘 -> 알고리즘 (X) 진입차수와 진출차수 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 큐를 이용하는 위상 정렬 알고리즘의 동작 과정은 다음과 같다. 진입차수가 0인 모든 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. 새롭게 진입차수가 ..

최단 거리 문제 모든 간선의 비용이 양수일 때 1번 노드에서 다른 노드로 가기 위한 최소 비용은 얼마일까? 음수 간선이 포함될 때 아래 그래프에서는 음수 간선이 포함되어 있지만 여전히 최단 거리를 계산할 수 있다. 음수 간선의 순환이 포함될 때 하지만 음수 간선의 순환이 포함된다면 최단 거리가 음의 무한인 노드가 발생한다. 최단 거리 문제 음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류할 수 있다. 모든 간선이 양수인 경우 음수 간선이 있는 경우 음수 간선 순환은 없는 경우 음수 간선 순환이 있는 경우 벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다. -> 또한 음수 간선의 순환을 감지할 수 있다. -> 벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘..

비트마스크란 비트마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 사용하며, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. 이진수는 0 또는 1을 사용하므로 하나의 비트가 표현할 수 있는 경우는 2 가지이다. 비트마스크의 장점 1. 수행 시간이 빠르다. -> 비트마스크 연산은 비트 연산이기 때문에 O(1)의 시간복잡도로 구현되는 것이 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 동작한다. 다만, 비트마스크를 이용하는 경우에는 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 적은 경우에는 속도에 큰 차이가 없지만, 연산 횟수가 늘어날수록 차이가 매우 커지게 된다. 2. 코드가 짧다. -> 다양한 집합 연산들을 비트 연산자로 한 줄로 작성할 수 있기 때문에 반복문, 조건문 등을..

최장 증가 수열 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분 수열을 의미한다. 이 때, 부분 수열의 각 수는 서로 연속할 필요는 없다. 아래 수열에서 최장 증가 수열을 찾으면 아래와 같다. {10, 20, 30, 50} 는 전체 수열 중 오름차순으로 증가하는 가장 긴 부분 수열이다. 문제의 풀이 방법 Dynamic Programming(동적 계획법) 이진 탐색 Dynamic Programming(동적 계획법) x : 수열 A의 크기 arr : 수열 A를 이루고 있는 A(i)를 담은 배열 dp : arr[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이 x = int(input()) arr = list(map(int, input().split()) dp = [1 for i in ra..

크루스칼 알고리즘 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘 -> 여러 개의 도시가 있을 때 각 도시의 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하기 위해 적용되는 알고리즘 핵심 개념 간선을 거리가 짧은 순서대로 그래프에 포함시키면 어떨까? 주의 사항 사이클이 발생하지 않아야 한다. 사이클이란 그래프가 서로 연결되어 사이클을 형성하는 경우 최소 비용 신장 트리에서는 사이클이 발생하지 않아야 한다. 사이클 발생 여부는 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..

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] 값을 찾아..

배낭 문제 배낭 문제란 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제. Fraction Knapsack Fracktion Knapsack 문제는 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결할 수 있다. 남은 배낭이 감당할 수 있는 무게보다 물건의 무게가 많이 나가면 잘라 넣으면 된다. → Greedy로 해결 가능 0-1 Knapsack 0-1 Knapsack 문제는 물건을 자를 수 없기 때문에 물건, 물건의 무게, 물건의 가격, 배낭의 남은 용량을 모두 고려해야 한다. → DP로 해결 가능 0-1 Kna..