알고리즘

[C++] 계단 오르기 알고리즘

예로 들어서 n이 3이라면 꼭대기에 도달 하는데까지 총 3가지의 방법이 존재한다. 다른 예시로는 n = 1 // 한 가지의 방법만 존재하므로 1을 출력 n = 2 // 2, (1 , 1)과 (2) n = 4 // 5, (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2) 재귀를 사용한 방식 방법의 수(n) = 방법의 수(n - 1) + 방법의 수(n - 2) 피보나치 수열을 이용하여 구할 수가 있다. 방법의 수(1) = 피보나치(2) = 1 방법의 수(2) = 피보나치(3) = 2 방법의 수(3) = 피보나치(4) = 3 int fib(int n) { if (n

sort() 함수에서 쓰여지는 정렬 알고리즘 (Intro 인트로, Tim 팀)

일반적으로 시간 복잡도를 기준으로 sort 알고리즈므이 성능을 판단하지만, 실제로는 지역성이나 실 데이터의 분포 등 고려할 것들이 많다. 언어마다 default로 사용하는 sort들이 정해져있다. C++ : Intro Sort c++의 std::sort로 사용되고 퀵 정렬, 삽입 정렬, 힙 정렬로 이루어져 있다. 특징 기본적으로 퀵 정렬로 시작을 한다. 정렬할 element가 Threshold(일반적으로 16) 미만일 때는, 삽입 정렬로 수행된다. 재귀 depth가 정렬되는 element 수(n)과 비교해 log N보다 많아지면 힙 정렬로 수행된다. 퀵, 삽입 정렬은 지역성의 이점을 얻는 알고리즘(배열의 경우)으로 유명하다. 특히, 삽입 정렬은 참조 지역성을 아주 잘 만족한다고 한다. 삽입 정렬의 경우 ..

Brute Force (브루트 포스) 알고리즘

개념 브루트 포스를 사전적 의미로 찾아본다면 아래와 같다. 브루트(Brute) : 무식한 + 포스(Force) : 힘 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 장단점 장점) 알고리즘을 설계하고 구현하기 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 단점) 알고리즘의 실행 시간이 매우 오래 걸린다. 메모리 효율면에서 매우 비효율적이다. 종류 선형 구조) 순차 탐색 비선형 구조) 백트래킹, dfs, bfs 예시 만약 10자리 비밀번호 자물쇠가 있다고 가정해보자. 이 자물쇠를 풀..

[C++] 개인적인 (MST 알고리즘) 크루스칼 & 프림 구현

사용할 데이터는 다음과 같다. 결과) 17 1 2 2 2 6 7 3 2 3 3 6 8 4 3 5 4 2 3 4 1 1 5 1 4 5 4 9 공통으로 쓰여짐 // 간선 개수 const int edge = 9; struct sNode { public: int from = 0, to = 0, weight = 0; /*sNode() = default; sNode(int from, int to, int weight) : from(from), to(to), weight(weight) { }*/ bool operator(const sNode& ref) const { return weight > ref.weight; } bool operator==(const sNode& ref) const { return from =..

냅색 - meet in the middle (밋 인 더 미들) 알고리즘

n

Boyer-Moore (보이어무어) 알고리즘 / 문자열 탐색

개념 기존 고지식한 알고리즘과, KMP 알고리즘 혹은 지금까지 봐왔던 알고리즘들은 대부분 처음부터 비교해 나갈 것이지만 보이어-무어 알고리즘은 뒤에서부터 비교해나간다. 뒤에서부터 비교를 진행해 나가다 비교 값이 서로 다를 시 테이블을 참조해 나아간다. 아래는 보이어-무어 알고리즘으로 비교해 나아가는 이미지다. 뒤에서 비교하다 index 3번이 다르다는 것을 확인 후 테이블을 참조한다. 테이블을 참조 후 다음 비교할 위치로 건너뛴다. 그 다음 값을 보면 index 5, 6번이 다르지만 보이어-무어 알고리즘은 뒤에서부터 비교하므로 테이블 참조 시 index 6번에 대한 값을 참조하여 다음 비교 위치로 넘어긴다. 총 2번의 이동만으로 원하는 값을 찾아냈다. 만약 고지식한 알고리즘이었다면 2번 이동했을 때쯤 i..

