이것저것

둘 다 이진탐색 (Binary Search) 기반의 탐색법이다. 이진탐색 (Binary Search) 기반이므로 배열이나 리스트가 오름차순으로 정렬되어있어야 한다. [upper_bound] upper_bound는 key 값을 초과하는 가장 첫 번째 원소의 위치 (주소)를 구한다. 사용법 : upper_bound(시작 주소, 끝 주소, key 값) 리스트의 값이 key 값을 가장 먼저 초과하는 주소 값을 리턴한다. 찾는 값이 없을 경우 끝 주소를 리턴한다. (벡터의 경우 , v.end() ) v : 1, 1, 2, 2, 3, 3, 4, 4 upper_bound(v.begin(), v.end(), 3) => v[6] 의 주소값을 리턴한다. [lower_bound] lower_bound는 key와 같거나 큰 ..

이진 탐색이란? 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘 배열의 중간에 있는 임의의 값을 선택하여 찾고자하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터를 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 위 과정을 반복한다. 이진탐색 예시 {10,13,15,17,20,23,27} 오름차순으로 정렬된 배열이 있다. 이진 탐색을 이용하여 15를 찾아보자 첫 번째 시도 중간값 17을 선택한다. 선택한 17과 찾고자 하는 값 15를 비교한다. 15< 17 이므로 15는 17의 좌측에 존재한다는 것을 알 수 있다. 두 번째 시도 좌측에 존재하는 배열을 대상으로..

BFS는 인접한 노드부터 탐색했지만, DFS는 그러지 않다. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 재귀를 사용하여 구현한다. 모든 노드를 방문하고자 하는 경우 사용된다. 시간복잡도 : O(N+E) void dfs(int curr){ visited[curr] = true; for(int next : adj[curr]){ if(!visited[next]){ dfs(next) } } }

루트노드 (혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. (인접한 노드 =⇒ 가까운 곳부터 먼저 간다) Queue 를 사용해서 구현할 수 있다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. 시간 복잡도 : O(N+E) ⇒ O(정점개수+간선개수) 다음 노드를 이미 방문했는지, 방문하지 않았는지를 기록해두는 배열이 필요하다. bool visit[50] : 기본값 false이므로 방문하면 true로 바꿔준다. 큐에 넣는 순간 visit을 true로 바꾸어주어야한다. (색칠된 곳은 visit[ ]=true) void bfs(){ vector visited(N, false); queue q; //q에 push와 visited true체크는 한 세트처럼 q...

그래프를 코드로 표현하는 방법은 크게 두가지가 존재한다. 1) 인접행렬 (이차원 배열) 장점 구현이 간단하다 두 노드가 연결되어 있는지 알고싶을 때 O(1) 에 가능하다. 단점 공간을 많이 차지한다. 한 노드와 연결된 모든 노드를 알고 싶으면 O(V) (V : 노드의 개수) 모든 노드의 연결관계를 탐색하려면 O(V^2) 구현방법 int graph[100][100]; //양방향 그래프인 경우 graph[2][3]=1; graph[3][2]=1; 2) 인접리스트 (이차원 벡터) 실제로 연결된 노드들에 대한 정보만 저장한다. 장점 간선의 개수만큼만 메모리 차지 모든 노드의 연결 관계를 O(V) 에 탐색 가능하다. 단점 어떤 두 노드가 연결되어있는지 찾으려면 O(V) 구현방법 vector graph[100]; ..

(Graph도 일종의 자료구조이다.) 자료구조는 삽입, 삭제, 탐색이 가능하다. 그래프에서 삽입,삭제 작업은 그래프 구현을 통해, 탐색 작업은 DFS(+Backtracking),BFS를 통해 구현하다. 그래서 그래프란? 어떤 요소(=노드)들 사이의 연결관계(=간선)를 표현하기 위한 자료구조 노드와 노드를 연결하는 간선으로 이루어져 있다. 트리도 그래프의 일종 지도, 도로, 등 실생활에서의 많은 것을 그래프로 모델링 가능 그래프는 방향 그래프, 무방향(양방향) 그래프 두가지가 존재 연결 요소 (Connected component) 그래프는 모두 연결되어 있지 않을 수도 있다. 각각의 그룹을 연결 요소라고 부른다. 위는 두개의 연결 요소를 지닌 하나의 그래프 그래프 summary 노드와 노드를 연결하는 간선..

퀵정렬을 실제 문제푸는데 가장 많이 사용되는 정렬 알고리즘이다. 대부분 언어에서 정렬 라이브러리는 퀵 정렬이다. "기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?" 기준을 설정한 다음 큰 수와 작은 수를 교환한 이후 리스트를 반으로 나누는 방식으로 동작한다. Pivot이라는 개념이 등장 (Pivot = 기준) 기준을 어떻게 설정할 것인가? 가장 대표적인 분할 방식으로 호어 분할 방식이 있다. "리스트에서 첫 번째 데이터를 Pivot으로 정한다" 퀵 정렬의 시간 복잡도는 O(NlogN) (선택 정렬, 삽입 정렬에 비해 빠른 편이다.) (최악의 경우에는 시간 복잡도가 O(N^2) 이다.) - 데이터가 무작위로 입력되는 경우는 퀵 정렬은 빠르게 동작한다. - 데이터가 정렬..

"데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다" 필요할 때만 위치를 바꾸면 된다. = 데이터가 거의 정렬 되어 있다면 비용 감소 삽입 정렬은 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 위처럼 정렬이 이루어진 원소는 항상 정렬된 상태를 유지한다. 시간 복잡도 : O(N^2) 다만 배열이 거의 정렬되어 있는 경우, 매우 빠르게 동작 (최선의 경우 - O(N) )