ComputerScience/알고리즘

최소스패닝트리(Minimum Spanning Tree) - 프림 알고리즘, 크루스칼 알고리즘

최소스패닝트리 란? 그래프 G에 대한 신장트리는 G의 마디를 모두 포함하면서 트리로 연결된 그래프이다. 이 중 모든 간선의 가중치가 최소가 되는 신장트리를 최소비용신장트리. 즉, 최소 스패닝 트리(MST)라고 한다. 존재하는 신장트리를 모두 찾아보는 방법은 최악시간복잡도가 지수시간보다 나쁘기 때문에, 탐욕적 방법을 사용하면 효율적으로 문제를 풀 수 있다. 부분적으로 최적인 고려 사항에 대해 이음선을 선택하는 알고리즘으로 프림 알고리즘과 크루스칼 알고리즘이 존재한다. 프림 알고리즘 : 최소 스패닝 트리를 찾기 위해 정점 부분집합에 이웃한 거리들을 판단하며 구한다. 즉, 신장트리에 붙은 마디 중 가장 minimum한 값을 선택하면서 만들어가는 방식이다. 알고리즘 단계 1. 하나의 꼭지점을 선택하여 이웃한 거..

Python 정규표현식(regex) 정리하기 - 1

정규 표현식(Regular Expressions)은 복잡한 문자열을 처리할 때 사용하는 기법으로, 파이썬만의 고유 문법이 아니라 문자열을 처리하는 모든 곳에서 사용된다. 정규 표현식의 기초, 메타 문자 정규 표현식에서 사용되는 메타 문자는 다음과 같은 것이 있다. 1. 문자 클래스 [] : "[] 사이의 문자들과 매치". [abc] 라면 a, b, c 중 한개의 문자와 매치를 뜻한다. 두 문자 사이에 "-" 를 사용하면 두 문자 사이의 범위(From-To)를 의미한다. [0-5]는 [012345]와 동일하다. 문자 클래스 안에는 어떤 문자나 메타 문자도 사용할 수 있지만 ^를 조심하여야 한다. ^는 반대라는 의미를 갖고 있어 [^0-9]라는 정규 표현식은 숫자가 아닌 문자만 매치된다. - [a-zA-Z]..

그래프

Least Common Ancestor 스패닝 트리 더보기 백준문제 - 집합의 표현 (1717) - 줄세우기 (2252) - 네트워크 연결 (1922) - LCA2 (11438) - 키 순서(2458) - 게임 개발(1516) - 교수님은 기다리지 않는다 (3830) - 도로네트워크 (3176) - 두번째로 작은 스패닝 트리(1626) 더보기 백준문제2 - 단절점 (11266) - 최단경로 (1753) - 타임머신 (11657) - 플로이드 (11404) - 단절선 (11400) - 할로윈 묘지(3860) - 거의 최단 경로(5719) - K번째 최단경로 찾기 (1854)

정수론과 조합론

유클리드 호제법 : 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a > b), a와 b의 최대 공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다. 1. a % b = r 2. gcd(a, b) = gcd (b, r) static long gcd(long a, long b) { while(b != 0) { long r = a % b; a = b; b = r; } return Math.abs(a); } 확장 유클리드 호제법 : 특정 방정식을 만족하는 해를 구할 수 있다. public class P3955 { static int T; static long A, B; public static void main(Stri..

자료구조

자료구조(Data Structure)란 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법을 이야기 한다. 자료구조는 저장되는 데이터의 형태에 따라 선형 자료구조와 비선형 자료구조로 구분된다. - 선형 자료구조 : 데이터가 일렬로 나열되어 있음. * 배열 (Array) * 연결리스트 * 스택 * 큐 - 비선형 자료구조 : 데이터가 특정한 형태를 띄고 있음. * 트리 * 그래프 배열 : 가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조. * 배열의 특징 - 데이터 접근이 용이. - 데이터 삽입 / 삭제가 어려움 (뒤로 1칸식 밀어주어야함. 최악의 경우 O(n)) - 구조가 간단하여 프로그램 작성이 쉬움. 연결리스트 : 각 노드가 데이터와 포인터를 가지고 일렬로 연결..

알고리즘 기초

### 알고리즘이란? 고대 페르시아의 수학자 알콰리즈미에서 유래되어 문제를 해결하기 위한 여러 동작들의 모임. 알고리즘을 이용하기 위해서는 복잡한 구조의 코드를 정확하게 구현할 수 있는 구현력이 필요하다. ### 알고리즘의 조건 - 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다. - 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다. - 입력 : 정의된 입력을 받아들일 수 있어야 한다. - 출력 : 답으로 출력을 내보낼 수 있어야 한다. - 유한성 : 특정 수의 작업 이후에 정지해야 한다. - 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다. 깊이우선탐색 (Depth First Search) - 그래프 탐색 방법의 한가지로 한 경로로 탐색하다 특정 상황에서 최대한 깊숙하게 들어..