CS

카라츠바의 빠른 곱셈 (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)이 소요되지만, 덧셈과 뺄셈을 하는..

아스키코드(ASCII Code) - 컴퓨터의 문자 처리 원리

컴퓨터가 이해하는 언어는 0과 1(1bit)이다. 2진수로 데이터를 처리한다. 컴퓨터는 전기신호를 받아들이므로 전기의 OFF, ON 두 가지 상태(0과 1)로 모든 걸 표현하기 때문이다. 0과 1의 두 가지 상태를 나타내는 단위를 bit라고 한다. 그러나 1bit만으로는 표현할 수 있는 게 0, 1 단 두 개뿐이니, 더 큰 수를 표현하기 위해 8개의 bit를 묶어서 1byte를 사용한다. 컴퓨터가 데이터를 저장하는 최소 단위가 바로 이 byte다. 1byte는 8개의 bit니까 2의 8제곱, 즉 0~255(256개)의 데이터를 저장할 수 있다. 중요한 것은 더 큰 수를 표현할 수 있게 되었더라도 컴퓨터가 인식하는 것은 숫자라는 점이다. 컴퓨터는 0과 1 이외에는 아무것도 인식할 수 없기 때문이다. 그렇다..

[C++] Dynamic Programming (동적계획법) / Top-Down (탑다운)과 Bottom-Up (바텀업) 방식

I. 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다는 것이 핵심이다. 즉, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. (우리가 평소에 문제를 풀이할 때 효율적인 방법으로 고안할 필요가 있다.) 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운-하향식, 바텀업-상향식)으로 구성된다. 매우 비효율적인 문제더라도 다이나믹으로 획기적으로 시간을 줄일 수 있다. 다이나믹 프로그래밍은 조건을 만족해야 사용할 수 있다. 최적 부분 구조 - 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제를 모아서 큰 문제를 해결 중복 부분 문제 - 동일..

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

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

[C++] 이분 탐색 (Binary Search)

이분 탐색(Binary search)이란? - 정렬된 리스트(배열)에서 원하는 값(target)의 존재 여부(존재 위치)를 찾는 알고리즘. - 반드시 리스트(배열)를 정렬해서 사용해야 한다는 단점이 있다. - 탐색할 때마다 검사 범위가 절반으로 줄어든다. - 재귀적인 방법, 반복문, STL를 이용하여 이분 탐색(Binary Search)을 실행할 수 있다. - Time Complexity : O(log N) 변수 설명 1. int low & int high 검사 범위의 시작점, 끝점의 인덱스를 가리키기 위한 변수. left는 시작점을, right를 끝점의 인덱스를 가리킨다. // nums에 수들이 들어가있다고 가정 vector nums; int low = 0; // 초기 세팅: 제일 앞 인덱스 int h..

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;..

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) / 장단점, 구현 및 시간복잡도

DFS의 장/단점 장점 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다. 깊이가 무한히 깊어지면 스택오버플로우가 날 위험이 있다. (깊이 제한을 두는 방법으로 해결가능) DFS의 구현 그래프를 인접 행렬(adjacency matrix)로 구현했는지, 인접 리스트(adjacency list)로 구현했는 지에 따라 구현방법이 달라진다. 인접 행렬로 구현했을 경우 [시간복잡도] DFS 하나당 N번의 loop를 돌게 되므로 O(n)의 시간복잡도를 가진다. 그런데 N개의 정점을 모두 방문 해야하므로 n*O(n)이므로 O(n..

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

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

누적 합 (Prefix Sum)

계산 양을 줄여서 시간적으로 많은 이득을 볼 수 있는 알고리즘이다. 1. 기본 원리 1) 1차원 배열 1차원 배열에서 i번째부터 j번째 인덱스까지 k를 더한 것을 기록하려면, 새로운 배열의 i번째 인덱스에 k를 더하고 j+1번째 인덱스에 k를 빼면 된다. 새로운 배열의 크기는 기존 배열 크기보다 하나 이상 크게 만든다. 예를 들어 크기가 5인 배열에서 0번째부터 2번째 인덱스까지 N을 빼고 싶다면 다음과 같이 누적 합 배열을 만든다. { -N, 0, 0, N, 0, 0 } 위 새로운 배열을 0번째부터 마지막 인덱스까지 누적 합을 계산하게 되면 다음과 같다. 추가로 1번째부터 2번째 인덱스까지 M을 더하고 싶다면 누적 합 배열에 값을 추가한다. { -N, -M, 0, N, M, 0 } 다시 0번째부터 마지..

프로그래밍 언어와 빌드 과정 [Build Process]

⦁ Build 란? 컴퓨터는 근본적으로는 0과 1밖에 모른다. 우리가 작성하는 코드들은 거의 대부분 고급언어를 사용하기 때문에 결국에는 컴퓨터(CPU)가 이해할 수 있도록 번역을 해주어야한다. (C, Java, C++ 등 어셈블리를 제외한 대부분 언어가 고급언어다.) 컴퓨터가 이해하는 언어를 기계어라고 하는데, 우리가 만든 소스 코드가 컴퓨터 입장에서는 해외판 책이 되는 것이고, 이 책을 기계어(machine code)로 번역하여 컴퓨터에서 이해할 수 있는, 즉 실행 가능한 파일로 만드는 과정을 빌드(Build) 라고 한다. ⦁ Build Process 1. Compile Type 이렇게 한 번에 번역하는 언어들을 보통 Compile Language 라고 하는데, 대표적으로 C, C++, Go 언어가 있..