코딩테스트/알고리즘

그리디 알고리즘(Greedy Algorithm)이란?

개념 그리디 알고리즘은 "탐욕 알고리즘" 또는 "욕심쟁이 알고리즘" 이라고도 불린다. 말 그래도 탐욕스러운 욕심쟁이이기 때문에 선택의 순간마다 최적의 선택을 하여 전체적으로도 최적이길 바라는 방법이다. 선택의 순간마다 최적의 선택을 하여 해답을 만들었다고 해서 그것이 최적의 해답이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용하는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 탐욕 알고리즘을 적용하기 위한 2가지 조건 1. 탐욕스러운 선택 조건 (Greedy Choice Property) => 앞의 선택이 이후의 선택에 영향을 주지 않는 것 2. 최적 부분 구조 조건 (Optimal Substructure) => 문제에 대한 최적해가 부분 문제에 대해서도 최적해라는 것 위 조건이 성립하지 ..

삽입 정렬(Insertion Sort)이란?

개념 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 즉, 삽입 정렬은 2번째 요소부터 시작하여 앞 쪽과 비교하여 위치를 지정한다. 삽입 정렬에서는 정렬할 자료가 2개의 부분집합인 S(Sorted)와 U(Unsorted)로 나뉘어져 있다. 정렬된 앞부분의 요소들은 부분집합 S이고, 정렬되지 않은 나머지 요소들은 부분집합 U이다. 부분집합 U에서 요소를 하나씩 꺼내서 이미 정렬된 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다. 따라서 S의 요소는 1개씩 늘리고, U의 요소는 1개씩 줄인다. 이렇게 U의 요소를 모두 S에 삽입하여 공집합이 되면 삽입 정렬이 끝난다. 과정 시작 지점이 있으..

버블정렬(Bubble Sort)이란?

개념 버블 정렬은 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다. 과정 (굵은 글자는 인접한 두 개의 비교를 뜻하고, 빨간색은 자리 교환이 이루어진 것) {16, 2, 31, 14, 5} 리스트가 있을 때 버블 정렬을 시작하면 1회전 {2, 16, 31, 14, 5} ⇒ (16, 2) 비교하여 16이 더 크므로 자리 교환 {2, 16, 31, 14, 5} ⇒ (16, 31) 비교하여 31이 더 크므로 자리 교환 안함 {2, 16, 14, 31, 5} ⇒ (31, 14) 비교하여 31이 더 크므로 자리 교환 {2, 16, 14, 5, 31} ⇒ (31, 5) 비교하여 31이 더 크므로 자리 교환 1회전을 끝내면 가장 큰 자료인 31이 맨 뒤로 이동하게 된다. 2회전 1회전 때 나온 맨 뒷자리를 ..

선택정렬(Selection Sort)이란?

개념 선택 정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다. 과정 주어진 리스트 중 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. (패스(pass)) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 과정 - 그림설명 1단계 : 첫 번째 자리를 기준 위치로 정하고, 전체 원소 중 가장 작은 원소인 2를 선택하여 자리를 교환한다. 2단계 : 두 번째 자리를 기준 위치로 정하고, 1번 위치를 제외한 나머지 원소 중 가장 작은 원소인 10과 교환한다. 3단계 : 세 번째 자리를 기준 위치로 정하고, 1번과 2번 위치를 제외한 나머지 원소 중 가장 작은 16과 교환한다. 4단계 : 네 번째 자리를 기준 위치로 정하고, 1번과 2번과 ..

시간복잡도 Big-O(빅오)란?

알고리즘이란? 어떤 문제나 목적을 달성하기 위해 거쳐야 하는 여러 과정들을 의미한다. 이 과정들은 다양하고, 상황에 따라 알고리즘은 모두 다르다. 따라서 상황에 맞게 시간 복잡도가 가장 낮은 알고리즘을 선택하여 사용한다. (효율적이고 사용 환경에 최적인 알고리즘을 선택하여 사용한다.) 일반적으로 알고리즘의 성능 분석은 실행에 필요한 공간 측면에서 분석하는 공간 복잡도, 실행 소요시간 측면에서 분석하는 시간 복잡도를 추정하여 평가를 한다. 알고리즘의 실행 시간이란? 알고리즘의 실행 시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다. 이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 컴파일러 속도에 달려있다. 알고리즘의 실행 시간을 두 부분으로 나누면 다음과 같다. 입력값의 크기에 따른 알고리즘의 실..