MJmemento

크루스칼 알고리즘란? 크루스칼 알고리즘은 주어진 그래프에 대한 최소 스패닝 트리를 생성하는 데 사용되며 그리디 부류로 작동한다. 그럼 잠깐, 최소 스패닝 트리란 정확히 무엇알까? 최소 스패닝 트리는 그래프와 꼭짓점 수가 같고 꼭짓점 수가 -1인 그래프의 부분 집합이다. (또한 스패닝 트리의 모든 에지 가중치 합계에 대한 최소 비용도 있다.) 그럼 다음으로, 크루스칼 알고리즘은 어떻게 작동할까 ? 1. 모든 에지를 에지 가중치의 오름차순으로 정렬하고, 2. 선택한 에지가 어떤 사이클을 형성하지 않는 경우에만 트리에 노드를 계속 추가한다. 3. 처음에는 최소 비용으로 에지를 선택하고, 마지막으로 최대 비용으로 에지를 선택한다. 다시금 말하면 모든 최소 결과를 찾기 위해 국소적으로 최적의 선택을 한다고 말할 ..

위상 정렬이란? 꼭짓점 u와 v에서 꼭짓점 v까지의 모든 꼭짓점 u,v에 대해 u가 순서에서 v보다 먼저 오도록 꼭짓점을 선형 정렬하는 것이다 다시금 예를 들어, 그래프의 정점들을 수행할 작업의 순으로 나타낼 수 있고, 가장자리는 한 작업이 다른 작업보다 먼저 수행되어야 하는 제약 조건을 나타낼 수 있다. 여기서 위상 정렬은 비순환 그래프(DAG)인 경우에만 가능하다. (비순환 그래프는 적어도 하나의 위상 순서를 가지며, 알고리즘은 선형 시간 내에 DAG의 위상 순서를 구성하는 것으로 알려져 있다.) 또한 DAG그래프만이 그래프에 사이클이 있으면서 두 정점 u,v가 사이클 속에 위치한 정점일 경우, 정점 u가 v보다 먼저 오거나 v가 u보다 먼저 올 수 있기에 DAG 그래프만 위상 정렬이 가능하다. 조금..

플로이드 와샬 알고리즘이란? 양 또는 음의 에지 가중치를 갖는 방향 가중 그래프에서 각각의 정점에서 정점까지의 모든 최단 경로를 찾는 알고리즘이다. 다시, 이전의 다익스트라와 벨만포드의 경우 두 정점간의 최소 거리를 계산했다면 플로이드와샬 알고리즘은 모든 정점간의 최소 거리를 알아내는 알고리즘이다. 다른 알고리즘들과 달리 구현이 매우 쉽다. 3중 for 문을 사용하며 O(V^3)의 시간 복잡도를 갖고 있다. 그럼 작동방식은 어떠할까? 아래 그림을 잠깐 보도록 하자 인접행렬로 행과열의 값 arr[a][b] 는 a에서 b로 가는 비용이다. 일단 주어진 가중치를 인접행렬에 갱신해준다. 그렇다면 이젠 가정이 필요하다. a에서 c까지 가는 경로가 있다고 보자, 그런데 a->b->c로 가는 경로가 더 싸다면?? a..

벨만 포드 알고리즘이란? 단일 소스 꼭짓점에서 다른 모든 꼭짓점까지의 최단 경로를 계산하는 알고리즘이다. 다익스트라와 같은 문제에 대한 알고리즘보다는 느리지만, 가중치 중 일부가 음수인 그래프를 처리할 수 있기 때문에 더 다용도적이다 이 알고리즘은 알폰소 심벨(1955)이 처음 제안했지만, 대신 1958년과 1956년에 각각 발표한 리처드 벨먼과 레스터 포드 주니어의 이름을 따서 명명되었다.[2] 에드워드 F 무어는 1959년에 이 알고리즘의 변형을 발표했으며, 이러한 이유로 벨먼-포드-무어 알고리즘이라고도 불린다. 다시, 이전에 설명한 다익스트라 알고리즘과 (모든 꼭짓점까지의 최단경로를 구하기에)비슷 하지만 차이점으로는 가중치(비용)이 음수가 가능하다. 여기서 의문이 생길 수 있다. " 가중치가 음수가..

