Algorithm

컴퓨터공학을 전공하고 있는 학생이라면, 지금쯤 알고리즘이란 무엇인가라고 정의 내릴 수 있을 것이다. 교수님에 따라, 전공책에 따라 약간의 차이는 있겠지만, 일반적으로 우리는 어떤 문제를 해결하기 위한 명확한 절차(과정)나 규칙, 명령어들의 집합을 알고리즘이라고 일컫는다

시간 복잡도(Time Complexity)는 알고리즘이 입력 크기(𝑛)에 따라 수행하는 연산 횟수를 표현한 것이다.즉, 입력 크기(n)가 커질 때 알고리즘의 실행 시간이 얼마나 증가하는지를 나타내는 척도라는 것!위 사진은 삽입정렬 의사코드를 분석한 사진이다tⱼ 는 “

지금까지 우리는 알고리즘의 올바름(Correctness)에 대해 알아 보았다. 그 효율성(Efficiency) :최대한 빠르게 동작하고, 메모리를 적게 사용해야 함. 시간 효율성(Time Efficiency)과 공간 효율성(Space/Memory Efficiency)

지금까지 우린 Insertion Sort에 대해서 공부했다.삽입정렬만으로 모든 Sorting문제들을 해결하면 얼마나 좋을까?하지만 애석하게도 우리가 공부했던 삽입정렬을 쓸 일은 생각보다 많지 않을 것이다🥲세상에는 그것보다 더 효율적인 정렬 방법이 너무나도 많다.그 중

분할 정복 시간복잡도 분할 정복 알고리즘의 런타임을 분석하기 위해선 점화식을 사용해야한다 그렇다면 점화식이란 무엇일까? 1️⃣ 점화식(Recurrence Relation)이란? 점화식이란 어떤 수열에서 특정 항을 이전 항(또는 여러 개의 이전 항)과의 관계로 정의하

Master Method

알고리즘의 procedure 중 random한 어떤 선택이 들어가면 그것을 Randomized Algorithms이라고 한다.Ex) BogoSort 아주 비효율적인 "무작위 섞기 → 확인" 알고리즘이다.Ex) QuickSort일반적인 퀵소트는 pivot을 무작위로 선택

Random Algorithm의 일종인 Linear-Time Selection, 그 중에서도 Quick Selection에 대해 알아보자

더 좋은 피봇을 고르는 방법 우리가 관심 있는 건 Linear-Time Selection 알고리즘이니까, 시간 복잡도가 Θ(n) 이 되도록 피벗을 잘 골라야 한다. 그렇다면 가장 이상적인 상황은 무엇일까? 당연히 피벗이 리스트를 정확히 반으로 나눠주는 경우 일것이다.

우리는 지금까지 몇 가지 정렬 알고리즘을 살펴봤다.Insertion Sort(삽입 정렬)과 Quick Sort(퀵 정렬)의 최악의 경우는 Θ($n^2$)Merge Sort(병합 정렬)의 최악의 경우 시간복잡도는 Θ($nlogn$)이 알고리즘들의 공통점은 "비교(com

이전 시간까지 우리는 다양한 정렬 알고리즘에 대해서 공부했다.지금부터는 자료구조를 기반으로한 다양한 알고리즘에 대해 알아보자.그 중에서도 이번 시간엔 BST (Binary Search Tree), 특히 Red-Black Tree를 배워볼 것이다.컴퓨터 과학에서 가장 중