알고리즘

카라츠바의 빠른 곱셈 (Karatsuba algorithm)

카라츠바의 빠른 곱셈 알고리즘은 수백, 수만자리나 되는 큰 두개의 정수를 곱하는 알고리즘이다. 필요성 카라츠바 알고리즘을 소개하기에 앞서, 두자릿수 이상의 두 수를 곱하는 과정은 다음과 같다. 이 알고리즘의 시간복잡도는 두 정수의 길이가 모두 n이라고 할 때 O(n^2)이다. 2중 for문을 이용하고 있으니 이 점을 이해하기는 어렵지 않을 것이다. 카라츠바 알고리즘은 이 시간복잡도를 O(n^log(3)) 까지 낮춰주기 위해 사용된다. log(3) = 1.585...이므로 O(n^2) 보다 훨씬 적은 곱셈을 필요로 한다. 만약 n이 10만이라고 하면 곱셈 횟수는 대략 100배 정도 차이가 난다. 아이디어 자릿수가 n인 두개의 수 a,b를 단순히 곱하기 위해서는 O(n^2)이 소요되지만, 덧셈과 뺄셈을 하는..

탐욕 / 그리디 알고리즘 (Greedy Algorithm)

Greedy Algorithm 탐욕 알고리즘(그리디 알고리즘)은 특정 경우들 중 하나를 선택할 때, 그 순간에 가장 최적의 경우를 선택하는 알고리즘이다. 목적지까지 최단 경로로 가야 하는 상황을 예로 들어보자. 목적지를 향해 가던 중, 갈림길을 만났다. 그리디 알고리즘에서는, 다음과 같은 갈림길들 중 현재 상황에서만 최적인 경우를 선택한다. 따라서 위 그림에 그리디 알고리즘을 적용한다면, 직진을 하게 될 것이다. 하지만 만약 직진으로 간 다음 경유지에서 목적지까지의 거리가 100km이고, 다른 두 갈림길의 경유지에서 거리는 10km라면 어떻게 될까? 그리디 알고리즘을 통해 최적의 경우를 선택했지만, 결과적으로는 직진을 선택했기 때문에 목적지까지 최단경로로 갈 수 없게 된다. 이와 같이 그리디 알고리즘은 ..

C++ MST 크루스칼 + 프림 알고리즘 코드

이미지 출처) Minimum Spanning Tree - Kruskal - Algorithms for Competitive Programming (cp-algorithms.com) 정답) 1 + 2 + 3 + 4 + 7 = 17 순회하는 순서가 추가되는 노드 순서에 따라 상이할 수 있음. 입력 데이터 From 1 To 2 Value 2 Edge형 구조체에 담음, int from, to, val; 9 1 2 2 1 4 1 1 5 4 2 4 3 2 3 3 2 6 7 3 6 8 4 3 5 5 4 9 0 0 0 크루스칼 알고리즘 핵심 포인트) 모든 부모 노드들을 포함하고 있을 int형 벡터와 Edge형 벡터, 한 방향만 연결. #include #include #include using namespace std;..

1e9? 2e9? 알고리즘 문제해결

알고리즘 문제를 풀다 보면 1e9, 2e9라는 코드를 자주 볼 수 있다. 1e9 = 1*109 = 1000000000, 2e9 = 2*109 = 2000000000 위와 같이 간단하게 표현하는 방법이다. 특히, 2e9는 int 범위내에서 무한대 값을 나타내기 위해 사용하는 경우가 많다. 1e9? 2e9? 알고리즘 문제해결 (tistory.com)

비트마스크 (BitMask) 알고리즘

1. 비트마스크(BitMask)란? - 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. - 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다. - 보통 어떤 비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말한다. 2. 비트마스크의 장점 1. 수행 시간이 빠르다. 비트마스크 연산은 bit 연산이기 때문에 O(1)에 구현되는 것이 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 동작하게 된다. 다만, 비트마스크를 이용하는 경우에는 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 적은 경우에는 속도에 큰 차이가 없지만, 연산 횟수가 늘어날수록 ..

