코딩하는 개굴이

알고리즘 뽀개기 Step 6 : 트리 알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :) 해당 내용은 백준 알고리즘 강의를 기반으로 작성되었습니다. 추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다. 트리 자료 구조의 일종으로, 사이클이 존재하지 않는 그래프 정점의 개수가 V라면, 간선의 개수가 V-1 루트(root) : 특정 정점으로부터 아래로 방향을 정할 수 있다 위의 트리에서는 1을 루트로 볼 수 있다. 부모(parent) : 1은 2,3의 부모이며, 2는 4,5의 부모이다. 자식(child) : 2는 1의 자식이며, 4는 2의 자식이다. 3의 자식은 6,7이다. 단말 정점(leaf node) : 트리의 마지막 노드를 말함 위 트리의 단..

알고리즘 뽀개기 Step 5 : 그래프 알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :) 추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다. 해당 내용은 백준 알고리즘 강의를 참고하여 작성되었습니다. 그래프 자료구조의 일종으로, 정점(Node/Vertex)과 간선(Edge)으로 구성되어있으며, G = (V,E) 로 표현한다. 아래와 같은 개념을 추가로 알아두자. 경로 : 정점 2에서 1로 가는 경로 2 -> 3 -> 1 2 -> 1 사이클 : 정점 A에서 다시 A로 돌아오는 경로 단순 경로/사이클 : 같은 정점을 두 번 이상 방문하지 않는 경로/사이클로, 문제 등에서 특별한 언급이 없을 경우 일반적인 경로/사이클은 이를 의미한다. (보통 다..

알고리즘 뽀개기 Step 4 : 정렬 알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :) 추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다. 정렬 sort 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 힙 정렬, 병합 정렬 등이 존재 주로 O(N^2), O(NlogN) 의 복잡도로 나뉘는데, 정렬 알고리즘은 빠를 수록 좋기 때문에, O(NlogN)이하로 걸리는 정렬을 사용하도록 한다. 정렬을 직접 구현하는 것보다, C++ 기준 STL 에 있는 sort (각 언어에서 구현되어있는 소팅 수단)을 사용하는 것이 좋다. sort(begin, end) 로, begin 부터 end 바로 전까지를 정렬하는 함수 리스트의 0~n 까지를 정렬할 경우, so..

알고리즘 뽀개기 Step 3 : 수학 알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :) 추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다. 수학 나머지 연산 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어있기에, 답을 M으로 나눈 나머지를 출력하라는 문제가 종종 등장한다. (A + B) mod M = ((A mod M) + (B mod M)) mod M (A X B) mod M = ((A mod M) X (B mod M)) mod M (A - B) mod M = ((A mod M) - (B mod M) + M) mod M 뺄셈의 경우는 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 위와 같이 M을 더한후 mod 를 수행한다. 최..

알고리즘 뽀개기 Step 2 : 다이나믹프로그래밍 알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :) 추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다. 다이나믹 프로그래밍 큰 문제를 작은 문제로 나누어 푸는 알고리즘을 의미 다이나믹 프로그래밍의 조건 Overlapping Subproblem (문제를 작은 문제들로 쪼개어 풀 수 있다) Optimal Substructure (문제의 정답을 작은 문제들의 정답으로 구할 수 있다) 각 작은 문제는 한번만 푼다. Optimal Substructure를 만족하기 때문에, 같은 작은 문제일 경우 순서에 상관없이 구할 때 마다 정답이 같다. 구한 특정 작은 문제의 정답을 저장하여 활용한다. (Memoiz..

알고리즘 뽀개기 Step 1 : 자료구조 알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :) 추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다. 스택 스택 (Stack)은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다. 마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out (LIFO)라고도 한다. 연산 push, pop, top(가장 위의 자료를 보는 연산), empty(비어있는지 아닌지 확인하는 연산), size(저장된 자료의 개수를 반환하는 연산) 문제 추천 괄호 : https://www.acmicpc.net/problem/9012 큐 큐 (Queue)는 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 ..