LimeCoding

위상 정렬이란?(What is Topological Sorting?) 위상 정렬의 뜻을 검색해보면 "DAG에 대한 위상 정렬은 정점 u에서 정점 v로 가는 방향이 있는 간선이 있을 때 모든 정점 u가 모든 정점 v 앞에 오도록 정점을 정렬하는 선형 정렬"이라고 나온다. 이 말이 쉽게 와닿지 않을 수 있다. 하지만 게임의 테크트리를 생각하면 어떤 말인지 쉽게 알 수 있다.  우리가 게임을 하다보면 어떤 기술을 열거나 건물을 건설할 때 요구 조건이 있는 것을 한번쯤은 봤을 것이다. 그리고 요구 조건을 충족할 때만 기술을 열거나 건물을 건설할 수 있다. 이때 각 건물과 기술들이 정점이 되는 것이고 요구 조건과 관련된 건물과 기술의 관계가 간선이라고 생각하면 된다.  그런데 위상 정렬 앞에 DAG란 조건이 붙어..

이분 검색이란?(What is binary search?) 이전 포스팅에서 작성한 순차 검색은 최대 n이라는 시간이 걸리는 검색 방법이다. 그렇기에 n이 100만, 1000만이 되면 검색하는데 상당히 많은 시간이 소요된다. 이를 해결하기 위한 알고리즘이 바로 이분 검색이다. 이분 검색은 대표적인 분할 정복 알고리즘이다. 이러한 분할 정복 알고리즘은 반복문으로 고쳐주면 더 빠른 성능을 낼 수 있다. 이분 검색의 작동 방식은 다음과 같다. 배열의 중간 요소와 찾고자하는 값을 비교한다. 이때 찾고자하는 값이 배열의 중간 요소이면 값을 리턴하고 종료한다. 배열을 반으로 나눈다. 중간 요소를 기준으로 찾는 값이 작으면 왼쪽 배열을, 크면 오른쪽 배열을 탐색한다. 1~3을 반복한다. 이분 검색 알고리즘(Binary..

나머지 연산(Modular) 이번에는 모듈러 연산에 대해 알아보려고 합니다. 모듈러 연산은 어떤 정수 a가 주어졌을 때 이를 0이 아닌 정수 b로 나눈 나머지를 구하는 연산입니다. 기호로는 mod를 사용합니다. 예를 들어 10을 3으로 나눈 나머지가 알고 싶다면 10 mod 3 = 1과 같은 방식으로 표현합니다. 이 나머지 연산은 코딩 문제를 풀면서 결과값이 커지는 걸 방지하기 위해 많이 사용하는데 나머지 연산에는 재미있는 규칙이 숨어 있습니다. 나머지 연산의 분배 법칙 나머지 연산에는 3가지 연산에 대해 분배 법칙이 존재합니다. (A + B) mod p = ((A mod p) + (B mod p)) mod p (A - B) mod p = ( (A mod p) - (B mod p)) mod p (A * ..

플로이드-워셜 알고리즘 가중치 그래프에서 만들 수 있는 모든 두 정점 사이의 최단 거리를 구하는 알고리즘이다. 이 그래프를 사용하기 위해선 가중치가 음이 아니여야 한다.(음수이면 무한정으로 음수를 더함) 플로이드 워셜 알고리즘은 최단 거리를 구하기 위해 동적 프로그래밍 방식을 사용한다. 먼저 그래프에서 모든 노드로 가는 최단 거리를 2차원 배열로 만든다. 이때 자기 자신(1 -> 1)으로 가는 최단 거리는 0이다. 또한 갈수 없는 노드는 무한으로 표현한다. 프로그램에서는 무한대 표현이 불가능함으로 무한대를 나타낼 수 있는 충분히 큰 수로 대체한다. 2차원 배열을 모든 정점의 개수가 n개일 때 n * n형태의 배열이 만들어진다. 1 2 3 4 5 1 0 1 3 - - 2 1 0 4 7 - 3 3 4 0 -..

오랜만에 공부관련으로 포스팅하는 것 같다. 좀 게으른 면이 있어서 포스팅은 안했지만 개인적으로 공부는 꾸준히하고 있었다. 잡담은 이 정도로 하고 알고리즘 첫 포스팅을 시작해야겠다. 순차 검색이란?(What is sequential search?) 순차 검색은 말 그대로 순차적으로 검색하는 방법을 말한다. 이름이 적힌 장부가 하나 있다고 가정해보자. 근데 장부 이름이 정렬이 안되어 있다면 우리는 이름을 찾을 때 처음부터 순차적으로 이름을 찾아야 한다. (찍어서 맞췄다면 축하한다! 당신은 컴퓨터보다 나은 존재다.) 이런 상황에서 순차 검색을 사용한다. 순차 검색은 우리가 가장 쉽게 떠올릴 수 있을 만큼 쉽지만 그만큼 원시적인 방법이라 이후에 나오는 검색 방법에 비해 성능이 상당히 안 좋다. 그럼 순차 검색이..

알고리즘은 자료구조와 땔 수 없는 존재이기 때문에 서로 동시에 소개되는 경우가 많다. 필자가 공부할 때도 그랬기 때문에 자료구조에서 기본적인 알고리즘의 개념을 배웠다. 그래서 기본은 자료구조에 잘 써져있다. 알고리즘으로 가져오기는 조금 그래서 혹시 알고리즘의 기본이 궁금하다면 필자 블로그의 자료구조 포스팅의 처음을 봐주길 바란다. '자료구조' 카테고리의 글 목록 (3 Page) limecoding.tistory.com

다익스트라 알고리즘이란?(What is a Dijkstra Algorithm?) 다익스트라 알고리즘은 가중치를 가지는 그래프에서 한 정점을 기준으로 다른 정점들에 도달하는 최단 경로를 찾는 알고리즘이다. 이때 중요한 것은 가중치가 음수를 가지면 안된다는 것이다. 가중치가 음수를 가지면 다익스트라 알고리즘이 동작할 수 없다. 다익스트라 알고리즘은 인접한 정점으로 가는 간선중 가장 적은 비용을 가지는 간선을 택한다. 알고리즘 수행중 새로운 경로가 생기면 그 경로를 기록하고 이후에 생기는 또 다른 경로와 비교하면서 최단 경로를 탐색한다. 다익스트라 알고리즘을 수행하기 위해서는 먼저 그래프를 인접 행렬로 표현해야 한다. 위 그림에서 인접 행렬을 보면 무한대 표시가 보인다. 이는 정점이 인접하지 않는다는 표시이다..

솔린 알고리즘이란?(What is a Sollin Algorithm) 솔린 알고리즘은 최소 비용 신장 트리를 구하는 알고리즘중 하나로 크루스칼 알고리즘과 프림 알고리즘처럼 간선을 하나씩 선택하는 것이 아닌 동시에 여러 개의 간선을 선택하여 트리를 만드는 알고리즘이다. 솔린 알고리즘을 설명하기 전 포레스트(Forest)라는 용어의 정의가 필요하다. 포레스트란 서로 연결되지 않은 트리들의 집합 또는 연결되지 않은 비순환 그래프의 집합을 말한다. 그림으로 표시하면 다음과 같다. 그림을 보면 두 그래프는 서로 순환하지 않은 그래프이면서 서로 연결되어 있지 않다. 이런 자료 구조를 포레스트라고 한다.(정점만 있는 그래프나 하나의 트리도 포레스트가 될 수 있다.) 이제 솔린 알고리즘을 설명할 수 있다. 솔린 알고리..

프림 알고리즘이란?(What is a Prime Algorithm) 프림 알고리즘은 최소 비용 신장 트리를 구하는 알고리즘중 하나이다. 가중치를 가지는 그래프에서 가장 작은 가중치를 가지는 엣지를 시작으로 인접한 정점과 연결된 엣지들중 가장 작은 가중치를 가지는 엣지들을 선택해 나가면서 신장 트리를 만드는 것이 프림 알고리즘이다. 프림 알고리즘이 엣지를 하나씩 선택한다는 점에서는 크루스칼 알고리즘과 같지만 인접한 정점의 엣지들만 선택한다는 점에서는 크루스칼 알고리즘과 다른 점을 보여준다. 다음은 프림 알고리즘 수행 과정이다. 그래프 및 가중치 표 다음은 프림 알고리즘에 사용될 그래프와 그래프의 가중치를 표로 나타낸 것이다. 그럼 프림 알고리즘을 수행해보자. (4, 6) 선택 먼저 시작은 가장 작은 가중치..

크루스칼 알고리즘이란?(What is a Kruskal Algorithm?) 최소 비용 신장 트리를 구하는 알고리즘중 하나인 크루스칼 알고리즘은 가중치가 부여된 그래프 G = (V, E)가 있을 때 그래프 G를 이루는 G(V)에 대해 가장 가중치가 낮은 엣지부터 각 정점들이 모두 연결될 때까지 간선을 추가한다. 이때 엣지는 사이클이 만들어지지 않는 엣지만 선택해야한다. 그래프가 n개의 정점으로 이루어져 있다면 가중치가 가장 낮은 엣지부터 시작해서 n-1개의 엣지를 선택하여 만들면 된다. 만약 n-1개 미만의 엣지만이 존재한다면 이는 그래프가 애초에 연결 그래프가 아닌 상태이다. 다음은 크루스칼 알고리즘을 이용한 최소 비용 신장 트리 구성 방법이다. 그래프의 초기 상태 및 각 엣지의 가중치 그래프의 형태와..