슬라이딩 윈도우 알고리즘 (Sliding Window)

( 슬라이딩 윈도우 알고리즘 간단 예제 ) 1, 2, 3, 4, 5, 6, 7 로 이루어진 숫자 배열에서 A[i] + A[i+1] + A[i+2] 형식으로 연속적인 3개의 숫자의 합의 최댓값을 구한다고 가정해보면 아래 5가지의 경우의 수가 나온다. [1, 2, 3], 4, 5, 6, 7 1, [2, 3, 4], 5, 6, 7 1, 2, [3, 4, 5], 6, 7 1, 2, 3, [4, 5, 6], 7 1, 2, 3, 4, [5, 6, 7] 다음으로 합을 계산하는 고정된 크기의 배열의 변화를 보면 [1,2,3] => [2,3,4] => [3,4,5] ... => [5,6,7]이다. 그렇다면 어떻게 최소한의 계산으로 다음 배열의 합을 구할 수 있을까? - 먼저 처음 배열 [1,2,3] 의 합을 구한다. =..

각 정렬의 특징 및 장단점 & 시간복잡도 + 코드

선택정렬 (Selection Sort) 선택정렬은 앞에서부터 차례대로 먼저 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 진행하는 정렬 방법이다. 코드가 직관적이기에 구현도 비교적 간단하다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하며 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점이다. 따라서 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있다. 선택 정렬이 가장 적합한 자료 상태는 역순 정렬이다. 즉, 내림차순으로 정렬되어 있는 자료를 오름차순으로 재정렬할 때 최적의 효율을 보여준다. 반대로 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준..

C++ 다익스트라(Dijkstra) 알고리즘 개념 및 구현 (무방향 그래프)

다익스트라 알고리즘 다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 참고로 그래프 알고리즘 중 최소 비용을 구하는 데는 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다. 동작 단계 ① 출발 노드와 도착 노드를 설정한다. ② '최단 거리 테이블'을 초기화한다. ③ 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다. ④ ..

[C] 이진 탐색 (Binary Search) 알고리즘 개념과 예제

이진 탐색 이진 탐색은 오름차순으로 정렬되어있는 데이터에서 원하는 값(타겟 넘버)의 위치를 찾아내는 알고리즘이다. 여기서 이진(Binary)는 우리가 알고있는 그 이진 코드 (0101001...) 가 아니라 데이터를 반(2개)으로 나누어서 비교하고 찾는 방식이여서 이진 탐색이라고 한다. 이진 탐색의 알고리즘 진행방식은 아래와 같다. 정렬되어있는 데이터의 중간 값을 임의의 값 X로 정함 타겟 넘버의 값과 X를 비교 타겟 넘버의 값이 X보다 크다면, 타겟 넘버는 데이터에서 X보다 우측에 위치해 있으니 반으로 나눈 데이터의 우측에서 1번 과정부터 다시 시작 타겟 넘버의 값이 X보다 작다면, 타겟 넘버는 데이터에서 X보다 좌측에 위치해 있으니 반으로 나눈 데이터의 좌측에서 1번 과정부터 다시 시작 이진 탐색 예..

투 포인터 알고리즘(Two Pointers Algorithm)

1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태의 알고리즘이다. 절대 답이 되지 않는 경우는 계산하지 않아 시간을 단축시켜준다. Q. 배열에서 부분 배열의 합이 M이 되는 경우의 수를 구하여라! A1. 가장 쉽고 단순한 방법으로는 이중 for문을 이용해서 모든 경우의 수를 구할 수 있다. 시간 복잡도 O(N^2) A2. 투 포인터 알고리즘을 이용하면 시간복잡도를 O(N)으로 단축시킬 수 있다. 주로 적용되는 문제 유형 - 연속된 수들의 합 - 부분 배열의 합 풀이 방법 1. 포인터 2개가 같은 방향으로 진행해 나아가는 것 2. 포인터 2개가 양끝에서 반대로 진행하는 것 대표 문제 풀이 1 - 백준 [2003] 수들의 합 2 www.acm..