Redddy's Devlog

한동안 알고리즘 공부를 멈췄다가 최근에 다시 흥미가 생겨 발을 들이기 시작했다. 이번에는 또 어떤 씹덕 알고리즘을 배워볼까 하다가 이분 매칭이 맛있어 보였다.    모든 간선 용량이 1이고, 정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 유량 그래프를 이분 그래프(bipartite graph)라고 한다.    이분 그래프에서 한쪽 그룹을 A, 다른 쪽 그룹을 B라고 할 때, 간선의 방향이 모두 A -> B일 때, 최대 유량을 구하는 문제를 이분 매칭(bipartite matching) 문제라고 부른다. 위 그림에서는 생략되었지만 소스에서 A로 가는 간선과 B에서 싱크로 가는 간선이 있다고 생각하면 된다.  이분 그래프에서 매칭은 두 그룹의 정점..

대회하면서 매번 헷갈릴 때가 있어서 정리해두려고 한다. 특정 비트 1로 만들기 x = 12 x |= (1

문자열 $N$ 와 $H$가 주어졌을 때 $N$에 $H$ 있는지 찾는 문자열 검색 알고리즘에 대해 알아보자. 나이브하게 접근해보면 $N$의 첫문자부터 마지막문자까지 $H$와 하나하나 비교해가면서 일치하는지 판별할 수 있고 해당 솔루션의 시간복잡도는 $O(|N|*|H|)$ 이다. 문자열의 길이가 짧다면 해당 접근방법도 구현도 쉽고 나쁘지만은 않다. 하지만 문자열의 길이가 커진다면 제한시간내에 동작하지 못하게 된다. $N[k...i-1]$과 $H[...i-1]$ 까지는 문자열이 일치하였지만 $H[i]$ 문자에서 일치하지 않는경우 다시 $N[k+1]$ 부터 비교하는 것이 아니라 이미 $H[...i-1]$까지 어떤 문자가 있는지 알고 있으니 보지 않아도 $H[k+1]$이 $H[0]$과 같은지 다른지는 알 수 있지..

서로소 집합 (Disjoint Sets) 서로소 집합은 공통 원소가 없는 두 집합을 의미한다. A = {1, 2} 와 B = {3, 4} 가 있다면 두 집합은 서로소 관계이다. 서로소 집합 자료구조란 서로소 부분들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조다. 서로소인지 판별하려면 union과 find 연산이 필요하다. union연산은 두 집합을 하나의 집합으로 합치는 연산이고 find 연산은 어떤 원소가 주어졌을 때 이 원소가 속한 집합의 대표를 찾는 연산이다. 즉 find 를 통해 주어진 두 집합의 대표를 비교하여 서로 서로소인지 확인이 가능 한 것이다. 때문에 서로소 집합 자료구조는 유니온파인드(Union-Find)라고도 불리운다. 집합 {1, 2, 3, 4, 5, 6}이 있고 여기에 un..

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드 워셜 알고리즘은 플로이드와 워셜이 개발한 알고리즘으로 그래프의 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 데이크스트라 알고리즘과 비슷하게 단계별로 거쳐 가는 노드를 기준으로 최소값을 갱신하지만, 데이크스트라 알고리즘은 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾아서 방문하였다면 이 플로이드 워셜 알고리즘은 아묻따 모든 노드를 탐색한다. 인접 행렬 형태의 2차원 테이블을 만들어 최단 거리 정보를 저장한다. 이전에 한번 한 연산은 다시 반복하지 않는다는 점에서 다이나믹 프로그래밍 유형에 속한다. 이 알고리즘은 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인하여 갱신해준다. a에서 ..

데이크스트라 알고리즘 (Dijkstra Algorithm) 최단 경로 알고리즘은 주어진 그래프에서 가장 빨리 도달할 수 있는 길을 찾는 알고리즘이다. 노드를 연결하는 간선에 비용 있어 간선의 갯수가 같다고 하여도 실제 이동시간은 다를 수 있기에 그런 것들을 잘 체크해주어야 한다. 데이크스트라 알고리즘은 음의 간선이 없을 때 정상적으로 작동한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계에서 음의 간선이란 존재할 수 없다. 때문에 GPS 소프트웨어의 기본 알고리즘으로 채택되기도 한다. 데이크스트라 알고리즘의 동작 원리는 인접한 노드중에 가장 비용이 적은 노드를 선택하여 움직이기에 그리디 알고리즘으로 분류된다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화 한다. 방문하지 않은..

다이나믹 프로그래밍 (Dynamic Programming) 다이나믹 프로그램은 동적 계획법이라고도 불리운다. 다이나믹 프로그램의 기본 모토는 중복되는 연산을 줄이는 것이다. 한번 실행한 연산들은 DP 테이블(리스트)에 저장해두고 그 연산이 필요할 때마다, 연산을 하지 않고 그 DP 테이블에서 연산데이터를 호출하는 방식이다. 이런 기법은 메모제이션 기법이다. 다이나믹 프로그래밍의 대표적인 예제로 피보나치 수열이 있다. 피보나치 수열의 점화식은 a(n) = a(n-1) + a(n-2), a(1) = 1, a(2) = 1 이다. 즉 이전 데이터와 전전 데이터를 더하여 현재 데이터가 된다. 피보나치 수열을 재귀적으로 구현한 코드는 다음과 같다. # 피보나치 함수(Fibonacci Function)을 재귀함수로 ..

이진 탐색 (Binary Search) 이진 탐색이란 정렬되어 있는 데이터에서 특정 데이터를 찾을 때 사용된다. 이진 탐색 말고도 탐색법은 여러개가 있는데, 그중 순차 탐색은 리스트에 저장된 데이터를 처음부터 끝까지, 즉 첫번째 인덱스부터 마지막 인덱스까지 순서대로 탐색하는 방법이다. 이진 탐색의 탐색 방법은 우선 데이터의 중간값과 타겟을 확인한다음 만약 중간값이 타겟값보다 작다면 이제 중간값보다 더 큰 데이터들만 확인하고, 만약 중간값이 타겟값보다 크다면 중간값보다 작은 데이터들만 확인하면 된다. 다시말해 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 우리가 어렸을 때 했던 업앤다운 숫자찾기 게임도 이진 탐색을 사용하면 순차탐색보다 빠르게 찾아낼 수 있다. 1부터 10까지의 자연수 중 하나를..

정렬 (Sorting) 정렬은 데이터를 특정한 기준에 따라서 순차적으로 나열하는 것이다. 흔히 사용하는 내림차순이나 오름차순 역시 이 정렬을 통해 이루어진다. 이진탐색이라는 탐색기법은 정렬과정을 거친 후에만 사용이 가능하다. 정렬알고리즘은 Comparison Sorting Algorithm(비교방식 알고리즘)과 non - Comparison Sorting Algorithm 이렇게 크게 두가지로 나눌 수 있다. 비교방식 알고리즘에는 선택정렬, 삽입정렬, 퀵정렬 등이 있고, non-비교방식 알고리즘에는 계수 정렬이 있다. 선택 정렬 (Seletion Sort) 선택 정렬은 배열에서 가장 작은 데이터를 선택하여 다른 데이터와 자리를 바꾸는 알고리즘이다. 일반적으로 쉽게 떠올릴 수 있다. 정렬되지 않은 배열에서..

※ 그래프 사진은 직접 그려서 추가예정! 갤럭시 탭이 오면 그걸로 그려야지ㅎ.ㅎ DFS와 BFS는 모두 그래프 탐색 알고리즘이다. 코딩테스트를 준비하다보면 어느 순간 만날 수 밖에 없는 알고리즘이다. DFS DFS는 Depth-first Search의 약자로 깊이 우선 탐색을 의미한다. 그래프의 가장 깊은 곳 우선으로 탐색을 하는 알고리즘이다. 스택 자료구조를 사용하여 그래프를 탐색한다. DFS의 탐색과정은 다음과 같다. 탐색 시작 노드를 스택에 넣고, 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그중 가장 작은 값의 인접 노드를 스택에 넣고 방문처리한다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때가지 반복..