차가운오미자님의 유리병

이진 탐색은 범위를 반으로 나눠가며 찾는 것이다. 선형 탐색보다 훨씬 빠르게 타겟을 찾을 수 있다. 시간 복잡도는 NlogN이다 주의할 점은, 이진 탐색에서 m의 왼쪽에 m보다 작은 요소가, 오른쪽에 m보다 큰 요소가 있는 걸 보장하기 위해, 이진 탐색 전에 배열은 반드시 정렬되어 있어야 한다. 예를 들어서, 9개의 요소를 가진 배열 arr가 있다고 가정하자. 1 2 3 4 5 6 7 8 9 이렇게 있을 때, 3을 찾는다고 하자. 일단 전체 arr[0] ~arr[8] 중 중간 요소가 3인지 확인한다. 타겟은 3보다 5가 크므로 5보다 아래에 있다는 소리이다. 그럼 다시 arr[0] ~ arr[3] 을 찾아본다. 중간((0+3)/2)은 arr[1] == 2 이다. 타겟 보다 작으므로 오른쪽에 있다는 소리다..

모든 요소를 탐색하면서 요구사항에 맞게 동작하면 된다. DFS를 이용하거나 BFS를 사용하는데 1. DFS를 사용할 경우 코드가 간단하지만, map이 크면 메모리 부족이 일어날 수 있고, 디버깅이 어렵다 2. BFS는 맵이 너무 클 경우에 사용한다. https://chagaun-omija.tistory.com/71 [백준] 2667: 단지번호붙이기 https://www.acmicpc.net/problem/2667 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번 chagaun-omija.tistory.com 여기 있는 이 문제가 Flood Fill의 예시 문제이다. 문제 해설처럼 맵에서 ..

동적 계획법이란? 메모리를 사용해 수행시간의 효율성 향상시키는 방식 이미 계산된 결과를 별도의 메모리 영역에 저장해서 다시 계산하지 않도록 한다. Top-Down 방식과 Bottom-Up 방식(전형적) 두 가지가 있다. - Dynamic Allocation에서 dynamic(실행 도중에 해결하는 방식)과 무관한 명칭이다. 조건 Optimal Substructure (최적 부분 구조) Overlapping Subproblem (중복되는 부분 문제) 예시 Fibonacci 수열 a₁ = 1, a₂ = 1 이고, a_n = a_n-1 + a_n-2 이라는 점화식으로 표현할 수 있다. 재귀함수를 사용해서 풀 수 있는 문제인데, 여기서 이 수열의 계산값들을 배열이나 리스트로 저장해두면 더 빠르게 해결 가능하다. ..

너비 우선 탐색 (Breadth First Search) 탐색 시 너비를 우선으로 탐색 수행 (가까운 것 먼저 탐색) = 출발 노드에서 거리 1인 것부터 탐색하게 됨. - 큐와 그래프로 구현 - 맹목적인 탐색 하고자 할 때 사용 - 최단 경로를 찾아줌 (ex. 미로) 알고리즘 구성: 1) 시작 노드를 큐에 넣어줌 & 방문 처리 2) 알고리즘 따름 (반복문) 1) 큐에서 노드 꺼내서 방문 처리 2) 꺼낸 노드와 연결된 노드 중 방문하지 않은 노드 큐에 넣어줌. 코드: #include #include #include using namespace std; int num = 7; int visited[7]; vector a[8]; // 배열 void bfs(int start){ queue q; q.push(st..

1. Stack 1. 스택 라이브러리 사용 2. 직접 구현 일반적으로 알고리즘 대회에서는 스택 라이브러리 쓰는게 빠름 사용 가능 명령어: stack 이름; (선언 방식) push() pop() empty() top() #include #include using namespace std; int main(void){ stack s; s.push(7); s.push(3); s.push(4); s.pop(); s.push(6); while(!s.empty()){ cout

