이번 글은 눈 앞에 보이는 최선의 선택만 하는 알고리즘 Greedy 알고리즘에 관한 내용입니다. Greedy 알고리즘은 이전에 다뤘던 Dynamic Programing 이나 Divide and Conquer 알고리즘처럼 사용하기 위한 필수 조건이 있는 것은 아닙니다. 하지만 미래는 내다보지 않고 눈 앞에 보이는 최선의 선택만 하는 탐욕적인 알고리즘이기 때문에 최적의 답을 찾기 위한 조건은 있습니다. 최적의 부분 구조를 갖고 각 단계에서 탐욕스러운 선택이 각 문제에서 최종 답을 구하기 위한 최선의 선택이라는 탐욕적 선택 속성을 갖고 있다면 최적의 답을 보장할 수 있습니다. 간단하고 빠르다는 장점을 갖고 있지만 최적의 답을 보장해주는 조건에 사용하는 것이 아니라면 최적의 답을 보장받지 못한다는 단점을 갖고 ..

이번 글은 하나의 문제는 단 한 번만 풀도록 하는 효율적인 알고리즘, Dynamic Programming에 대해 다룹니다. 동적 계획법(DP, Dynamic Programming)은 한 번 푼 문제는 저장해놓고 공간복잡도를 늘리는 대신 시간복잡도는 줄이는 방식입니다. 지난 포스팅에서 합병 정렬과 퀵 정렬을 하며 다뤘던 분할 정복 방식(Divide and Conquer)과 유사한 알고리즘입니다. 분할 정복 방식도 문제를 더 작은 문제로 나눠서 풀었었죠? 동적 계획법도 비슷한 조건을 갖고 있습니다. DP를 적용하기 위한 2가지 조건입니다. 1. 최적 부분 구조(Optimal Substructure) - 전체 문제의 답을 부분 문제의 답을 이용하여 풀 수 있는 구조 2. 중복되는 부분 문제(Overlappin..

지난 포스팅에서 선형 탐색과 이진 탐색에 대한 내용을 다뤘습니다. 이진 탐색을 하기 위해서는 정렬된 상태여야 한다는 조건이 있었죠. 그래서 이번 포스팅은 정렬에 관한 내용을 다루겠습니다. 정렬? 그냥 sort메서드나 sorted함수 사용하면 안되나? 라고 생각하실 수 있지만 아래 그림처럼 각 정렬 알고리즘은 시간/공간 복잡도가 각 상황에 따라 다르기 때문에 상황에 맞는 알고리즘을 사용하는 것이 효율적인지 생각해야 합니다. 순서 1. 선택정렬 2. 삽입 정렬 3. 합병 정렬 4. 퀵 정렬 모든 정렬의 설명은 내림차순 기준입니다. 1. 선택 정렬(Selection Sort) 선택 정렬은 현재 위치에 들어갈 값을 선택하여 정렬하는 것입니다. 아래 그림과 같이 배열 값 중 가장 작은 값을 찾습니다. 가장 작은 ..

이번글은 가능한 모든 경우의 수를 시도하는 알고리즘 Broute Force에 대해 알아보겠습니다. 1. Broute Force Brute Force 알고리즘은 무차별 대입 공격으로 가능한 모든 경우를 시도하는 순진한 알고리즘입니다. 가능한 모든 경우를 시도하기 때문에 완전 탐색 알고리즘입니다. 직관적이고 명확한 알고리즘으로 답을 확실하게 알 수 있지만 input이 크면 비효율적이라는 단점을 갖고 있기 때문에 작은 경우에만 효율적입니다. Brute Force알고리즘으로 문제를 해결하는 과정은 다음과 같습니다. 이전 포스팅에서 다뤘던 순차 탐색도 Brute Force알고리즘을 이용하여 문제를 푸는 방식입니다. 선형 구조를 모두 탐색하는 방법 중 이전 포스팅에 다뤘던 선형 탐색(순차 탐색)도 Brute For..

이번 글은 선형구조에서 특정 값을 찾고 싶을 때 어떻게 탐색하는 것이 효율적인가에 대한 알고리즘을 설명합니다. 순서 1. 선형탐색과 이진탐색 이론 2. 파이썬 구현 1. 선형탐색과 이진탐색 이론 만약 도서관에서 "여덟단어" 책을 찾으려고 할 때 어떻게 찾을 것인가요? 도서관에 책이 왼쪽에서 오른쪽으로 자음 순서대로 있다고 할 때 왼쪽부터 순서대로 찾을 수도 있고 중간 자음인 'ㅅ'을 찾은 후 'ㅅ'을 기준으로 오른쪽 책들만 확인해서 찾아볼 수도 있을 것입니다. 이처럼 왼쪽부터 차례대로 탐색하는 것을 선형탐색 또는 순차탐색, 중간 위치를 찾아서 탐색할 범위를 줄여 탐색하는 것을 이진탐색이라고 합니다. 아래 그림처럼 주어진 데이터를 처음부터 검색하는 것이 선형탐색이고, 이진탐색은 정렬된 데이터의 중앙값을 이..

이번 글은 그래프에 관한 내용입니다. 그래프는 연결되어 있는 객체 간의 관계를 표현하는 자료구조입니다. 실생활에서 자주 볼 수 있는 그래프는 지하철 노선도, 항공노선도, 전기회로 등이 있습니다. 항공노선도는 도시들이 항공편으로 어떻게 연결되어 있는지를 확인할 수 있고 전기회로는 각 소자들의 연결 관계를 확인할 수 있습니다. 그래프는 다양한 객체가 서로 복잡하게 연결된 구조를 표현할 수 있습니다. 그래프 이론 그래프와 관련된 다양한 문제를 연구하는 학문 분야로 수학자인 오일러가 최초로 창안하였습니다. 쾨니히스베르크에 7개의 다리가 있었는데 사람들은 같은 다리를 두 번 이상 건너지 않으면서 모두 건널 수 있을까에 대한 물음을 가지고 있었습니다. 1736년 오일러는 7개의 다리에는 그러한 경로가 존재하지 않는..