알고리즘, 자료구조/정리
-
버블 정렬 알고리즘 (Bubble sort Algorithm)알고리즘, 자료구조/정리 2023. 3. 27. 13:48
틀린 내용을 발견하신 경우 말씀 부탁드립니다! 🙇 버블정렬 알고리즘은 서로 인접한 두 개의 값을 비교하여 정렬하는 방식이다. 오름차순 정렬이라고 가정했을 때, 1회전이 끝나면 가장 큰 값이 맨 뒤에 위치하게 되며 각 회전이 끝날 때마다 비교해야하는 값이 하나씩 감소한다. 주어진 배열에서 값을 교환(swap) 하기 때문에 제자리 정렬 알고리즘에 속한다. 값을 정렬할 때 발생하는 교환 작업(swap)이 복잡하기 때문에 단순한 알고리즘임에도 불구하고 잘 쓰이지 않는다. Pseudo code n개의 요소로 이루어진 (정렬되지 않은) 배열을 오름차순으로 정렬하는 경우, (1회전 차) 첫 번째 값과 두 번째 값을 비교한다. 작은 값은 첫 번째 인덱스에, 큰 값은 두 번째 인덱스에 놓는다. (1회전 차) 두 번째 값..
-
선택 정렬 알고리즘 (Selection sort Algorithm)알고리즘, 자료구조/정리 2023. 3. 18. 12:05
틀린 내용을 발견하신 경우 말씀 부탁드립니다! 🙇 선택 정렬 알고리즘은 제자리(in-placing) 알고리즘 중 하나로, 결과 값을 만들기 위해 별도의 추가적인 메모리를 사용하지 않고 입력 배열의 메모리만 사용하는 정렬 방법이다. 제자리(in-placing) 알고리즘은 일반적으로 입력 값이 출력 값으로 덮어씌워지며, 입력 값을 출력 값으로 교체하거나 요소들의 위치를 바꾸는 방식으로 출력 값을 반환한다. 선택정렬 시각화 참고 Pseudo code n개의 요소로 이루어진 (정렬되지 않은) 배열이 있을 경우, 첫 번째 ~ n번째까지 탐색하며 기준에 맞는 요소를 찾은 뒤, 첫 번째 자리와 위치를 변경한다. 두 번째 ~ n번째까지 탐색하며 기준에 맞는 요소를 찾은 뒤, 두 번째 자리와 위치를 변경한다. 세 번째 ..
-
퀵 정렬 알고리즘 (Quick sort Algorithm)알고리즘, 자료구조/정리 2023. 3. 14. 13:35
틀린 내용을 발견하신 경우 말씀 부탁드립니다! 🙇 퀵 정렬은 분할 정복(Divide and conquer) 전략 중 하나로 재귀적 알고리즘에 해당한다. 분할 정복 전략은 그대로 해결할 수 없는 문제를 작은 문제로 분리하고 결과를 모아 원래의 문제를 해결하는 전략이다. 분할 정복 전략으로 문제를 풀기 위해선 아래 단계를 거친다. ① 문제가 기본단계가 될 때까지 나눈다 (Divide) ② 기본 단계를 해결한다 (Conquer) ③ 기본 단계의 답을 통합해 가장 큰 문제(원래 문제)의 답을 도출한다 (Combine) 분할 정복 전략 예시 가로 14, 세로 6인 직사각형을 똑같은 크기의 정사각형으로 나누면 총 몇 개의 정사각형이 반환되는가? 정사각형은 최대한 크게 만들도록 한다. 1. 주어진 직사각형을 최대한 ..
-
이진 탐색 알고리즘 (Binary search Algorithm)알고리즘, 자료구조/정리 2020. 8. 10. 10:32
이진 탐색 알고리즘(이분 탐색 알고리즘)은 정렬된 배열에서 특정 값의 위치를 찾는 알고리즘이다. 맨 처음 단계에서 정렬된 배열의 중간의 값을 임의의 값으로 선택한다. 선택한 임의의 값과 찾고자 하는 값의 크고 작음을 비교하여 탐색하는 방식이다. 만약 임의의 값이 찾는 값보다 클 경우, 임의의 값은 새로운 최댓값이 된다. 반대로 임의의 값이 찾는 값보다 작으면 해당 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있으나, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다(O(l ogN)). BinarySearch(A[0..N-1], value, low, high) { if (high value) return BinarySearch(A, value,..
-
동적 계획법 알고리즘 (Dynamic programming Algorithm)알고리즘, 자료구조/정리 2020. 7. 30. 12:00
동적 계획법 알고리즘이란 동적 계획법이란 하나의 복잡한 문제를 여러 개의 간단한 하위 문제로 나누어 푼 다음, 이를 결합하여 답을 도출해내는 방법이다. 나누어진 하위 문제들의 결과를 따로 저장해두었다가 이후 동일한 문제가 나왔을 시 저장해둔 결과를 가져다가 쓰면 같은 문제를 반복해서 풀지 않아도 되기 때문에 문제를 해결하는데 시간을 절약할 수 있다. 즉 한번 푼 하위 문제는 중복해서 풀지 않는다. 그렇다면 어떤 문제인 경우에 동적 계획법으로 해결할 수 있을까? 우선 문제를 나누어봤을 때 반복되는 작은 문제들이 나와야 되고, 전체 문제의 최적해가 부분 문제의 최적해들로 구성되는지 확인해야 된다. 이 두 가지 조건 모두 충족한다면 동적 계획법으로 풀 수 있는 문제일 것이다. 지금까지 썼던 내용을 간단히 요약..
-
너비 우선 탐색 알고리즘 (BFS Algorithm)알고리즘, 자료구조/정리 2020. 7. 18. 15:45
DFS(Depth-First Search) 알고리즘에 이어 BFS(Breadth-First Search)를 정리해본다 BFS(Breadth-First Search) 탐색 알고리즘 중 하나인 BFS는 트리의 root 노드(그래프일 경우 임의의 노드)부터 시작해 모든 이웃 노드를 탐색한 뒤 아래 depth로 내려가 탐색을 반복하는 방식이다. 즉 시작 노드에서 가장 가까운 노드들을 모두 탐색하고, 그다음으로 가까운 노드들을 모두 탐색하는 것. DFS 알고리즘과 달리 BFS 알고리즘은 재귀 함수로 구현할 수 없다. 현재 노드에서 가까운 노드들을 모두 탐색한 뒤 그다음으로 가까운 노드들을 탐색하기 위해선 queue(FIFO: First In First Out)을 이용해야 하고, 어떤 노드를 방문했는지에 대해 검사..
-
깊이 우선 탐색 알고리즘 (DFS Algorithm)알고리즘, 자료구조/정리 2020. 7. 13. 14:32
탐색 알고리즘 문제를 볼때마다 멍해지는 관계로 이번 기회에 확실히 짚고 넘어가야겠다. 이번 포스트에서는 DFS를 정리한다. DFS (Depth-first search) 미로 문제 해결 전략으로 연구된 DFS는 트리 및 그래프 구조를 탐색하는 알고리즘 기법이다. 트리의 경우엔 root node부터, 그래프의 경우엔 임의의 node부터 맨 밑까지 탐색하면 되고, 이전에 방문한 노드는 다시 방문하지 않는다. 그림으로 표현하면 아래와 같다. 일반적으로 DFS 알고리즘은 그래프 전체를 탐색하는데 사용한다. 시간 복잡도는 O(|V|+|E|)으로 그래프 사이즈만큼의 선형 시간이 걸린다. (V는 정점의 수, E는 간선의 수를 나타낸다) 즉, 정점이 늘어나는만큼 시간도 오래 걸리기 때문에, 탐색 과정이 시작 노드에서 한..