Computer Science/자료구조20 [자료구조] Chapter 15 백트래킹 백트래킹의 개요백트래킹은 문제의 해가 될 수 있는 후보를 찾고, 해가 될 수 있는 조건을 충족하지 못하는 후보를 제거해 나가며 최종 해를 찾는 방법이다. 1) 백트래킹의 개념백트래킹은 여러 후보해 중 특정 조건을 충족시키는 모든 해를 찾는 알고리즘이다. 미로의 한 지점에서 탈출구로 향하는 경로 속에는 여러 길목이 있는데 이들 각 길목에서 왼쪽으로 갈지 오른쪽으로 갈지 물음(부분문제)에 답(부분해)을 구하는 과정을 반복하며 완성하는 것이 탈출로(해)이다. 이렇게 해가 될 수 있는 가능성을 가진 부분해의 조합을 후보 해라고 한다. 탐색 규칙은 아래와 같다.갈림길이 나오면 무조건 왼쪽 길부터 들어간다.막다른 곳이 나오면 갈라진 길목으로 나와 그다음 길을 시도한다.목표 지점에 도달하거나 모든 경로를 탐색할 때까.. 2024. 1. 22. [자료구조] Chapter 14 탐욕 알고리즘 탐욕 알고리즘의 개요탐욕 알고리즘은 최적화된 문제의 답을 얻기 위해 사용된다. 아래와 같은 과정으로 동작한다.해 선택: 현재 상태에서 부분 문제의 최적해를 구한 후 이를 부분 집합에 추가한다.실행 가능성 검사: 새로운 부분해 집합이 실행 가능한 것인지 확인한다. 다시 말해, 문제의 제약 조건을 위반하지 않는지를 검사하는 것이다.해 검사: 새로운 부분해 집합이 문제의 해가 되는지 확인한다. 아직 전체 문제의 해가 완성되지 않는다면 1의 해 선택부터 다시 한다. 거스름돈 줄이기 문제“어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?”해 선택: 가장 좋은 해를 선택하면 된다. 단위가 큰 동전으로만 거스름돈을 만들면 동전의 개수를 줄일 수 있다. 현재 고를 수 있는 가장 .. 2024. 1. 18. [자료구조] Chapter 13 동적 계획법 동적 계획법의 개요1) 동적 계획법의 개념동적 계획법이란 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어졌을 때, 각 단계에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법이다. 분할 정복은 문제를 위에서 아래로 쪼개지만, 동적 계획은 제일 작은 부분 문제부터 상위에 있는 문제로 풀어올라간다. 동적 계획법은 분할 정복과 달리 한 번 푼 적 있는 부분 문제의 답을 다시 푸는 일이 없도록 테이블에 저장한다. 동적계획법은 아래와 같은 단계로 이루어진다. 문제를 부분 문제로 나눈다.가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장한다.테이블에 저장된 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다. 이러한 동적계획법을 이용하여 문제를 풀기 위해서는 문제가 최적 부분.. 2024. 1. 15. [자료구조] Chapter 12 분할 정복 분할 정복 기법의 개요1) 분할 정복 알고리즘의 배경분할 정복 알고리즘의 핵심은 문제를 잘게 나누는 것이다. 분할: 문제가 분할 가능한 경우 2개 이상의 하위 문제로 나누는 것. 정복: 하위 문제가 여전히 분할 가능한 상태라면 하위 집합에 대해 분할 단계를 수행하고, 아닌 경우 하위 문제를 푼다. 결합: 정복의 단계를 통해 답을 구하는 것. 병합 정렬1) 병합 정렬의 동작 방식병합 정렬은 나누고 합치는 것으로 정리할 수 있다. 아래의 과정을 보자면,정렬할 데이터를 반으로 나눈다.나뉜 하위 데이터의 크기가 2 이상이면 하위 데이터에 대해 단계 1을 반복한다.동일 데이터에서 나뉜 하위 데이터 둘을 병합하여 원래대로 하나의 데이터로 만든다. 단 병합할 때의 데이터 원소는 기준에 따라 정렬한다.데이터가 원래대로.. 2024. 1. 8. [자료구조] Chapter 11 알고리즘 성능 분석 알고리즘 성능 측정 기준과 수행 시간1) 알고리즘 성능 측정 기준정확성: 정확하게 동작하는가? 작업량: 얼마나 적은 연산을 수행하는가? 메모리 사용량: 얼마나 적은 메모리를 사용하는가? 단순성: 얼마나 단순한가? 최적성: 더 이상 개선할 여지가 없을 만큼 최적화되어 있는가?정확성알고리즘이 입력값에 대해 정해진 절차를 수행하여 결과적으로 정확한 출력을 제공하는가를 가리키는 기준이다.작업량작업량은 요구되는 기능을 수행하기 위해 알고리즘이 수행해야 하는 작업의 양이 얼마나 되는가를 가리키는 기준이다. 버블 정렬을 예로 들면, 정렬을 수행하기 위해 비교연산을 몇 번 수행해야 하는가가 해당한다.메모리 사용량해당 알고리즘이 작업을 수행할 때 사용해야 하는 메모리의 양을 의미한다.최적성알고리즘에 더 이상 개선할 부분.. 2024. 1. 4. 이전 1 2 3 4 다음 반응형
