본문 바로가기

전체 글

 (104)
다익스트라 다익스트라 (Dijkstra)다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 다음과 같다. 기능특징시간 복잡도 (노드 수 : V, 에지 수: E)출발 노드와 모든 노드 간의 최단 거리 탐색에지는 모든 양수O(ElogV) 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있다.   다익스트라 알고리즘의 핵심 이론1. 인접 리스트로 그래프 구현하기 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋다. 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결했다.  2. 최단 거리 배열 초기화하기최단 거리 배열을 만들고,..
위상 정렬 위상 정렬 (topology sort)위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 기능특징시간 복잡도(노드 수 :V, 에지 수 :E)노드 간의 순서를 결정사이클이 없어야 함O(V+E) (참고 : https://m.blog.naver.com/ndb796/221236874984) 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.  위상 정렬의 핵심 이론위상 정렬은 다음과 같은 단계로 설명할 수 있다. 다음 예를 보자. 위상 정렬의 원리 이해하기1. 진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다. 다음을 보면 ArrayList로 그래프를 표현했다. 그래프..
유니온 파인드 유니온 파인드 (union-find)유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다. https://ip99202.github.io/posts/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C(Union-Find)/ 유니온 파인드(Union-Find)유니온 파인드란? 유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다..
그래프의 표현 그래프그래프는 노드와 에지로 구성된 집합이다. 노드는 데이터를 표현하는 단위이고 에지는 노드를 연결한다. 여기서는 그래프를 구현하는 3가지 방법을 알아본다. 에지 리스트 (edge list)에지 리스트는 에지를 중심으로 그래프를 표현한다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현한다. 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현한다.  에지 리스트로 가중치 없는 그래프 표현하기가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다. 노드는 여러 자료형을 사용할 수 있으며 다음의 경우 노드는 Integer 형이다.1에서 2로 뻗어나가는 에지는 [1, 2]로 표현한다. 4에서 5로 뻗어나가는 에지는 [4, 5]로 표현한..
정수론 - 확장 유클리드 호제법 유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것이다. 확장 유클리드 호제법을 제대로 이해하려면 수학 증명 과정까지 공부해야 하지만 여기서는 확장 유클리드 호제법 관련 문제를 풀기 위한 알고리즘만 설명한다.  확장 유클리드 호제법의 핵심 이론확장 유클리드 호제법에서 해를 구하고자 하는 방정식은 다음과 같다. 해를 구하고자 하는 방정식ax + by = c (a, b, c, x, y는 정수) 이때 위 방정식은 c % gcd(a, b) = 0인 경우에만 정수해를 가진다. 다시 말해 c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가진다. 이는 ax + by = c가 정수해를 갖게 하는 c의 최솟값이 gcd(a, b)라는 것을 의미한다..
정수론 - 유클리드 호제법 유클리드 호제법 (euclidean-algorithm)유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시한다.  유클리드 호제법의 핵심 이론유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 한다. MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문이다.  연산기능예제MOD두 값을 나눈 나머지를 구하는 연산10 MOD 4 = 2 // 10 % 4 = 2 MOD 연산을 이해하면 다음과 같은 3단계로 유클리드 호제법을 구현할 수 있다. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.앞 단계에서의 작은 수와 MOD 연산 결괏..
정수론 - 오일러 피 오일러 피오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있지만 여기서는 실제 코딩 테스트에 사용하기 위한 구현 부분만 알아본다.  오일러 피의 핵심 이론오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다.1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화한다.2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면 (=소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] / K 연산을 수행한다. (i는 K의 배수)3. 배열의 끝까지 2를 반복하며 오일러 피 함수를 완성한다.  오일러 피 함수의 원리 이해하기 1. 구하고자 하는 범위까지 배열을 생성..
정수론 - 소수 구하기 수학에서 정수론은 수의 성질을 탐구하고 공부하는 분야를 뜻한다. 실제 코딩 테스트에서는 모든 정수론의 분야가 나오지 않고, 영역도 매우 방대하므로 전체를 공부하기에는 효율성이 떨어진다. 따라서 여기서는 소수 부분과 호제법 부분을 집중적으로 다루도록 하겠다.  소수 구하기소수(prime number)는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. 이와 같은 의미로 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다. 코딩 테스트에서는 이러한 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제된다.  소수 구하기의 핵심 이론소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다. 원리는 다음과 같다. 1. 구하고자 하는 소수의 범위만큼 1차원 배열을..

티스토리툴바