알고리즘 정리

이제 알고리즘 공부를 하며 동시에 정리도 하려한다. 사실 전에 파이썬으로 어느정도 진행하였지만, 시간이 지나서 잘 기억이 안나는 것도 있고 코딩테스트용 언어를 파이썬에서 C++로 바꾸기로 했기에 다시 공부할 필요성을 느꼈다. 이제부터 정리하게 될 알고리즘 공부 내용들은

선택정렬의 아이디어는 매우 간단하다. 오름차순을 기준으로, 주어진 숫자들 중 가장 작은 숫자를 찾고 맨 앞에 놓는 것이다. 이것을 반복해서 결론적으로 오름차순 정렬을 완성시키는 것이 바로 선택 정렬이다. 매우 간단하게 구현할 수 있지만 O(n²)이라는 시간 복잡도를 가

버블 정렬은 매우 직관적이고 간단한 알고리즘이다. 옆에 있는 값과 숫자를 비교해서 더 작은 값을 앞으로 보낸 다는 것이 버블 정렬의 아이디어이다.(오름차순 기준이다.) 이 방법을 사용할 경우 뒷쪽 부터 정렬이 완성된다. 매우 단순하고 직관적이지만 시간 복잡도가 O(n²

삽입 정렬은 각 숫자들을 적절한 위치에 삽입하는 알고리즘입니다. 여기서 가장 KEY포인트는 필요할 때만 위치 변경이 이루어진다는 것입니다. 오름 차순 기준으로 자신보다 작은 원소를 만났을 때만 위치 변경이 이루어집니다.(비교를 통해 필요할 때만 자신의 위치를 찾아서 들

퀵 정렬은 앞에 설명했던 정렬 알고리즈보다 매우 빠른 속도를 가지고 있습니다. 퀵 정렬은 대표적인 분할 정복 알고리즘으로 O(n\*logn)의 시간 복잡도를 가집니다. 퀵 정렬은 특정한 값(pivot)을 기준으로 큰 숫자와 작은 숫자를 나누는 것을 메인 아이디어로 합니

병합 정렬은 분할 정복을 사용한 알고리즘 입니다. 퀵 정렬 같은 경우에도 분할 정복을 사용하지만 피벗 값에 따라서 최악의 경우 O(n²)의 시간 복잡도를 가질 수 있습니다. 하지만 병합 정렬의 경우 기본적으로 정확히 반으로 나누고 정렬하는 것이 핵심이므로 O(n\*lo

힙 정렬 힙 정렬은 힙 트리 구조를 이용하는 정렬 방법으로, 매우 빠른 알고리즘입니다. 용어 정리 > 트리 데이터가 나무가 가지를 뻗는 것처럼 서로 연결되어 있는 구조 > 이진 트리 트리 구조에서 모든 노드의 자식 노드가 2개 이하인 노드 > 완전 이진 트

계수 정렬은 범위 조건이 있는 경우 엄청 빠른 알고리즘입니다. 이 알고리즘의 시간 복잡도는 O(n)으로 엄청 빠른 속도를 자랑합니다. 계수 정렬의 메인 아이디어는 단순하게 크기를 기준으로 갯수를 세는 것 입니다. 이 알고리즘은 위치를 바꾸거나 할 필요 없이 모든 데이터

BFS란 너비 우선 탐색을 말합니다. 맹목적인 탐색을 할 때 사용됩니다. BFS는 최단경로를 찾는 문제를 해결할 때도 자주 쓰입니다. 자료구조는 Queue를 사용합니다.시작 노드를 큐에 삽입시작 노드 방문 처리큐에서 하나의 노드 꺼내기해당 노드에 연결된 노드 중 방문하

DFS는 깊이 우선 탐색을 뜻합니다. 이 DFS 또한 맹목적으로 각 노드를 탐색할 때 주로 사용됩니다. DFS는 자료구조로 stack을 사용해서 구현됩니다. 하지만 사실 스택을 안쓰고 재귀함수로도 구현이 가능합니다. 이유는 컴퓨터 자체가 구조적으로 항상 스택의 원리를