어떤 문제를 해결하는데 있어서 나오는 알고리즘은 다양할 수 있다. 간단한 예로 주어진 정수 n의 절대값을 구하라는 문제가 있을 때, > 정수 n을 제곱한 뒤, 그 값에 다시 루트를 씌운다. 정수 n이 음수인지 확인하고, 조건이 참이면 그 값에 -1을 곱한다. 이처럼
선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한
버블정렬은 선택정렬과 유사한 개념으로 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.인접한 2개의 원소의 크기를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.구현이 매우 간단하고, 소스코드가 직관적이다.정렬하고자 하는 배열 안에서 교환하는 방식이므로
삽입 정렬 개념 삽입 정렬은 선택정렬과 유사하지만 좀 더 효율적인 정렬 알고리즘이다. 삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 방식이다. 삽입정렬의 경우,
병합 정렬의 기본 개념 병합정렬은 분할정복 알고리즘을 기반으로 정렬되는 방식이다. 병합 정렬은 우선 입력을 반으로 나눈뒤 전반부와 후반부를 각각 독립적으로 정렬하여 마지막으로 정렬된 두 부분을 합쳐서 정렬된 리스트를 얻는다. 이때 전반부와 후반부를 정렬할 때에도 반으
퀵정렬은 병합정렬과 유사한 개념으로 선행 작업을 한 다음 재귀적으로 작은 문제를 해결하며 정렬하는 방법이다.하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체를 정
힙은 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조이다.힙정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다.추가적인 배열이 필요하지 않다.시간복잡도가 항상 $O(nlogn)$로 보장된다
셸 정렬이란 Donald L. Shell이 제안한 방법으로 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안하여 삽입정렬을 보완한 알고리즘이다.삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다.즉, 만약 삽입되어야 할
이전에 $O(n^2)$ 알고리즘은 자신의 옆에 수와 비교해야하므로 $n^2$의 한계를 벗어나지 못한다고 하였다. $O(nlogn)$ 알고리즘은 자신의 옆에 수 말고, 건너건너 수와 비교하여 하나 당 logn시간의 비교를 하여 $O(nlogn)$시간을 완성할 수 있었다.
업로드중..
요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고리즘이다.검색이 종료되는 종료 조건
이진 탐색법은 탐색의 대상인 데이터가 오름차순으로 정렬되어 있는 경우에 데이터를 이분화하면서 특정 값을 탐색하는 알고리즘이다.img가운데에 있는 요소를 먼저 탐색한다.조건이 가운데 요소보다 정렬순서가 빠른지 느린지를 보고, 탐색범위를 좁힌다.탐색범위를 좁혔으면 다시 한
재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다. 이떄 이루어지는 호출을 재귀호출이라고 한다. 재귀 함수 단순 예제위 예제는 어느 정도 출력하다 최대 재귀 깊이 초과 오류가 발생하는데, 이는 python에서 메모리 제한을 두었기 때문이다.(RecursionErr
동적계획법(다이나믹 프로그래밍) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 모든 작은 문제들을 한 번만 풀어야 한다. 따라서 정답을 구한 작은 문제의 답은 어딘가에 메모해놓는다. 다시 그 보다 큰 문제를 풀어나갈 때, 똑같은 작은 문제가
그리디 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법으로 최적해를 구하는 데에 사용되는 근사적인 방법이다.순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만 그 선택들을 계속 수집하여 최종적(전역적)인 해답을
DFS 장단점 장점 단지 현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고
다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을