다익스트라란? 컴퓨터 과학자 에드거 데이크스트라에 의해 만들어진 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘이다. 즉, 다익스트라 알고리즘은 주어진 그래프에서 시작점으로부터 원하는 노드로 가기에 가장 적은 비용을 갖고 도착하는 경우를 찾는다. (최단거리,최소비용) 위에서 말한 알고리즘을 적용하는 그래프는 방향이 주어지거나 안주어진 그래프의 경우로, 둘다 사용할 수 있지만 가장 많이 사용되는건 방향을 가진 그래프안에서 사용된다. 그럼 다익스트라 알고리즘은 어떻게 작동할까? 그리디처럼 현재 주어진 노드에서 가장 적은 비용으로 갈 수 있는 노드로 움직이는 방식을 가졌다. 상세한 설명 이전에 아래 그림을 보자 우리가 가고자하는 노드로 도착하기전에 이전에 방문한 곳을 계속해서 돌다간 도착할 수 없다. 그렇기..

투 포인터란? 정렬된 배열에서 한 쌍씩 검색하는데 사용되는 쉽고 효과적인 알고리즘이다. 두개의 기준을 잡고 안에 값들에 다라 조건을 걸어, 두 기준(pointer) 들을 옮겨주는 양상이다. 정렬된 배열 A(오름차순으로 정렬됨)가 N개의 정수를 가지고, 그 합이 X와 같도록 원소 쌍(A[i], A[j])이 존재하는지 알아보고자 하는 상황에서 투 포인터를 사용할 수 있다. def isPairSum(A, N, X): for i in range(N): for j in range(N): if(i == j): continue if (A[i] + A[j] == X): return True if (A[i] + A[j] > X): break return 0 arr = [2, 3, 5, 8, 9, 10, 11] val =..

구간한 배열이란? 순차적 계산 모델에서 계산하기 위해 yi = yi - 1 + xi 공식을 사용하여, 각 출력 값을 순차적으로 계산하기 위해 사용되는 기법이다. (알고리즘이라기보단 테크닉이다) 그렇다 이해하기 힘들테니 쉽게 얘기 하겠다. 어떠한 N크기의 배열이 있다 가정하자. 해당 배열에서 어떤 부분의 배열의 합을 구하려면 반복문을 통해 합을 구할 수 있다.O(N) 그러나 이러한 계산을 O(1)로 만들 수 있다면?! 구간합 배열을 사용하자 1 2 3 4 5 6 ... 1 3 6 10 15 21 ... N +1 크기의 배열을 만들어준다. 이후 해당 인덱스들의 누적합을 N+1 크기의 배열에 채워나간다. 만약 2~4 인덱스를 가진 요소들의 부분합을 구하고싶다면? (5인덱스에속한 N+1 배열의 값) - ( 2인..

백트레킹이란? 특정 제약 만족 문제에 대한 해결책을 찾기 위해 사용하는 알고리즘으로, 해결책에 대한 후보를 점진적으로 접근하고, 접근하던 후보가 유효한 해결책으로 완성될 수 없다고 판단되는 즉시 바로 전에 후보로 후퇴하여 다른 후보로 접근한다. 이미지로 보면 이러하다 . 사실 미로찾기와 같다. 미로찾기하면 무슨 알고리즘이 생각나는가? 바로 DFS다. 백트레킹은 완전 탐색의 한 종류인데 DFS를 활용하여 사용할 수 있다. 이번에는 그래프를 잠깐 잊고 아래 문제를 풀어보자 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.ne..