https://yeongjaekong.tistory.com/35 [자료구조] AVL tree란? / AVL tree의 연산 방법 및 활용 AVL Tree란? AVL 트리란 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)의 한 유형입니다. Adelson-Velsky와 Landis가 1962년에 발명하였으며, 이들의 앞글자를 따서 이름을 붙였습니다. AVL 트리는 각 yeongjaekong.tistory.com https://pinopino.tistory.com/entry/%ED%8A%B8%EB%A6%AC-%EA%B0%9C%EB%85%90-%EC%A0%95%EB%A6%AC-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89%ED%8A%B8%EB%A6%AC..

컴퓨터는 1억번 연산하는데 약 1초가 걸린다. 하지만 알고리즘 문제를 해결하다 보면 입력이 1억번 이상 주어지는 경우가 있다. 이때에는 모두 탐색할 경우 시간 초과가 날 가능성이 크다. 따라서 더 빠른 풀이방법을 생각해야 한다. 이런 경우 보통 이분탐색을 쓴다. 선형 탐색의 시간 복잡도를 O(lon N)으로 만들어준다. [반복문으로 구현한 이분 탐색] while(L arr[M]) L = M + 1; else if(target < arr[M]) R = M - 1; else { result = true; break; } } lower_bound upper_bound

[목차] Task Scheduling Problem이란? Task Scheduling 알고리즘 Dynamic Programming 알고리즘 Greedy 알고리즘 예제 1. Task Scheduling Problem이란? 예제로는 [백준 1931번 회의실 배정]이 있다. 2. Task Scheduling 알고리즘 1) DP 2) Greedy 나중에 다른 그리디 문제를 풀 때에도 내가 떠올린 그리디 알고리즘이 올바른지 확인할 때 지금 당장 손해를 보더라도 나중 가서는 이득인 경우가 있을 수는 없는지 고민해보면 정당성을 확인하거나 반례를 찾을 때 도움이 됩니다. 3. 예제 유명한 예제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11..

이번 포스팅에서는 자료구조, 알고리즘에 대해 알아보고 둘의 관계를 살펴보겠습니다. 1. 자료구조란? 데이터에 효율적으로 접근, 변경하기 위해 설계해놓은 데이터 저장 방법입니다. 2. 알고리즘이란? 알고리즘이란 문제 해결을 위한 명령어들의 집합입니다. 간단히 말하면 문제의 풀이과정들입니다. 알고리즘은 자료구조와 매우 밀접한 관계가있습니다. 문제 해결을 위해서는 데이터들을 원하는 형태로 저장해야 하기 때문에 이 과정에서 어떤 자료구조를 사용하는냐에 따라 속도가 천차만별이다. 잘선택 일반적으로 데이터는 그래프로 나타낼 수 있습니다. 이 그래프는 노드와 간선들로 연결되어 있는데요, 노드와 간선들의 종류에 따라 [가중치를 연결한 그래프] #include #include #define F first #define ..

https://www.acmicpc.net/workbook/view/824 문제집: FFT (koosaga) www.acmicpc.net 나중에 풀 실력이 되면 플레를 찍고 모든 알고리즘을 마스터한 뒤 건드려볼 예정.... 그날이 올까?

순서를 고려하는 경우 고려하지 않는 경우 #include using namespace std; int N, K; int D[201][201]; int main(void) { cin >> N >> K; for (int i = 1; i

[목차] LIS란? LIS를 구하는 알고리즘 완전 탐색 알고리즘 분할 정복 백트래킹 두 완전 탐색 알고리즘의 비교 동적 계획법 알고리즘 O(N²) 풀이 이분 탐색을 이용한 풀이 두 동적 계획법 알고리즘 비교 세그먼트 트리 알고리즘 LIS의 대표 예제 전깃줄 문제 줄세우기 문제 합친 LIS 1. 가장 긴 증가하는 부분 수열(LIS)이란? 증가하는 부분 수열을 중에서 길이가 가장 긴 수열을 말한다. 영어로는 줄여서 LIS(Longest Increasing Subsequence)라고 한다. 여기서 잠깐 LIS의 S가 subarray가 아니라 subsequence의 이유를 보면 다음과 같다. 부분 수열의 종류는 크게 subarray와 subsequence가 있다. subarray는 연속적으로 이어져있는 부분 수..

[백준] 14502번 연구소를 풀다가 화딱지가 나서 겨우겨우 구현했다. 이게 과연 쓸 일이 있을까 해서 그냥 남겨둔다. 백트래킹으로 1차원 배열의 조합은 구현해봤어도 2차원 배열의 조합은 처음 해본다. 생각보다 생각해내기 어려웠다.... 직접 손으로 써보면서 겨우 찾아냈다.. y좌표가 증가하는 순으로 x좌표가 무조건 0부터n-1까지가 아니라 다음 탐색에서 y랑 같을 때만 x이고 그 다음부터는 0부터 n-1까지이다. x부터가 아니라 바로 x+1부터로 하면 되지 않냐? 하는 의문이 들지만 해보면 처음 채울 때에 첫째칸이 안채워진다. 따라서 x부터 하는게 맞다. #include using namespace std; int map[4][4]; int cnt; void print() { for (int i = 0..