분할 정복(Divide and Conquer) 분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임을 말한다. 분할 정복(Divide and conquer)은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼개나간 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다. 대표적인 분할 정복 알고리즘으로는 병합 정렬이 있다. 위의 이미지에 보이듯이 병합 정렬은 상단에서 '분할' 하고, 중앙에서 '정복' 하고, 하단에서 '조합' 한다. 이를 좀 더 구체적으로 살펴보면 아래의 이미지와 같다. 중요 개념 정리 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다. 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다. 조합: 하위 문제에 대한 결과를 ..

이분 탐색(binary search)란? 이분탐색(binary search)은 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법이다. 이분탐색을 사용하는 이유와 시간 복잡도 내가 원하는 값을 빠르게 찾을 수 있기때문에! 정렬된 데이터에서만 사용 가능한 제약사항이 존재하지만 선형 검색과는 달리, 이진 검색에서는 주목할 원소를 다음에 검색할 범위의 중간 지점으로 단숨에 이동하게 된다. 일반적으로 n개의 원소가 오름차순으로 정렬된 배열에서 이진 검색에서 한 단계씩 진행할 때마다 검색 범위는 거의 반으로 좁혀진다. 따라서 시간 복잡도는 O(logN) 으로 굉장히 빠르다. 아래 그림에서 차이를 확인해보자. 선형탐색 vs 이분탐색 ..

힙(Haep) 이란? 힙(Heap)이란 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 힙은 '부모의 값이 자식의 값보다 ' 부모 - 자식 간 두 값의 대소 관계가 일정해야 한다. 또한 이 조건을 만족하는 완전 이진 트리이다. 참고: 힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다. HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 힙을 사용하는 이유와 시간 복잡도 배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(n)의 시간복잡도를 가지게 된다. 1. 이에 반해, 배열에 데이터를 넣고, 힙을 만드는 과정의 시간 복잡도는 O(log n) 2. 따라서 힙 정렬은 원소의 개수만큼 작업을 ..

큐(Queue)는 스택과 같이 데이터를 임시 저장하는 자료구조이다. 하지만 스택과는 다르게 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조이다. 용도 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용한다. 서로 다른 쓰레드 사이 또는 프로세스 사이에서나 네트워크를 통해 자료를 주고받을 때 자료를 일시적으로 저장하는 용도로 많이 사용한다. 스택 용어 정리 인큐(enqueue): 큐에 데이터를 추가하는 작업 디큐(dequeue): 데이터를 꺼내는 작업 프론트(front): 데이터를 꺼내는 쪽(가장 앞에 있는 원소) 리어(rear): 데이터를 넣는 쪽(가장 뒤에 있는 원소) 스택과 마찬가지로 큐 또한 배열을 사용하여 구현이 가능하다. 참고로 인큐는 밀어 넣기라고도 표현한다..

데이터를 임시 저장하는 기본 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식이다. LIFO(last in first out)란 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 자료 구조이다. 용도 스택은 비교적 구현이 쉬운 편임에도 활용도가 크다. 예를 들어서 브라우저에서 우리가 이전에 들어갔던 페이지로 돌아가기 위해서 '뒤로가기' 버튼을 눌렀을 때도 스택이 사용되고, Ctrl + Z (Undo) 작업도 스택을 이용한 작업이다. 또한 함수가 함수 자신을 호출하는 것(재귀 함수)도 스택에 기반을 두고 있다.(기회가 되었을 때 메모리의 구조를 공부하여 포스팅 해봐야겠다!) 또한 우리가 코드를 돌렸을 때 수많은 에러 내용을 Traceback으로 확인할 수 있을텐데, 이것도 스택에 기반해서 에러 ..