반응형

알고리즘 공부/알고리즘 17

바이너리 서치 BinarySearch 이진 탐색 C++ Parametric Search

개요정렬된 데이터에서 탐색 범위를 반씩 줄여가면서 빠르게 특정값을 찾는 알고리즘데이터가 주어졌을때 우선 정렬이 된 상태로 만들어 주어야 한다. algorithm을 include하고 sort를 진행한다.이진 탐색 Flow탐색 범위에서 시작 지점 index를 left, 종료 지점 index를 right로 지정한다.(left + right) / 2를 통해 left와 right의 중간 index, mid 값을 구해준다.찾으려는 수와 배열 내에서 mid 인덱스를 가진 수를 비교해 준다.만약 찾으려는 수가 mid 인덱스를 가진 수보다 작을 경우 mid보다 왼쪽, 클 경우 오른쪽에 있는 것이다.만약 왼쪽에 있을 경우 left는 그대로 두고 right를 mid로 교체해 준다.오른쪽에 있을 경우 right는 그대로 두고..

다익스트라 Dijkstra C++

개요특징특정 노드에서 연결 되어 있는 모든 노드까지의 최단 거리를 구할 수 있다.가중치는 양수여야만 하며 음수일 경우 해당 간선을 계속 방문하게 되어 루프에 빠지게 된다.양방향 및 단방향 그래프 및 2차 배열 형태에서도 에 모두 사용 가능하다.동작 요약모든 노드 까지의 거리를 2e9 혹은 INT_MAX와 같은 값을 사용하여 최대치로 설정한다.시작점 노드 자기 자신 까지의 거리를 0으로 설정하고, 우선순위 큐에 자신을 추가한다.첫 탐색 시 자신과 연결된 인접 리스트를 참고하여 해당 노드까지의 거리가 현재 거리보다 짧다면 갱신해 주고 해당 노드를 우선순위 큐에 넣어준다.이후 우선순위 큐에 있는 노드와 연결된 인접 리스트를 참고하여 거리 정보가 최소가 되도록 갱신해 주는 작업을 반복한다.우선순위 큐에 더 이상..

merge, lower_bound, upper_bound C++

개요 C++ 표준 라이브러리에서 merge, lower_bound, upper_bound는 모두 정렬된 시퀀스를 처리하는 데 사용되는 알고리즘이다. algorithm을 include 해야 사용할 수 있다. 1. merge 알고리즘merge는 두 개의 정렬된 시퀀스를 병합하여 하나의 정렬된 시퀀스를 생성하는 알고리즘, 두 입력 시퀀스는 정렬되어 있어야 하며, 병합된 결과도 정렬된 상태로 유지된다.사용법templateOutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );매개변수first1, last1: 첫 번째 정렬된 시퀀스의 범..

우선순위 큐 Priority Queue C++

개요1. Queue일반적인 큐의 경우 선입 선출을 통해 먼저 들어왔던 데이터가 먼저 처리되는 특성을 가진다.큐 내에 {1, 2, 3, 4, 5} 가 존재한다면, 6을 push하고 front에 존재하는 값을 pop 한다면 {2, 3, 4, 5, 6}이 되고, 6을 사용하기 위해선 앞에 존재하는 2, 3, 4, 5가 모두 pop 되어야 6을 pop 할 수 있다. 2. Priority Queue기본적인 큐에서 특정 조건으로 인해 큰 값으로 정렬 되어 있는 큐이다.만약 큐에 {5, 4, 3, 2, 1}이 존재한다고 가정했을때 6을 push한 후 front에 존재하는 값을 pop 한다면, 6이 pop이 될 것이다.pq의 기본형은 내림차순 정렬이지만, 특정 compare 함수를 작성할 경우 우선순위를 다양하게 설정..

최소 신장 트리 MST, Union-Find C++

개요1. 그래프와 트리의 차이점트리는 무방향 간선을 가지며 사이클이 없고 특정 노드 간 경로가 유일한 그래프다.그래프 내에는 여러개의 신장 트리가 있을 수 있다. 2. 신장 트리 (Spanning tree)N개의 노드를 N - 1개의 간선으로 모든 노드가 연결된 트리 3. 최소 신장 트리 MST가중치가 최소인 신장 트리 = Minimum Spanning Tree간선에 가중치가 주어졌을때 간선의 합이 최소인 Spanning Tree가 최소 신장 트리가 된다.  아래와 같은 간선간 가중치가 있는 그래프가 있다고 가정 해보자노드의 개수는 9개이므로 8개의 간선으로 9개의 노드를 모두 이을 수 있는 가중치의 최소값은 얼마일까? 각 가중치가 오른쪽과 같은 간선을 선택하여 더하면 20 + 21 + 1 + 13 + ..

유니온 파인드 Union-Find C++

