알고리즘
-
Line Sweep 알고리즘 :: 마이구미알고리즘 2018. 2. 11. 19:09
이 글은 Line Sweep 알고리즘을 다룬다.Line Sweep, Sweep Line, 라인 스위핑 등과 같이 불려진다.일반적으로 가장 가까운 두 점을 찾는 문제에서 출발한다.다음 링크의 문제 풀이를 통하여 알고리즘을 설명할 것이다.( 백준 2261번 "가장 가까운 두 점" )참고 - https://www.acmicpc.net/blog/view/25 수 많은 점들 중에서 가장 가까운 두 점을 찾는 문제가 존재한다.이러한 문제의 시나리오는 다음과 같다. See the Pen line sweeping by leejunghyun (@mygumi) on CodePen. 순수한 접근으로 점들 중에서 가장 가까운 두 점을 찾는 방법은 간단하다.모든 점들을 확인하면 된다.하지만 이러한 경우 시간복잡도는 O(N^2)..
-
연쇄 행렬 곱셈 (Matrix chain multiplication) :: 마이구미알고리즘 2017. 11. 27. 00:14
이 글은 연쇄 행렬 곱셈(Matrix chain multiplication) 알고리즘을 다룬다.동적계획법이 기반으로 된 알고리즘이다.위키 내용과 관련 알고리즘 문제를 참고했다. (위키는 번역본이 아직 없다)참고 링크 - https://en.wikipedia.org/wiki/Matrix_chain_multiplication 연쇄 행렬 곱셈은 최적화 문제를 동적계획법(DP) 을 이용하여 해결할 수 있다.행렬의 순서가 주어질 때, 행렬의 곱셈에서 가장 효율적인 방법을 찾는 것이 목표이다.문제는 실제로는 곱셈을 수행하는 것이 아니라 행렬의 곱셈 순서를 결정하는 것이다. 행렬 곱셈에 있어서, 괄호를 어디에 넣어도 같은 결과를 만든다.이것이 의미하는 것은 예를 통해 확인해보자.4개의 행렬 A, B, C, D 를 가..
-
디스조인트-셋(disjoint-set) :: 마이구미알고리즘 2017. 11. 5. 17:27
이 글은 디스조인트-셋(disjoint-set) 자료구조를 다룬다.유니온-파인드(union-find) 라고도 불리고, 머지-파인드-셋이라고도 불리는 자료구조이다.위키백과 - 디스조인트-셋 디스조인트-셋은 해석하면 서로소 집합이라고 표현할 수 있다.서로소 집합이란, 공통된 원소가 없는 집합으로써, 교집합이 공집합인 집합이라고 보면 된다. 디스조인트-셋을 활용하기 위해서는 다음과 같은 정의를 확실히 이해해야한다. 많은 상호 배타적 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조. "상호 배타"와 "독립"을 혼동해서는 안된다.독립은 집합으로 표현하면 다음과 같다. A ∩ B = 0, A ∪ B = U A와 B 사이에는 어떠한 관계도 존재하지 않다는 것을 알 수 있다.상호 배타는 다음과 같..
-
동전 교환 관련 문제 접근 :: 마이구미알고리즘 2017. 2. 23. 12:07
이번 글은 "동전 교환" 에 관한 알고리즘을 다뤄볼 것이다.백준 알고리즘 사이트에서 알고리즘 분류에서 "동전 교환"을 볼 수 있다.2293번 동전 1, 2294번 동전 2, 11047번 동전 0 문제를 통해 다룬다.동전 0 - https://www.acmicpc.net/problem/11047동전 1 - https://www.acmicpc.net/problem/2293동전 2 - https://www.acmicpc.net/problem/2294 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.) 생각해볼 수 있는 방법은 각 동전에 대한 경우의 ..
-
LCS(최장 공통 부분 수열) 알고리즘 :: 마이구미알고리즘 2017. 2. 17. 15:09
이번 글은 LCS(Longest Common Subsequence) 알고리즘은 다뤄본다. 최장 공통 부분 수열(LCS)은 LIS 최장 증가 부분 수열과 비슷하게 생각하면 된다.LCS 또한 LIS와 같이 DP(동적 계획법)을 기반으로 한다.LCS 알고리즘을 통해 두개의 문자열을 비교하여 공통 부분 수열의 길이를 구할 수 있다. 주의할 점은 LCS는 Longest Common Substring과 Longest Common Subsequence이 존재한다.공통 부분 문자열(Longest Common Substring), 공통 부분 수열(Longest Common Subsequence)이라고 말할 수 있다.2개는 다른 의미를 가지고 있기 때문에 구분해야한다.차이점은 연속 여부이다. 최장 공통 문자열의 길이는 3..
-
효욜적인 약수 개수 구하기 알고리즘 :: 마이구미알고리즘 2017. 2. 9. 18:06
이번 글은 약수를 구하는 알고리즘을 다뤄본다.약수 구하는 방법은 어렵지 않다.하지만 조금만 응용된 약수 관련 문제라면 순수한 방법으로는 시간이 너무 오래걸린다.더 효율적인 방법을 알아볼 것이다. 약수(約數, divisor)는 어떤 수를 나누었을 때 나머지가 0인 수를 말하며, 배수 관계와 서로 반대되는 개념이다. 약수는 보통 정수에 대해 정의되지만, 일반화하여 정역에 대해 정의하기도 한다. 관련 문제를 보자. (약수 문제)기본적인 문제로써, 주어진 수(N)의 약수의 개수를 구하는 문제이다.가장 순수한 방법으로는 1부터 N까지 N의 나머지를 구해 0이라면 약수라고 판단한다. int n = sc.nextInt(); int cnt = 0; for(int i = 1; i
-
그리디(Greedy) 알고리즘 :: 마이구미알고리즘 2017. 2. 8. 22:07
이번 글은 그리디(Greedy) 알고리즘에 대해 다뤄본다.그리디 알고리즘은 탐욕 알고리즘, 욕심쟁이 알고리즘으로도 불린다. 그리디 알고리즘은 간단히 정의하자면 아래와 같이 표현할 수 있다. 경우의 수가 존재할 경우, 경우를 선택해야할 때 최선이라고 생각하는 경우를 선택하는 알고리즘이다. 여기서 최선이라고 생각하는 경우가 무엇인가?그것을 이해하면 그리디 알고리즘을 이해할 수 있다.쉽게 말하면, 전체를 고려하지 않고, 그 순간에서의 최선을 말한다.즉, 그때그때 더 좋아보이는 쪽을 선택하는 것이다.그렇기에 최종적으로는 그 선택이 최적이라고 확신할 수 없다. (문제에 따라 최적이라고 확신할 수도 있다.) 예를 들어, 지금은 초코파이를 먹을 수 있지만, 10분 후면 랍스타를 먹을 수 있다.그리디 알고리즘의 경우에..
-
플로이드 와샬 알고리즘 :: 마이구미알고리즘 2017. 1. 27. 22:36
이번 글은 플로이드 와샬 알고리즘에 대해 다뤄본다.동적계획법을 기반으로 구현되는 알고리즘이다.위키백과의 정의를 보자. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. 정의를 보다시피 최단 경로를 찾기에 좋은 알고리즘이다.시간복잡도는 3개의 반복문을 통해 O(n^3) 이다. 플로이드 알고리즘은 3개의 반복문이면 구현된다.코드를 보면 굉장히 짧고 간단하다. for (int k = 0; k <..