알고리즘/알고리즘_기초 (11) 썸네일형 리스트형 13강 - 너비 우선 탐색 (BFS) 1. 만들 것 1) 큐: 탐색 중인 노드들 저장 / q 2) bfs_visited: 방문 여부 표시 3) node: 현재 탐색할 노드 4) 벡터(bfs_vector): 탐색을 마치고 탐색 순서 저장 (나중에 출력할 것) 2. 코드 1) 시작점 설정 1> 시작 노드를 큐에 삽입 / q.push(시작 노드) 2> 해당 노드를 방문했다고 표시 / bfs_visited[시작 노드] = true 2) 반복문 1> node에 큐의 맨 앞 요소를 저장 / int node = q.front() 2> node를 벡터에 삽입 / bfs_vector.push_back(node) 3> 벡터에 삽입하면 큐에서 node를 뺀다. / q.pop() 4> 반복문 (연결된 노드 탐색) - 새로운 노드가 이 node와 연결된 것 && .. 12강 - 그리디 (Greedy) 1. 그리디 1) 정의 : 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 2) 특징 1> 대표 예제: 거스름 돈 문제 - 일단 큰 화폐부터 주는 것 2> 극단적으로 문제에 접근: 무조건 큰 경우대로, 무조건 작은 경우대로 11강 - 다이나믹 프로그래밍 (Dynamic Programming) 1. DP 1) 정의 1> 큰 문제를 작은 문제로 나눠 풀 때 작은 문제들이 같은 문제라면 2> 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법 2) 특징 1> 단순 분할 정복과는 다르게 동일한 문제를 다시 풀지 않습니다. 2> Memoization을 통해 이미 계산한 결과는 array에 저장함으로써 나중에 동일한 계산이 필요한 경우 단순 return합니다. 2. 예시 (피보나치 수열) #include using namespace std; int memo[100]; int fibonacci(int x) { if (x == 1) return 1; if (x == 2) return 1; if (memo[x] != 0) return memo[x]; // 기록한 적이 있다면 기록한 것을 출.. 10강 - 큐 (Queue) 1. 큐 1) 정의 1> FIFO (First In First Out) 2> 먼저 집어 넣은 data가 먼저 나오는 구조 3> data 삽입은 한 쪽 끝에서, 삭제는 반대쪽 끝에서만 일어난다. 4> 용어 - rear: 삽입이 일어나는 쪽 - front: 삭제가 일어나는 곳 2) 특징 1> 일종의 리스트 2> Linked List로 구현 3) 선언 1> 헤더 파일 #include 2> 큐 선언 queue '변수명'; 4) 연산 1> 추가: 뒷 부분(back) 추가 q.push(element); // 큐의 뒷 부분에(back) 원소를 추가 2> 삭제: 앞에 있는(front) element를 삭제 q.pop(); // 큐의 앞에 있는(front) 원소를 삭제 3> 조회 - front (삭제 되는 곳) q.fr.. 9강 - 스택 (Stack) 1. 스택 1) 정의 1> LIFO (Last In First Out) 2> 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 형식의 자료 구조 3> 가장 최근에 추가한 항목이 가장 먼저 제거될 항목이다. 4> 택배 상하차를 생각한다. 2) 특징 3) 선언 1> 헤더 파일 #include 2> 스택 선언 stack '변수명' 4) 기본 함수 1> 추가 s.push(element) // item 하나를 스택의 가장 윗(top) 부분에 추가 2> 삭제 s.pop(); // 가장 위(top)에 있는 element를 삭제 3> 조회 s.top(); // 스택 맨 위(top)에 있는 원소를 return 4> 크기 s.size(); // 스택 내부의 element 개수를 return 5> 비어있는지 s.empty(); //.. 6강 - C++ STL sort() 함수 0. STL 1> 표준 라이브러리 (Standard Template Library) 2> 프로그램에 필요한 자료구조와 알고리즘을 Template로 제공하는 라이브러리 1. Sort 함수 1) 특징 1> '#include '을 선언해야 한다. 2> quick sort를 기반으로 함수가 구현되어 있어서 3> 시간복잡도가 O(nlogn)이다. 2) 사용법 기본 sort(start 주소, end 주소) 1> [start, end) 범위에 있는 element들을 - start를 포함하고 end를 포함하지 않는 구간 - 그러니 정렬하고 싶은 범위보다 하나 더 뒤에 있는 원소의 주소까지 argument에 넣어야 한다. 2> 오름차순(default)으로 정렬한다. 3) 다른 사용 예시 1> array sort(arr,.. 5강 - 병합 정렬 (Merge Sort) 1. 병합 정렬 1) 정의 2) 특징 1> 분할 정복 알고리즘(divide and conquer)의 하나 2> 시간 복잡도: - 편향된 분할을 하는 퀵 정렬과 달리 - 정확히 절반으로 분할을 해서 O(nlogn)을 보장한다. 3> 안정 정렬 4> 일단 반으로 쪼개고 나중에 합친다. 3) 퀵 정렬과 다른 점 1> pivot이 없다. 2> 그래서 항상 반으로 분할한다. (편향된 분할을 하지 않는다.) 2. 구체적인 과정 (오름차순 기준) 0> 해당 분할의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 1> 계속해서 2등분으로 잘게 잘라놓는다. 2> 맨 처음 2개의 분할을 가지고 진행한다. 3> (각 분할은 이미 정렬되어 있다) 각 분할의 가장 맨 앞의 값을 비교하여 작은 값을 다른 array(sorted.. 4강 - 퀵 정렬 (Quick Sort) 다양한 퀵 정렬 중에서 보편화된 방법 하나를 다루겠습니다. 1. 퀵 정렬 1) 정의 2) 특징 1> 분할 정복 알고리즘(divide and conquer)의 하나 2> 시간 복잡도: O(nlogn ~ n^2) 3> 불안정 정렬 4> 비교 정렬 (다른 원소와의 비교만으로 정렬을 수행) cf> pivot: 기준 (정도로 생각하면 된다.) 농구에서 pivot이 한 발만 땅에 대고 움직이는 것을 연상하면 이해가 쉽습니다. - pivot을 무엇으로 하느냐에 따라 퀵 정렬 종류도 다양합니다. 2. 구체적인 과정 (오름차순을 기준) 1) 구체적인 순서 1> 맨 앞의 element를 pivot으로 설정 2> pivot을 제외하고 - 맨 왼쪽부터 pivot보다 큰 숫자를 찾고 - 맨 오른쪽부터 pivot보다 작은 숫자를.. 이전 1 2 다음