범위 조건이 있는 경우에 굉장히 빠른 알고리즘 시간 복잡도: O(N) 단순하게 '크기를 기준으로' 세는 알고리즘 예시) 숫자는 1에서 5사이의 정수 1 3 2 4 3 2 5 3 1 2 3 4 4 2 5 1 2 3 5 2 3 1 4 3 5 2 1 1 1 1이 몇 개인지, 2가 몇 개인지.... 5가 몇 개인지 셈 #include int main(void){ int temp; int count[5]; int arr[30] = { 1, 3, 3, 5, 2, 3, 4, 2, 4, 4, 5, 3, 4, 2, 1, 1, 2, 3, 5, 3, 2, 4, 4, 1, 2, 3, 3, 2, 5, 3}; // 배열 초기화 for(int i = 0; i

Heap Tree Structure을 이용하는 정렬 - Complete Binary Tree; 루트 부터 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차근 들어가는, 빽빽한 구조의 트리 - Heap: 최솟값, 최댓값을 최대한 빨리 찾아나기 위해 Binary Tree를 이용함 - 최대힙: 부모 > 자식 - 최소힙: 자식 > 부모 힙 생성 알고리즘(Heapify Algorithm) 예를 들어 부모 노드의 값보다 자식 노드의 값 중에 큰 값이 있다면, 부모 노드와 자식 중 가장 큰 자식 노드를 바꾸는 것 > 이렇게 하위로 갈 수록 규칙이 깨지지 않는지 쭉 탐색하면서 정렬해줘야 함 * 시간 복잡도: O(lg N) = height of Tree * 전체 힙 생성 시간 복잡도: O(1/2N lg N) = ..

Quick Sort 특정한 값을 기준으로 큰 숫자와 작은 숫자를 나눈다. - 기준값(pivot) - 분할 정복 - 왼쪽은 앞에서부터 탐색하며 기준값보다 큰 값을 찾고, 오른쪽은 뒤에서 탐색하여 기준값보다 작은 값을 찾는다. 찾은 후에 그 두 값의 위치를 바꿔준다. - 언제까지? 두 값이 엇갈릴때까지 - 좌측 인덱스(기준값보다 큰 값)값보다 우측 인덱스(기준값보다 작은 값)이 커지면 위치 변경 #include int number = 10; int arr[10] = {3,7,8,1,5,9,6,10,2,4}; void quickSort(int* arr, int start, int end){ if(start >= end){// 원소가 1개인 경우 return; } int key = start; int i = s..

1. 선택 정렬 가장 적은 것을 선택해 제일 앞으로 보낸다 - 가장 쉽고, 가장 단순 #include int main(void){ int i, j, min, index, temp; // i, j 반복 탐색, min 작은 것 int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9} ; for(i=0; i 속도가 빠르다 가정: 선택된 값보다 앞은 모두 정렬이 되어 있다. index보다 앞에 있는 정렬된 배열 중 어느 사이에 들어가야할지를 정하고 거기에 들어가는 것 #include void swap(int* a, int* b){ int temp = *a; *a = *b; *b = temp; } int main(void){ int i, j; int arr[10] = {1, 10, 5, ..

개념 당장 눈 앞에 보이는 최적의 상황을 쫓기. 그래서 '그리디'라고 불리는 것 예시1) 거스름돈 주기 - 가장 큰 화폐 단위부터 거슬러 주기가 최고의 알고리즘 - 큰 단위가 항상 작은 단위의 배수이므로 작은 단위들의 종합으로 다른 해가 나올 수 없다는 게 보장되어야 탐욕법을 사용했을 때 최적의 해가 나오게 됨 - 만약 500, 400, 100원이 있는데 800원을 거슬러줘야 할때 400*2 가 최적의 해이지만 그리디에 따라 큰 단위인 500부터 주면 500*1 + 100*3 이 됨 무조건 큰 경우부터, 작은 경우부터, 긴 경우부터 등 극단적 접근 => sort 기법 자주 사용 예시2) 크루스칼 - 모든 간선 정렬 후 짧은 간선부터 연결하는 최소비용 신장트리 알고리즘 최적의 해를 못찾을 경우, 동적 프로..