알고리즘

알고리즘 01. 선택 정렬과 삽입 정렬 선택 정렬의 정의 가장 작은 것을 선택하여 앞으로 보내는 정렬 기법 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산 --> O(N^2) 시간 복잡도 선택 정렬의 과정 image.png image.p

알고리즘 02. 퀵 정렬 퀵 정렬의 정의 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법 교체하는데에 N번, 교체 이후 원소가 반으로 나누어져 전체 원소를 나누는데 평균 log N번 소요 --> O(NlogN)의 시간 복잡도 퀵 정렬의 과정 ima

알고리즘 03. 계수 정렬 계수 정렬의 정의 Counting Sort는 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘 각 데이터를 바로 크기 기준으로 분류함 --> O(N)의 시간 복잡도 계수 정렬의 과정 > 계수 정렬에서는 숫자 자체가 인덱스가 됨 i

알고리즘 04. 기수 정렬 기수 정렬의 정의 Radix Sort는 자릿수를 기준으로 차례대로 데이터를 정렬 각 자릿수를 기준으로 분류하여 가장 큰 자릿수가 D일 때 --> O(DN)의 시간 복잡도 기수 정렬의 과정 image.png image.png ima

알고리즘 05. 이진 트리의 구현 및 순회 이진 트리의 순회 image.png 전위 순회 자기 자신 출력 왼쪽 자식 출력 오른쪽 자식 출력 > 전위 순회 결과 : 30 - 17 - 5 - 23 - 48 - 37 - 50 중위 순회 왼쪽 자식 출력 자기 자

알고리즘 06. 우선순위 큐 우선순위 큐의 필요성 우선 순위를 가진 데이터들을 저장하는 큐 데이터를 꺼낼 때 우선 순위가 높은 데이터가 가장 먼저 나오는 특징 운영체제의 작업 스케쥴링, 정렬, 네트워크 관리 등에서 적용 우선순위 큐와 큐의 차이점 일반적인 형태

알고리즘 07. 순차 탐색과 이진 탐색 순차 탐색의 방법 Sequential Search는 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법 찾은 뒤 해당 인덱스를 반환 image.png image.png image.png ![image.pn

알고리즘 08. 깊이 우선 탐색 깊이 우선 탐색의 정의 Depth First Search는 깊이를 우선적으로 탐색하는 알고리즘 전체 노드를 맹목적으로 탐색하고자 할 때 사용 스택 자료구조에 기초 > 깊이 우선 탐색은 모든 경우의 수를 탐색하고자 할 때 쉽게 사용

알고리즘 09. 너비 우선 탐색 너비 우선 탐색의 정의 Breadth First Search는 너비를 우선으로 하여 탐색하는 알고리즘 맹목적으로 전체 노드를 탐색할 때 사용 큐 자료구조에 기초 > 고급 그래프 탐색 알고리즘에 자주 활용 너비 우선 탐색의 과정

알고리즘 10. 이진 탐색 트리 이진 탐색 트리의 정의 Binary Search가 항상 동작하도록 구현한 이진 트리 탐색 속도 극대화 시킨 자료구조 항상 부모 노드가 왼쪽 자식보다 크고 오른쪽 자식보다 작음 이진 탐색 트리의 탐색 한번 확인 할 떄마다 확인할

알고리즘 11.AVL 트리 AVL 트리의 정의 균형이 갖춰진 이진트리 완전 이진 트리는 검색 시 O(log N)의 시간 복잡도 유지 AVL 트리는 간단한 구현으로 완전 이진 트리에 가까운 형태가 되도록 함 > AVL은 해당 논문을 발표한 G.M. Adelson-

알고리즘 12. 프림 알고리즘 최소 신장 트리 신장 트리란 특정한 그래프에서 모든 정점을 포함하는 그래프 최소 신장 트리는 스패닝 트리 중에서 간선의 가중치 합이 가장 작은 트리 image.png image.png 프림 알고리즘의 순서 그래프에서 정점 하나

알고리즘 13. 그래프-다익스트라의 최단 경로 다익스트라의 최단 경로 Dijkstra's Shortest Path Algorithm은 프림 알고리즘과 흡사 각 간선에 대한 정보를 우선순위 큐에 담아 처리 음의 간선이 없을 때 정상 동작하며 현실에서는 음의 간선이

알고리즘 14. 세그먼트 트리 구간 합 구간 합은 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 것을 의미 선형적으로 구간 합 구하기 image.png image.png > 선형적으로 구간 합을 구하는 과정은 O(N)의 시간

알고리즘 15. 인덱스 트리 트리 구조로 구간 합 구하기 세그먼트 트리는 구현 과정이 복잡하고 어려워 더 쉽게 구할 방법이 필요 인덱스 트리는 간단하며 O(log N)의 시간복잡도 가짐 인덱스 트리는 세그먼트 트리에 비해 메모리 효율성도 높음 인덱스 트리의 원리

알고리즘 16. KMP 문자열 매칭 단순 비교 문자열 매칭 단순 비교 문자열 매칭 알고리즘은 두 문자열을 처음부터 끝까지 계속 비교 단순 비교 문자열 매칭 알고리즘은 O(NM)의 시간 복잡도 가짐 단순 비교 문자열 과정 image.png image.png

알고리즘 17. 라빈 카프 문자열 매칭 라빈 카프 문자열 매칭의 특징 해시(Hash)를 활용하는 알고리즘 O(N+M)의 시간 복잡도를 가짐 아스키 코드 기반의 해시 함수(Hash Function)을 이용해 해시 값을 구함 연속적인 문자열이 이어지는 상황이므로 해시