구현 테크닉 알고리즘을 구현하는데 도움이 되는 여러가지 테크닉들 상하좌우 탐색 (x, y)를 기준으로 상하좌우 좌표를 생각해보자. x의 변화량은 [-1, 1, 0, 0]이고, y의 변화량은 [0, 0, -1, 1]이다. 이것을 dx, dy배열로 만들어서 상하좌우 좌표를 계산하는 테크닉이다. 2차원의 4방향뿐만 아니라, N차원의 M방향은 전부 표...

이분 탐색 이분 탐색은 $O(NlogN)$의 시간복잡도를 가지는 탐색 알고리즘으로, 원소들이 정렬된 상태에서만 사용할 수 있다는 특징이 있다. 알고리즘 진행 방식은 다음과 같다. 첫 번째 원소를 low, 마지막 원소를 high로 설정한다. mid = (low + high) / 2 mid가 key보다 작은 경우, low = ...

번외: FastIO #define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector // 생성 vector<int> v; // int type vector 생성 vector<int> v(N); // N개의 크기를 가지는 vector 생성 ...

공부해야 할 알고리즘 “이론” ✅ C++ ✅ STL ✅ Data Structure(Stack, Queue, Deque, Set, Map, Priority Queue, pair, tuple) ✅ Brute-Force ✅ Sort ✅ Backtracking ✅ Prefix Sum ✅ Greedy ✅ Dynamic Programming ✅...

ICPC란? ICPC는 International Collegiate Programming Contest의 약자로 세계에서 가장 권위 있고 규모가 큰 국제 대학생 프로그래밍 대회이다. 같은 학교 학생들로 구성된 3인 1조의(+ 지도 교수) 팀으로 참가하며, Regional 예선과 본선, World Final로 구성되어 있다. 각 팀은 컴퓨터 한 ...

문제 링크 백준 2505번: 두 번 뒤집기 아이디어 보드를 뒤집는 구간을 [L1, R1], [L2, R2]라고 했을 때, 구간의 관계에 따라 3가지 경우가 존재한다. 두 구간이 독립적인 경우 두 구간이 서로 독립적인 경우이다. 이 경우는 브루트포스로 [L1, R1], [L2, R2]을 전부 구할 수 있으므로 문제가 되지 않는다. 한 구...

문제 링크 24896번: 르블랑의 트리 순회 아이디어 순회가 불가능한 조건 1번 노드를 루트 노드로 트리를 순회한다고 가정했을 때, 한 번에 체크포인트가 3개 이상 필요하면 순회가 불가능하다. 위와 같은 트리는 순회가 가능하지만 위와 같은 트리는 순회가 불가능하다. 1번 노드의 오른쪽 서브 트리를 탐색한 후 왼쪽 서브 트리를 탐색하기 ...

그래프 그래프는 정점과 간선으로 이루어진 객체 사이의 연결성을 표시하는 비선형 자료구조이다. 그래프 G는 G=(V, E)로 정의하는데, V는 정점의 집합, E는 간선의 집합을 의미한다. 그래프 용어 정점(Vertex) 객체를 의미한다. V(G)는 그래프의 정점의 집합을 의미한다. 간선(Edge) 객체를 연결하는 선이다. E(G)는 그래프의 ...

힙 힙은 중복된 키 값을 가질 수 있는 완전 이진 트리의 한 종류로, 원소들 중 가장 큰 값이나 가장 작은 값을 $O(logN)$에 찾기 위해 사용된다. 모든 노드에 대해 부모의 키 값 $\geq$ 자식의 키 값을 만족하는 힙을 최대 힙, 자식의 키 값 $\geq$ 부모의 키 값을 만족하는 힙을 최소 힙이라고 한다. 최대 힙에서의 최댓값과 최소...

레드-블랙 트리 레드-블랙 트리는 높이를 $Klog_2(N)$으로 유지하는 자가 균형 이진 트리이다. 모든 노드가 red 혹은 black 색깔을 가지고 있으며, 다른 트리들과 다르게 NIL(NULL)노드를 표시한다. 레드-블랙 트리의 성질 모든 노드는 red or black node이다. 루트 노드는 항상 black node이다. ...

AVL 트리 AVL트리는 좌우 서브 트리의 높이의 차이가 1 이하인 트리로, 자가 균형 이진 탐색 트리이다. AVL 트리는 왜 등장하게 됐을까? 트리의 좌우 균형이 잘 맞을수록 트리의 높이는 낮아진다. 이진 탐색 트리에서 트리의 높이가 최소일 때 탐색 연산의 시간 복잡도는 $O(logN)$이고, 최고일 때의 시간 복잡도는 $O(N)$이다. 완전 이진...

이진 탐색 트리 이진 탐색 트리(BST: Binary Search Tree)는 탐색을 위한 이진 트리 형식의 자료구조이다. 임의의 노드를 루트 노드로 하는 서브 트리에서 왼쪽 자식 노드는 루트 노드보다 작은 값이, 오른쪽 자식 노드는 루트 노드보다 큰 값이 들어간다. 이진 탐색 트리의 노드는 유일한 값을 가진다. 이진 탐색 트리 탐색연산 찾으...

이진 트리 이진 트리는 모든 노드가 2개 이하의 자식 노드를 가지고 있는 트리를 말한다. 즉, 모든 노드의 차수가 2이하이다. 이진 트리의 종류 Full Binary Tree 모든 노드의 차수가 0 혹은 2인 트리 Degenerate Binary Tree 모든 내부 노드의 차수가 1인 트리 Skewed ...

트리 트리의 정의 트리란 노드와 간선으로 이루어진 계층형 자료구조이다. 트리의 특징 트리는 N개의 노드와 N-1개의 간선으로 이루어져 있다. 사이클이 존재하지 않는다. 모든 노드는 서로 유일한 경로로 연결되어 있다. 모든 트리는 1개의 루트 노드를 갖는다. 루트 노드를 제외한 모든 노드는 1개의 부모 노드를 갖는다. ...

덱 덱(deque: double-ended queue)은 front, rear에서 삽입과 삭제가 전부 가능한 자료구조이다. 덱 ADT 데이터 element E 메소드 내용 add...

큐 큐는 먼저 추가된 데이터가 먼저 삭제되는 선입선출(FIFO: First Input FIrst Out)구조를 가지고 있는 자료구조이다. 큐의 종류에는 선형 큐와 원형 큐가 있다. 큐에서 삭제가 일어나는, 즉 가장 앞에 있는 곳을 front, 삽입이 일어나는 가장 뒤에 있는 곳을 rear이라고 한다. 큐 ADT 데...

스택 스택은 나중에 삽입한 데이터가 먼저 나오는 후입선출(LIFO: Last In First Out)의 구조을 가지고 있는 자료구조이다. 스택에서 삽입과 삭제가 일어나는 가장 위에 있는 곳을 top이라고 한다. 스택 ADT 데이터 element E ...

리스트 리스트란 순서를 가진 데이터들을 일자로 나열한 자료구조이다. 리스트의 종류에는 선형 리스트와 연결 리스트가 있다. 리스트 ADT 데이터 element E 메소드 내용 add(...

다중 상속 다중 상속이란 2개 이상의 클래스로부터 동시에 상속받는 것을 말한다. 자바에서는 다중 상속을 허용하지 않는다. C++에서는 다중 상속을 허용했었던 기억이 있는데, 왜 자바에서는 다중 상속을 허용하지 않을까? 자바는 왜 다중 상속을 허용하지 않을까? One reason why the Java programming language d...