Hello World!

트리 - 개념 루트와 루트의 서브 트리로 구성된 계층형 자료구조 최소 하나 이상의 노드가 있어야 함. 이진트리 : 각 노드가 최대 2개의 자식 노드를 갖는 트리 - 트리의 표현 : 배열이나 연결 리스트 이용 - 트리의 탐색 중위 탐색 (inorder) : 왼쪽 서브트리, 루트 노드, 오른쪽 서브트리 순으로 탐색 전위 탐색 (preorder) : 루트 노드, 왼쪽 서브트리, 오른쪽 서브트리 순으로 탐색 후위 탐색 (postorder) : 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순으로 탐 - 문제 풀이 예시 : 백준 1991 트리 순회 (https://www.acmicpc.net/problem/1991) #include using namespace std; pair node[28]; int n; voi..

다이나믹 프로그래밍 - 개념 : 큰 문제를 작은 문제로 쪼개서 답을 저장하고 활용하는 것 (이전의 결과들은 기억하면서 수행하기 위한 알고리즘) - 다이나믹 프로그래밍 사용 조건 겹치는 부분 문제 : 동일한 작은 문제들이 반복해서 나타나야 함 최적 부분 구조 : 작은 문제들의 결과가 큰 문제에 상관없이 항상 동일해야 함. - 다이나믹 프로그래밍 알고리즘 구현 방식 bottom-up 방식 아래에서부터 계산을 수행하고 누저시켜 전체 큰 문제를 해결하는 방식 작은 문제의 결과들을 하나씩 저장해나간다. top-down 방식 n에서부터 호출을 시작해 인덱스 0까지 내려간다. 해당 결과 값을 재귀를 통해 전이시켜 재활용 - 다이나믹 프로그래밍 구현 과정 다이나믹 프로그래밍 조건 파악 및 적절성 판단 관계식(점화식) ..

슬라이딩 윈도우 - 개념 : 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해서 문제를 풀이하는 알고리즘 - 특징 1차원 배열에서 O(N*M)의 시간복잡도로 해결해야 할 일을 O(N)으로 해결할 수 있음 한 번 구한 값을 버리지 않고 재사용 구간의 넓이가 고정되어 있음. - 문제 풀이 예시 : 백준 21921 블로그 (https://www.acmicpc.net/problem/21921) #include using namespace std; int daysum[250001]; int main() { int n, x, result, max, cnt = 1, day; cin >> n >> x; cin >> day; daysum[0] = day; for (int i = 1; i < n; i++..

그래프 - 그래프 : 정점(노드)과 간선(링크)으로 이루어진 자료구조의 일종 - 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것 DFS - 깊이 우선 탐색 (Depth-First Search) : 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드 pop 2번의 과정을 수행할 수 없을 때까지 반복 - 특징 스택을 활용한 구현, 재귀함수를 통한 구현이 가능함. 공간복잡도가 낮음. 목표 노드가 깊이 있을 경우 빠르게 탐색이 가능함. 해가 없는 경로를 탐색할 경우 단계가 ..

Bruteforce - 개념 : 가능한 모든 경우의 수를 탐색하며 요구조건에만 충족되는 결과만을 가져온다. (완전탐색) 구현이 쉽고 정답만을 출력한다. 시간 측면에서 비효율적이다. 모든 자료를 탐색해야하므로 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다. - 완전 탐색 기법 단순 Bruteforce 특정 기법을 사용하지 않고 모든 경우를 만들어 답을 구하는 과정 비트마스크 (BITMASK) 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식 나올 수 있는 모든 경우의 수를 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용 가능 다른 자료구조에 비해 수행시간이 더 빠르다 : O(1) 비트 연산자를 사용해서 코드가 간결하다. 메모리를 더 적게 사용할 수 있다. 재귀 함수 ..

유클리드 호제법 - 유클리드 호제법의 정의 (https://terms.naver.com/entry.naver?docId=2073670&cid=47324&categoryId=47324) 두 정수 a, b의 최대공약수를 G(a, b)라고 하자. 정수 a, b, q, r (b ≠ 0)에 대해서 a = bq + r이면 G(a, b) = G(b, r)이 성립한다. - 유클리드 호제법으로 최대공약수 구하기 int gcd(int a, int b) { while (b != 0) { int tmp = a % b; a = b; b = tmp; } return a; } - 유클리드 호제법으로 최소공배수 구하기 int lcm(int a, int b) { return a / gcd(a, b) * b; } - 문제 풀이 예시 :..

Greedy Algorithm - 개념 : 최적화 문제를 해결하기 위한 알고리즘 각 단계에서 최적의 선택을 하면서 동작함. 각 단계에서의 선택은 지역적으로 최적이지만(local solution 제공), 전체적으로는 최적 해를 보장하지 않음(global solution 보장 x) 매우 간단하고 직관적인 방식이나 매 상황에서 최적해를 제공하지 않음. 그리디 알고리즘이 최적해를 보장하기 위해서는 다음의 두 조건을 만족해야 한다. - 조건 탐욕적 선택 속성 (Greedy-choice property) 앞의 선택이 이후의 결과에 영향을 주지 않는 경우 탐욕적으로 선택해도 최적해를 구할 수 있음. 현재 순간의 최적해를 선택하면 번복하지 않음. 최적 부분 구조 (Optimal substructure) 전체 문제의 최..

Priority Queue - 우선순위 큐 : 지정된 우선순위 규칙에 따라 우선순위가 큰 데이터를 먼저 반환 - 힙(heap) 자료구조 이용 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 완전이진트리의 형식으로 매순간 최대, 최소를 얻도록 정렬되어 있음 (모든 데이터가 정렬되어 있는 것은 아님.) 최댓값을 반환하는 최대 힙, 최솟값을 반환하는 최소 힙 최악의 경우에도 O(logN)을 보장함. - STL #include #include using namespace std; int main() { priority_queue 변수명; return 0; } 정렬은 내림차순이 기본 오름차순을 사용하기 위해서 정렬기준 자리에 함수를 만들어서 넣어주거나, greater을 넣어주면 됨. push() : 원소 ..

자료구조 : 컴퓨터과학에서 데이터를 구조적으로 표현하는 방식 선형 자료구조 : 하나의 자료 뒤에 하나의 자료가 배치되는 구조 ex) stack, queue, list, 배열 비선형 자료구조 : 하나의 자료 뒤에 여러 자료가 올 수 있는 구조 ex) 트리, 그래프 Stack - LIFO (Last in FIrst out) - STL #include push() : 스택에 원소 추가 pop() : 스택에서 원소 삭제 top() : 스택 최상단 원소 확인 size() : 스택의 사이즈 확인 empty() : 스택이 비어있는지 확인 - 문제 풀이 예시 : 백준 10828 스택 (https://www.acmicpc.net/problem/10828) #include #include #include using nam..

C/C++ 입출력 - C++의 경우 코드를 작성할 때 아래와 같은 틀에서 시작한다. #include using namespace std; int main() { // return 0; } - c++ 속도 향상하기 ios_base::sync_with_stdio(false) cin.tie(NULL) // 줄바꿈 시 endl 대신 '\n' 사용 STL 라이브러리 - STL(Standard Templete Library) : 자료구조와 이에 관련된 알고리즘을 구현한 템플릿의 모음 - STL을 포함하는 C++ 표준 라이브러리 : C++ 표준 라이브러리 구성 요소 STL Container STL Iterators STL Adapters STL Algorithms STL Function Object, Allocato..