KMP (문자열 중 특정 패턴을 찾아내는 탐색) 알고리즘 C++ 구현

개념 KMP 알고리즘은 문자열에서 특정 패턴을 효율적으로 찾을 수 있다. 살펴볼 문자열의 길이가 N, 찾고 싶은 패턴의 길이가 M이라면 O(N+M)의 시간 복잡도를 가지는 매우 효율적인 알고리즘이다. KMP 알고리즘이 얼마나 효율적인지 알기 전에, 모든 문자열을 일일이 비교하는 경우를 살펴보자. 모든 문자열을 일일이 비교하는 경우(브루트 포스 : Brute Force) "ABCDABCE"라는 문자열에서 "ABCE"라는 패턴을 찾는다고 해보자. 모든 문자열을 일일이 비교한 경우엔 아래와 같이 탐색을 진행할 것이다. 이처럼 모든 문자열을 비교하는 브루트 포스(Brute Force) 방식은 텍스트의 길이를 N, 찾고자 하는 패턴의 길이를 M이라고 했을 때 시간 복잡도가 O(NM)이다. 이는 매우 비효율적이다...

페이지 교체 알고리즘

가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 backing store에서 메모리로 적재를 하고 사용하지 않는 부분은 그대로 둔다. 하지만 필요한 페이지만 올린다고 하더라도 메모리가 나중에는 가득 차게 되고 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있다. 메모리가 가득 차면 추가로 페이지를 가져오기 위해 어떤 페이지는 page-out을 해야 하고 그 빈 공간에 필요한 페이지가 page-in을 해야 한다. 여기서 어떤 페이지를 backing store로 page-out을 시킬 것인지에 대해서 고민을 하게 된다. page-out이 되는 페이지를 victim page라고 부르는데 기왕이면 수정이 되지 않는 페이지를 선택하려고 한다. 만약 수정이 된다면 메인 메모리에서 내보낼 ..

SPFA (Shortest Path Faster Algorithm)

개념) 다익스트라 알고리즘은 O(ElogV)로 동작하며 (이론적으로는 O(E+VlogV) 음수 간선은 처리할 수 없다. 일반적으로 가장 많이 사용된다. 플로이드-와셜 알고리즘은 O(V3)으로 동작하며, 모든 정점들간의 거리를 모두 구한다는 특징이 있다. 음수 간선이 있어도 잘 동작하며 음수 사이클의 여부를 판단할 수 있다. 벨만-포드 알고리즘은 O(VE)이며 음수 간선이 있어도 잘 동작하고, 음수 사이클의 여부를 판단할 수 있다. 이제 SPFA 알고리즘에 대해 알아보자. SPFA 알고리즘은 벨만-포드 알고리즘의 성능을 향상시킨 것으로, 음수 간선이 있는 그래프에서 최단경로를 빠르게 구할 수 있다. 최악의 시간복잡도는 여전히 O(VE)이지만 실제로는 O(V+E) 정도로 동작한다. 벨만-포드 알고리즘에서는 ..

알고리즘 대회 (Competitive Programming)에서 애드혹(Ad-Hoc) 문제란?

일반적으로 경쟁적 프로그래밍(Competitive Programming) 대회, 이른바 알고리즘 대회에서는 종종 애드혹(ad-hoc) 문제가 출제된다. 일반적으로 애드혹 문제라고 하는 것은 해당 문제를 풀기 위해 잘 알려진 정교한(sophisticated) 알고리즘을 적용하지 않고 해결할 수 있는 유형의 문제를 일컫는다. 이러한 유형의 문제는 손으로 직접 해당 문제를 해결하기 위한 (해당 문제만을 위한) 아이디어를 찾아서 문제를 해결할 수 있다. 애드혹 문제들을 굳이 분류하자면 단순히 지시(instruction)를 따르면 되는 구현 유형이나 그리디 유형 알고리즘 혹은 수학 유형으로 분류할 수 있는 경우가 많다. 즉 그 문제를 풀기 위한 창의적인 아이디어를 떠올려야 하는 경우에 애드혹 문제라고 한다. 안경..