파고파고

해결 포인트✨ 1. 조이스틱 조작횟수만 구하면 되기 때문에, (1) A를 다른 알파벳으로 바꾸기 위해 필요한 조작의 수와 (2) 커서의 위치조작의 최소횟수를 더하는 식으로 답을 구했다. 2. (1)은 for 문으로 문자열을 한 번 돌면서 단순히 구해줬다. 3. (2)는 알파벳 'A' (방문할 필요가 없는 글자) 들을 barrier로 하여, 여러 barrier 후보 중 기존보다 이동횟수가 적은 barrier가 나왔을 때 barrier를 갱신해주는 방식으로 greedy하게 코드를 짰다. (처음에는 가장 긴 길이의 'A' barrier (AAAAAA가 AAA보다 길이가 김) 가 채택되는 것이 최소라고 생각하고 코드를 짰더니 통과가 안됐다. 이후에 예외를 살펴보니, barrier의 길이가 가장 긴 것이 아님에도..

Matrix chain multiplication: Optimal Substructure 연산(총 multiplication)의 양이 최소가 되도록 하는 행렬의 곱 순서를 푸는 알고리즘으로 구현해보자. *행렬곱에 관한 원칙 행렬 A(p×q)와 B(r×s)를 곱하기 위해서는 q = r이어야 하며, 곱의 결괏값은 (p×s)인 행렬이다. 행렬곱(p×q인 행렬과 q×r인 행렬의 곱)에서 시행되는 곱의 횟수는 총 pqr 회이다. 행렬곱은 결합법칙이 성립한다. 하지만, 계산순서가 바뀌었을 때, 연산의 '양' pqr은 달라질 수 있다. ## Matrix Chain Multiplication Problem 다음의 행렬곱이 있다고 하자. $$A_{1}·A_{2}·A_{3}·A_{4}····A_{n}$$ 곱해지는 각 행렬..

Comparison Sorting Methods 정렬에 있어, 각 요소의 비교를 사용한 정렬이다. 지금까지 포스팅한 정렬 알고리즘 모두가 comparison sorting 방식에 해당한다. InsertionSort, SelectionSort, MergeSort, HeapSort, QuickSort ### Lower bound of Comparison Sorting Comparison Sorting 방식을 사용하는 알고리즘들의, worst case에서의 공통적인 Lower Bound는 다음과 같다. $$\Omega (n*lg(n))$$ 즉, 최악의 경우 해당 시간보다 같거나 많은 시간이 걸린다는 것을 의미한다. (upper bound가 아님에 유의하자.) ### Decison Tree Model compa..

Quick정렬과, 그 구현을 위한 부가알고리즘들, 시간복잡도 등을 살펴보자. PARTITION 퀵정렬에서 핵심적으로 사용되는 알고리즘이다. merge sort에서와 비슷하게, 퀵정렬에서도 Partition은 pivot을 중심으로 큰 값과 작은 값으로 배열을 나누는 것을 의미한다. 그림으로 이해해보자. pivot x를 기준으로 왼쪽은 x보다 작은 요소, 오른쪽은 x보다 큰 요소로 배열이 나뉘었다. 이때 pivot은 배열의 어떤 요소든지 선택될 수 있다. partition의 과정을 그림으로 이해해보자. 초기세팅은 다음과 같다. pivot = 4 두 개의 포인터 i, j = 모두 배열의 가장 앞을 가리키는 중 r = pivot의 포인터를 의미한다. 가장 첫번째 요소부터 마지막 요소까지, pivot과 비교해주며..

Heap이란? almost complete binary tree (완전이진트리)를 기초로 하는 자료구조이다. *complete binary tree (1) 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 (자식이 모두 2개(binary)) (2) 마지막 레벨의 노드들은 가능한 한 왼쪽부터 채워져 있는 자료구조 *완전이진트리의 예시. heap에도 해당하는 것을 확인하자. 여기서 heap은 각 노드에 들어있는 값의 대소에 일정한 규칙이 있는 자료구조다. 그 규칙의 종류에 따라 heap은 2가지로 나뉜다. Max-Heap Property - 부모노드(parent node) 가 자식노드 (child node)보다 크거나 같다. - root node, 즉 트리의 가장 상단에 있는 node가 가장 큰 el..

알고리즘에서 자기 자신을 재귀적으로 호출할 때, 그 시간복잡도를 재귀로 표현할 수 있다. 재귀식이란, 함수에 더 작은 입력값을 대입했을 때의 등식이나 부등식을 표현한 것을 말한다. (이렇게 말하면 이해가 안되니까 가령,) $$\begin{cases} \theta(1) \; if\, n=1\\ 2T(n/2)+\theta(n) \; if\, n>1\\ \end{cases}$$ 재귀를 이용해 알고리즘에 대한 알맞은 점근표기법을 찾아낼 수 있다. 점근표기법을 찾는 과정에서 재귀를 푸는 방법으로는 3가지가 있다. 1) Substitution method 2) Recursion-tree method 3) Master method (다루지 않을 것) 1. Substitution Method 지난 포스팅에서 점근표기법..

알고리즘의 시간복잡도는 여러 표기법으로 표현될 수 있다. 대표적인 표기법은 3가지이다. 1. $$\theta( )$$ 보통 함수의 최고차항에서 계수를 뗀 차수를 괄호 안에 넣어 표기한다. 예를 들면 다음과 같다. $$3n^2+2n-1 = \theta(n^2)$$ $$3n-1 = \theta(n)$$ $$3n-1 ≠ \theta(n^2)$$ 2. $$O( )$$ 함수의 최고차항(계수를 뗀)과 같거나 높은 차수를 괄호 안에 넣어 표기한다. 다음과 같은 예로 이해할 수 있다. $$3n^2+2n-1 = O(n^2)$$ $$3n-1 = O(n)$$ $$3n^2-1 ≠ O(n)$$ 3. $$\Omega( )$$ 함수의 최고차항(계수를 땐)과 같거나 낮은 차수를 괄호 안에 넣어 표기한다. 다음과 같은 예로 이해할 수..

병합정렬(Merge Sort)이란? 병합(merge)을 이용한 정렬 알고리즘이다. 그렇다면 병합은 무엇을 의미하는가? 두 개의 sorted list에서 각각의 키(list A의 key, list B의 key)의 대소를 비교하면서 새로운 병합된(merged) sorted list를 생성하는 것을 의미한다. 예를들어, 를 병합한다고 치자. 위처럼 작은 key를 우선으로 하여 새로운 list 맨 뒤에 추가해주는 과정을 병합이라고 한다. 병합(Merge)과정을 pseudo code로 나타내면 다음과 같다. Merge(A, p, q, r) n1 = q - p + 1 //n1은 array L의 크기 n2 = r - q //n2는 array R의 크기 L[1... n1 + 1]과 R[1... n2+1]을 새로운 배열..

알고리즘이란 문제(problem)를 해결하는 일련의 과정(procedure)이다. 어떤 알고리즘이 더 나은가를 판단하는 기준들 알고리즘의 성능(Performance) 1. Running Time Division, Addition, Multiplication 등이 해당된다. 2. Space Consumption 변수의 개수 (Number of variables), 배열의 크기(Size of an array) 등이 해당된다. 문제(Problem)와 그 Instance Problem 1부터 n까지 정수의 합인 S를 구하는 것 Problem Instance 1에서 100까지 정수의 합을 구하는 것 즉, Problem Instance is a set of Problem. 이다.