아이테킨의 끄적끄적

먼저 이 글은 나동빈님의 '이것이 취업을 위한 코딩테스트이다' 이진탐색 파트를공부하고 정리한 것임을 밝힙니다. 순차탐색(Sequential Search) 리스트 안에서 특정 원하는 데이터를 찾으려고 할때 가장 먼저 떠올릴 수 있는 아이디어는 처음부터 하나하나 확인하면서 일치하는 데이터의 인덱스를 뽑아내는 것이다. 이를 순차탐색(Sequential Search) 이라고 한다. 반복문과 조건문을 적절히 이용하면 큰 어려움 없이 만들어볼 수 있다. 이때의 시간복잡도는 당연히 O(N)이다 이제 더 빨리 찾아낼 수 있는 이진탐색에 대해서 알아보자. 이진 탐색(Binary Search) 먼저 이진탐색은 데이터가 정렬이 되어있는 상태에서 사용할 수 있는 알고리즘이다. 이진탐색의 아이디어는 위치를 나타내는 변수 3개를..

∴다이나믹 프로그래밍에 대한 개념정리 및 예제풀이 마지막으로 DP 정복하는것을 향해서!!! 다이나믹 프로그래밍(Dynamic programming, DP)란? 다이나믹 프로그래밍이란 복잡한 하나의 문제를 간단한 여러개의 중복되는 문제로 나누어 같은 방식으로 풀어 답을 구하는 방법을 말한다. 나는 보통 동적(Dynamic)이라는 용어를 보면 '계속해서 움직이는' 이라는 뜻으로 이해했다. 그러나 여기서의 동적(dynamics)이라는 단어는 DP를 이해하는데 직관적으로 도움을 주지 못하는듯 하다. 뒤에서 언급하겠지만 그보다는 '작은 중복문제들을 기억하며 푼다'라는 의미로 받아들이는 것이 좋을 것 같다. 그래서 앞으론 dyanmic programming보다는 DP라고 부르려고 한다. (사실 이렇게 해야 나도 헷..

수많은 정렬 알고리즘 중 대표적인 5가지 정렬 알고리즘에 대해서 정리해보려고 한다. 버블 정렬(bubble sorting) 선택 정렬(Selection sorting) 삽입 정렬(insertion sorting) 병합 정렬(Merge sorting) 퀵 정렬(Quick sorting) 셸 정렬(shell sorting) 힙 정렬(heap sorting) 우선 시간복잡도 기준으로 나눠보자 O(N²) 버블 정렬 선택 정렬 삽입 정렬 O(N log₂ N) 병합 정렬 퀵 정렬 셸 정렬 힙 정렬 아래에 있는 정렬들이 일단 시간복잡도가 더 빠르니 성능이 좋은 정렬 알고리즘이라 생각해도 될 것 같다. 그러나 언제나 그렇듯 모든 상황에서 아래의 알고리즘이 더 좋다고 단정지을 수는 없다. 1. 버블 정렬(Bubble s..