이론/알고리즘
그리디 알고리즘
그리디 알고리즘 그리디 알고리즘이란 지금 주어진 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 결과를 선택한 결과 값이 전체적으로도 최선이기를 바라는 알고리즘이다. 일반적인 그리디 알고리즘 풀이 방법을 적어보자면 아래와 같은 흐름을 따른다. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 탐색 범위를 줄여도 올바른 답을 낸다는 것을 수학적으로 증명한다. 알고리즘을 구현한다. 그리디 알고리즘은 모든 경우에서 통하는 알고리즘은 아니다. 현재에 약간 손해보더라도 전체적으로 봤을 때는 이득인 경우에 통하지 않는데, 예를 들자면 유명한 마시멜로 이야기와 같이 지금 당장은 마시멜로를 1개를 받을 수 있지만 조금 기다리는 경우 2개를 받을 수 있는 경우 그리디 알고리즘으로 풀면 틀린 경우가..
이분탐색(Binary search)
- 이분탐색이란? 이분탐색이란 정렬이 되어있는 배열에서 원하는 데이터를 찾기 위해 순서대로 찾아보는 방법 대신에 탐색 범위를 절반으로 줄여나가며 찾는 탐색 방법이다. boj 문제 중에 이분탐색을 요구하는 문제가 있어서 문제를 보면서 이분탐색의 개념을 정리했다. - boj 1920 수 찾기 https://www.acmicpc.net/problem/1920 예시로 A 배열에 '3 5 6 9 10 12 14 26 35 41' 이 주어졌다고 하고, 14가 있는지 알아본다고 하자. 입력 받은 후에 sort 함수를 이용해서 정렬하면 앞과 같이 정렬된 상태일 것이다. 원래 문제는 A 안에 14가 있는지만 확인하면 되지만, 14가 A 안에서 위치하는 인덱스를 반환하는 함수를 구현해보려고 한다. st와 e..
기본 정렬(선택 정렬, 버블 정렬, 삽입 정렬)
목차 선택 정렬(Selection sort) 1-1. 선택 정렬이란? 1-2. 선택 정렬 구현 버블 정렬(Bubble sort) 2-1. 버블 정렬이란? 2-2. 버블 정렬 구현 삽입 정렬(Insertion sort) 3-1. 삽입 정렬이란? 3-2. 삽입 정렬 구현 시간복잡도 비교 1. 선택 정렬(Selection sort) 1-1. 선택 정렬이란? 자리가 정해져 있는 정렬 알고리즘이다. 주어진 배열이나 리스트에서 최솟값을 찾고 그 값을 맨 앞의 값과 위치를 바꾼다. 같은 방법으로 나머지 값들을 정렬한다. 아래에 8, 5, 1, 3, 6이 담겨 있는 배열을 선택 정렬로 정렬해보자. 우선, 제일 앞에 있는 8의 위치를 i라고 하고, j는 i다음 위치부터 존재하는 최솟값의 위치를 가져온다. 그리고 그 위치..