![]()
https://www.youtube.com/playlist?list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY 바킹독의 실전 알고리즘 강의 코딩테스트 대비를 위한 바킹독의 실전 알고리즘 강의입니다. 블로그 URL : https://blog.encrypted.gg/category/강좌/실전%20알고리즘 www.youtube.com 1. 스택 : 선입후출 1) 성질 - 원소 추가, 삭제 : O(1) - 제일 상단 원소 확인 : O(1) - 그 외 나머지 원소 확인/변경은 원칙적으로 불가 2) 구현 해보기 const int MX = 1000005; int dat[MX]; int pos = 0; void push(int x) { dat[pos] = x; pos++; } void pop() {..
https://www.youtube.com/playlist?list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY 바킹독의 실전 알고리즘 강의 코딩테스트 대비를 위한 바킹독의 실전 알고리즘 강의입니다. 블로그 URL : https://blog.encrypted.gg/category/강좌/실전%20알고리즘 www.youtube.com 1. 배열 1) 성질 O(1)에 k번째 원소 확인, 변경 가능 추가적으로 소모되는 메모리의 양이 거의 없음 데이터들이 붙어있으므로 캐시지역성(cache hit rate)이 좋음 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 임의의 위치에 원소에 삽입/삭제하기 위해서는 O(N) 시간이 걸림 insert, erase 함수 구현하기 #include us..
(5) 바킹독의 실전 알고리즘 강의 - YouTube 바킹독의 실전 알고리즘 강의 코딩테스트 대비를 위한 바킹독의 실전 알고리즘 강의입니다. 블로그 URL : https://blog.encrypted.gg/category/강좌/실전%20알고리즘 www.youtube.com 위 강의를 보고 학습한 내용을 바탕으로 작성하였습니다. 1. 시간복잡도, 공간복잡도 1) 시간 복잡도 - 컴퓨터는 1초에 대략 3~5억개 정도 연산 처리 가능 - 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 - 빅오 표기법 : 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법 O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!) O(1) O(logN) O(N) O(N..
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ - YES24 코딩 테스트를 위한 자료 구조와 알고리즘 with C++ - YES24 67개 문제 풀이로 익히는 C++ 자료 구조와 알고리즘!코딩 테스트 준비 및 최신 C++ 문법으로 알고리즘을 학습하자!C++ 자료 구조부터 그리디 알고리즘, 분할 정복 알고리즘, 그래프 알고리즘, 동적 www.yes24.com 🔔 1장 리스트, 스택, 큐 1.1 들어가며 응용 프로그램 설계시 중요 고려 항목 중 하나는 데이터 관리. 데이터를 메모리에 저장하기 위해 여러 자료 구조를 사용할 수 있음 응용 프로그램에서 필요한 기능을 구현하고, 동작 성능과 안정성을 확보하려면 적절한 "자료 구조" 선택해야 함 1.2 연속된 자료 구조와 연결된 자료 구조 데이터를 처리하..
1. 순열 1. swap을 이용한 재귀함수 구현 => 사전순 출력x #include #include #include using namespace std; int n; vector v(10); void permutation(int s, int e) { if (s == e) { for (int i = 0; i < n; i++) { cout
Chapter 08 - 다이나믹 프로그래밍(Dynamic programming) 1. 다이나믹 프로그래밍(동적 계획법) : 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법 1) 피보나치 수열 - 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예 n번째 피보나치 수 = (n-1)번째 피보나치수 + (n-2)번째 피보나치수 단, 1번째 피보나치수 = 1, 2번째 피보나치 수 = 2 ① 재귀 함수를 사용한 소스코드 int fibo(int x){ if(x==1 || x==2){ return 1; } return fibo(x-1)+fibo(x-2); } int main(){ cout n; for (int i = 0; i > x; arr.push_..
Chapter 03 - 그리디(Greedy) 1. 그리디 알고리즘(=탐욕법) : 현재 상황에서 지금 당장 좋은 것 만 고르는 방법 👉 매 순간 좋아 보이는 것만 선택 👉 현재의 선택이 나중에 미칠 영향에 대해 고려X 예제 3-1 ) 거스름돈(C++) Q . 손님에게 거슬러야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수? (동전은 500원, 100원, 50원, 10원이 있다) > 가장 큰 화폐 단위부터 돈을 거슬러 줘야 함 #include using namespace std; int n;//손님에게 받은 돈 int coin[4] = { 500, 100, 50, 10 }; int ans; //거스름돈의 개수 int main() { cin >> n; for (int i = 0; i < 4; i++) ..
![]()
1. 유니온 파인드 1) 의미 - 그래프 알고리즘으로 Union(합집합) + Find(찾다)로 '합집합 찾기' 라는 의미를 가지고 있다. - 서로소 집합(Disjoint Set) 이라고 불리기도 한다. - 여러 노드 중 두 노드를 선택하여 같은 그래프에 속해 있는 지 확인하는 알고리즘이다. 2) 연산 - 2가지 연산이 존재한다. ① Find(x) : 원소 𝑥가 속한 부분집합을 찾는다. 보통 𝑥가 속한 부분집합의 대표 원소를 되돌려준다 ② Union(x, y) : 원소 𝑥가 속한 부분집합과 원소 𝑦가 속한 부 분집합의 합집합을 구한다. * 각 부분집합은 트리로 나타낸다. 3) 구현(배열 이용) - 미리 해야할 과정 노드의 개수 만큼 배열을 선언한다. 각 노드의 루트노드를 가르키는 배열을 선언하고, 초기화 ..
1. BFS란? - BFS 는 너비우선탐색을 말합니다. - 루트 노드에서 시작하여 인접한 노드를 탐색하는 방법입니다. Q. 너비우선 탐색을 하면 순서가 어떻게 될까요? A. 0 - 1 - 2 - 3 - 4 - 5 -6 1) 특징 - 두 노드사이의 최단 경로를 찾을 때, 임의의 경로를 찾을 때 사용 - 코드가 DFS보단 복잡하지만 속도는 더 빠르다 2) 알고리즘 구현 방법 BFS의 결과 : 1 - 2 - 6 - 3 - 4 -5 - 큐를 이용하여 구현함 void bfs(int st) { q.push(st); visited1[st] = 1; while (!q.empty()) { int now = q.front(); q.pop(); printf("%d ", now); for (int i = 0; i < adj[..
