algorithm

휴리스틱 알고리즘 (Heuristic Algorithm)

우리가 문제 해결 시 흔히 사용하는 동적 계획법(DP) 또는 분할 정복과 같은 완전 탐색에 기초한 디자인 패러다임은 사실 실생활에서 쓰기엔 매우 한정적이다. 예를 들어, 인공지능 체스 프로그램을 알고리즘으로 짠다고 할 때 우리가 가장 먼저 떠올릴 수 있는 것은브루트 포스(brute force) 방식이다. 즉, 가능한 모든 말의 움직임을 다 해보는 것이다. 하지만 이 방식은 어림도 없는게 움직일 수 있는 말과 이동 가능한 칸이 너무 많기 때문에 만약 이 방식으로 프로그램을 개발했다고 하면, 죽을 때까지 게임이 끝나지 않을 것이다. (경우의 수가 10^120 가지라고 한다.)그렇다고 해서 분할 정복 기법을 사용하자니 적절한 분할 방법이 생각나질 않고 동적 계획법을 사용하자니 메모리가 턱없이 모자르다. 결국 ..

[C++] 두 배열을 비교할 수 있는 함수 equal

1. equal C++의 알고리즘 관련 여러 함수들이 담긴 헤더 에서의 equal 함수는 다음과 같은 두 가지 구조를 가진다. 1] equality - bool equal (InputIterator first1, InputIterator last1, InputIterator first2) 2] predicate - bool equal (InputIterator1 first1, InputIterator last1, InputIterator first2, BinaryPredicate pred) equal은 쓰임에 따라 3개 혹은 4개의 인자를 받는다. InputIterator first1 : 비교할 첫 번째 배열이나 어떤 container 자료형의 시작부 혹은 포인터 InputIterator last1: 비..

탐욕 / 그리디 알고리즘 (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;..

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

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

[C++] sort , stable_sort

sort()함수 #include 헤더 포함 - default 는 오름차순이다. - 정렬 조건을 주고 싶을때 함수를 만들어 함수이름 자리에 넣어주면 된다. (필수 X ) sort(시작주소, 끝주소+1, 함수이름 ) 1) 기본 배열의 sort 배열의 이름은 배열의 시작 주소값이므로 arr과 arr+ (요소의 개수) 를 단순하게 인자값으로 넣어주면 된다. #include #include using namespace std; int main() { int arr[5] = {3,7,1,9,5}; sort(arr, arr + 5); for (int i = 0; i < 5; i++) { cout

[C++] min max 함수 (algorithm 라이브러리)

0. std::min & std::max 1. ①비교할 값들이 많거나, ②ArrayㆍVector와 같은 일련의 컨테이너에 저장되어 있다면, 최소값ㆍ최대값을 구하기 위해 min_element 또는 max_element 함수를 사용할 수 있다. (해당 함수에 대해서는 나중에 포스팅 하겠다.) 2. std::min와 std::max는 algorithm 라이브러리에 3가지 형태로 존재한다. 『① Default Constructor 』 『② Custom Constructor 』 『③ Initializer List Constructor 』 가 이에 해당한다. 1. std::min & std::max 『① Default Constructor 』 함수 원형 /* -- Default Constructor -- */ #i..

스위핑 알고리즘 (Sweeping algorithm)

스위핑 알고리즘(sweeping algorithm)은 그냥 어떤 선이나 공간을 한쪽에서부터 싹 쓸어버린다는 건데 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 뭔가를 해 주면 정답이 구해지는 형태다. 추천 문제 2170 선 긋기 2836 수상 택시 10000 원 영역 5419 북서풍 3392 화성 지도 10534 City Park

최소 스패닝 트리 (MST) / 크루스칼 알고리즘 (Kruskal Algorithm)

최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽의 붉은 간선으로 이어진 부분 그래프들은 모두 스패닝 트리에 해당한다. 즉, 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종이므로, V개의 모든 정점을 연결하는 간선의 수는 V - 1개이다. 최소 스패닝 트리(MST)는 이러한 스패닝 트리 중, 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruskal, Prim 알고리즘이 존재한다. 크루스..

C++ _if STL 알고리즘 함수 (파라미터 _Pr _Pred) > 조건자 (Predicate)

참고할만한 부분은 _if로 끝나는 함수들만 매개변수(조건자)로 넘길 수 있다는 점, sort 함수 예외. 참고 사이트 : https://en.cppreference.com/w/cpp/algorithm #include #include #include #include #include using namespace std; bool Is_one(int _val) { return _val == 1; } class Test { public: bool operator()(int i) { return i % 4 == 0; } }; struct s_test { public: bool operator()(int i) { return i % 2 == 0; } }; int main() { // 파라미터 _Pr _Pred > ..