개요Union-Find데이터 단위를 그룹단위로 나누어 관리하는 알고리즘 Union으로 그룹을 합치고, Find로 찾는 구조이다.중간에 어떤 노드가 있는지 전혀 궁금하지 않고, 그룹을 합치고, 특정 노드가 어떤 그룹에 속해 있는지 파악하는 것에 초점이 맞혀져 있다.교집합이 없는 서로소 집합(disjoint set), 그룹을 합치는 것은 있으나 그룹을 쪼개는 것은 없다. Union일정 노드들을 그룹으로 묶고 부모 노드가 대표가 된다.Union(1, 2), Union(3, 4), Union(5, 6)위와 같이 묶은 경우 각 묶음은 하나의 그룹이 된다. Find단순하게 해당 노드를 찾으라는 의미가 아닌, 해당 노드가 속한 그룹을 찾는다. 1. 초기 단계모든 노드들이 대표인 상태  노드123456부모123456 ..

BFS 너비 우선 탐색 C++

개요그래프 : 노드와 간선으로 이루어진 자료구조완전 탐색 : 특정 노드에서 갈 수 있는 모든 노드를 확인하는 방법DFS : 깊이 우선 탐색BFS(Breadth First Search) : 넓이 우선 탐색 -> 가까운/인접한 노드부터 탐색 즉, 발견되는 노드부터 탐색한다. 위 그래프를 DFS로 탐색 한다면 0 -> 1 - > 3 -> 4 -> 2 순으로 탐색하게 된다. (깊이 우선)BFS로 탐색한다면 결과는 0 -> 1 -> 2 -> 3 -> 4 가 될 것이다. (넓이 우선, 가까운것 부터 탐색) BFS 진행 방식대기열 준비(Queue 자료 구조를 선택)시작 노드에 큐 삽입큐(대기열)에 맨 앞 노드부터 추출 및 확인(now) | 실제 탑승now를 기준으로 연결되어 있는 노드들을 큐에 등록(next 후보 검..

그래프, 트리, DFS C++

개요그래프정점과 정점사이의 상관관계를 나타내는 자료구조 노드와 간선으로 이루어져 있다.1. 그래프의 방향그래프는 방향이 있는 그래프와 방향이 없는 그래프로 나뉘어 진다. (양방향과 단방향)2. 가중치각 노드간 간선에 가중치가 있을 수 있다. (거리 등) 3. 트리그래프의 한 종류로 LEVEL이 설정되어 있는 그래프이다. LEVEL 0에 ROOT 노드가 있으며, 하위 노드는 자식이 된다. 반대로 자식 입장에서 ROOT 노드는 부모 노드이며, 자식간의 관계는 형제 노드가 된다.트리의 특징방향 그래프만 존재루트 노드가 한개만 존재계층 형식으로 비순환 그래프4. 인접 행렬위 트리 노드를 인접 행렬로 표현하면 아래와 같이 표현할 수 있다.노드12345101001200110300000400000500000 출발지 ..

백트래킹(2) 순열, 조합, N Castle C++

개요1. 중복 순열중복이 가능한 N개 중에서 R개를 선택하는 경우의 수(순서를 고려한다, 중복 조합)별다른 판별조건 없이 모든 수를 도출해 주면 된다.1 1 21 2 12 1 1 2. 순열서로 다른 N개 중에서 R개를  선택하는 경우의 수(순서를 고려한다, 중복인 경우는 선택하지 않는다.)DAT를 활용하여 이미 선택한 경우에는 선택하지 않도록(방문 여부 체크) 판별조건을 추가해 준다.1 2 31 3 22 3 1 3. 중복 조합중복이 가능한 N개 중에서 R개를 선택하는 경우의 수(순서를 고려하지 않는다.)중복이 가능하다 = 방문 처리를 하지 않는다.조합을 위해 현재 뽑는 순서가 2번째 이상일 경우 이전에 뽑았던 수보다 작을경우 선택하지 않는다. 라는 판별 조건을 추가해 준다.1 1 11 1 21 1 31 ..

백트래킹 C++

개요백트래킹 : 재귀 호출 중 가망성이 있는지 여부를 판별하면서 진행하는 방식재귀를 통해 경우의 수를 모두 탐색하여 구하고자 하는 조건에 일치하는 경우를 모두 구할 수 있다.실행하고자 하는 하는 반복 횟수, 재귀를 빠져나올 기저 조건, 각 반복 횟수에 적용할 식을 잘 세우면 효율적으로 사용할 수 있다.  예제1. 조합을 선택하여 출력하기서로 다른 n개의 수에서 k개의 수로 이루어진 조합을 출력하기코드#include using namespace std;int n, k;int arr[100];int DAT[110];void bt(int index) { // 2. 기저 조건 if (index >= k) { for (int i = 0; i > n >> k; for (int i = 0; i > arr[i]; }..

728x90
반응형