본문 바로가기

이론87

분할 정복 알고리즘 (Divide and Conquer) 분할 정복 알고리즘 분할정복(Divide and Conquer)은 문제를 작은 부분으로 나누어 해결하는 알고리즘 설계 전략입니다. 이 방법은 주어진 문제를 세 단계로 나누어 처리합니다: 분할(Divide): 주어진 문제를 더 작고 해결하기 쉬운 작은 부분 문제들로 분할합니다. 이때, 문제는 일반적으로 동일한 크기의 작은 부분 문제들로 분할됩니다. 정복(Conquer): 분할된 작은 부분 문제들을 각각 해결합니다. 보통 재귀적으로 작은 부분 문제를 해결하는 방식을 사용합니다. 결합(Combine): 작은 부분 문제들의 해를 결합하여 원래 문제의 해를 얻습니다. 이 과정에서 분할된 문제들의 해를 결합하여 최종 해를 얻습니다. 분할정복은 문제를 더 작고 해결하기 쉬운 작은 부분 문제들로 분할함으로써 전체적인 .. 2024. 3. 22.
정렬 알고리즘 - 삽입 정렬 (Insertion sort) 삽입 정렬 (Insertion sort) 이란? 삽입정렬은 리스트를 정렬하는 과정에서 이미 정렬된 부분 리스트와 비교하여 각 요소를 그 위치에 삽입하는 알고리즘입니다. 이 과정에서 삽입정렬은 각 요소를 정렬된 부분 리스트에 "적절한 위치에 삽입"하는 방식으로 동작하며, 이러한 특성에서 알고리즘의 이름이 지어졌습니다. 삽입 정렬은 아래와 같은 과정을 따릅니다. 리스트의 두 번째 요소부터 시작하여 이미 정렬된 부분 리스트와 비교합니다. 적절한 위치를 찾을 때까지 이전 요소와 비교하며 이동합니다. 비교하고자 하는 요소보다 작거나 같은 값을 가진 요소를 찾으면, 해당 요소 바로 뒤에 삽입합니다. 이러한 과정을 반복하여 전체 리스트가 정렬될 때까지 진행합니다. 삽입 정렬 코드 예시 (C#) 아래 코드는 C#으로 .. 2024. 3. 22.
정렬 알고리즘 - 버블 정렬 (Bubble sort) 버블 정렬 (Bubble sort) 이란? 버블 정렬은 간단하고 직관적인 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 필요에 따라 위치를 교환하여 정렬하는 방식입니다. 이 알고리즘은 이름 그대로, 가장 큰(또는 작은) 원소가 "거품"처럼 계속해서 위로 올라가는 모습을 닮았기 때문에 '버블' 정렬이라고 불립니다. 버블 정렬은 아래와 같은 과정을 거칩니다: 리스트의 첫 번째 원소부터 시작하여 인접한 두 원소를 비교합니다. 인접한 원소가 순서에 맞지 않으면 위치를 교환합니다. 리스트의 끝까지 도달할 때까지 위 과정을 반복합니다. 위 과정을 한 번 수행할 때마다 가장 큰(또는 작은) 원소가 마지막으로 이동하므로, 정렬된 부분을 제외하고 다시 처음부터 반복합니다. 버블 정렬 코드 예시 (C#) 아래 코드.. 2024. 3. 22.
정렬 알고리즘 - 선택 정렬 (Selection sort) 선택 정렬(Selection Sort) 이란? 선택 정렬은 간단하지만 효율적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 주어진 리스트에서 가장 작은(또는 큰) 원소를 선택하여 리스트의 처음부터 차례대로 정렬되는 위치로 옮기는 과정을 반복합니다. 이 과정에서 선택 정렬은 정렬된 부분과 정렬되지 않은 부분을 유지하며 동작합니다. 선택 정렬은 다음과 같은 과정을 따릅니다: 주어진 리스트에서 가장 작은(또는 큰) 원소를 찾습니다. 해당 원소를 리스트의 맨 앞으로 이동시킵니다. 정렬된 부분과 정렬되지 않은 부분을 나누어 위 과정을 반복합니다. 리스트의 모든 원소가 정렬될 때까지 위 과정을 반복합니다. 선택 정렬 코드 예시 (C#) 아래 코드는 C#으로 작성된 선택 정렬 알고리즘의 예시입니다. 입력 배열이 {6.. 2024. 3. 22.

티스토리툴바