자료구조16 백트래킹 백트래킹: 여러 후보해 중 특정 조건을 충족시키는 모든 해를 찾는 알고리즘.후보해란 해가 될 수 있는 가능성을 가진 부분해의 조합.다루는 문제들은 대부분 후보해의 수가 굉장히 많다는 특징이 있고이중 해가 될 조건을 만족시키는 전체 해를 효율적으로 찾는 것이 목적이다.부분 해: 현재까지 탐색한 해의 일부 조합.전체해: 조건을 만족하는 완전한 해답. 동작순서1. 현재 상태에서 가능한 선택을 시도.2. 조건 만족 여부 검사 조건 만족 → 계속 진행.조건 불만족 → 이전 상태로 되돌아감 (Backtrack!).3. 모든 선택지를 재귀적으로 반복. 이 과정은 깊이 우선 탐색과 비슷하지만 깊이 우선 탐색은 모든 노드를 방문하는 것이 목적이고백트래킹은 해를 찾는 것이 목적이기에 꼭 모든 노드를 방문할 필요가 없.. 2025. 4. 25. 탐욕 알고리즘 { 호프만 트리 } 탐욕(Greedy) 알고리즘: 각 단계의 부분 문제를 풀 때 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여적합한 결과를 도출한다고 해서 붙여진 이름.동적 계획법 보다 효율적이기는 하지만 반드시 최적해를 구해준다는 보장은 하지 못한다.대상 문제가 최적 부분 구조를 가지고 있어야 한다.동작 순서1) 해 선택: 현재 상태에서 부분 문제의 최적해를 구한 뒤 이를 부분해 집합에 추가함.2) 실행 가능성 검사: 새로운 부분해 집합이 실행 가능한 것인지 확인. 문제의 제약 조건을 위반하지 않았는지 검사하는 것.3) 해 검사: 새로운 부분해 집합이 문제의 해가 되는지 확인. 전체 문제의 해가 완성되지 않았다면 1단계부터 다시 시작. 고정 길이 코드: 모든 코드의 길이가 똑같은 값을 갖는 코드 체계를 말한다. 자.. 2025. 4. 25. 동적 계획법 { LCS 알고리즘} 동적계획법: 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어졌을 때, 각 단계에 있는 부분 문제의 답을 기반으로전체 문제의 답을 구하는 방법이다.제일 작은 문제부터 상위에 있는 문제를 풀어서 올라가는 방식이고 한 번 푼 적이 있는 부분의 문제는 테이블 등에 저장하여 다시푸는 일이 없도록 방지한다. 순서1) 문제를 부분 문제로 나눈다.2) 가장 작은 부분 문제의 해를 구한 뒤 테이블에 저장한다.3) 테이블에 저장된 부분 문제의 해를 이용해 점차적으로 상위 부분 문제의 최적해를 구한다.동적 계획법을 이용하려면 그 문제가 최적 부분 구조를 갖추어야 하는데최적 부분구조란 전체 문제의 최적해가 부분 문제의 최적해로부터 만들어지는 구조이다. 수열이란 물건이나 객체의 목록을 의미하는데 수열에서 일부 요소를 제.. 2025. 4. 24. 분할 정복 알고리즘 {병합 정렬, 거듭 제곱 계산, 피보나치 수 구하기 } 분할정복 알고리즘: 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나뉜 문제들을 각각 풀어서 결국 전체 문제의 답을 얻는 기법이고 핵심은 문제를 잘게 나누는 것이다.대략적인 순서1) 분할: 문제가 분할 가능한 경우 2개 이상의 하위 문제로 나눈다.2) 정복: 하위 문제가 여전히 분할 가능한 상태라면 하위 집합에 1을 수행하고 그렇지 않다면 하위 문제를 푼다.3) 결합: 2번을 통해 구한 답을 취합한다.분할 정복 알고리즘을 구현할 때 재귀 호출을 많이 사용하는데 이 때문에 문제를 잘게 나누어 얻은 알고리즘의 효율성이재귀 호출 비용 때문에 깎이기도 한다. 병합정렬: 데이터를 나눈 후 정렬하면서 합치는 알고리즘.순서1) 정렬한 데이터를 반으로 나눈다2) 나뉜 하위 데이터의 크기가 2 이상이면 이 하.. 2025. 4. 24. 알고리즘 성능 분석 알고리즘 성능 측정 기준 1. 정확성 - 알고리즘이 입력 값에 대해 정해진 절차를 수행하여 결과적으로 정확한 출력을 제공하는가를 가리키는 기준.2. 작업량 - 요구되는 기능을 수행하기 위해 알고리즘이 수행해야 하는 작업의 양이 얼마나 되는가를 가리키는 기준.3. 메모리 사용량 - 해당 알고리즘이 작업을 수행할 때 사용해야 하는 메모리의 양을 의미.4. 단순성 - 복잡하면 개선과 분석이 어렵기 때문에 중요한 요소.5. 최적성 - 더 이상 개선할 부분이 없을 정도로 최적화되어 있는가를 가리키는 기준. 알고리즘 수행 시간: 알고리즘이 입력을 받아 실행되었을때, 해당 입력을 처리하는 데 걸리는 시간. 실제 시간을 측정하는 것은제약이 많기에 입력 크기에 따라 시간이 얼마나 증가하는가를 보는 시간복잡도를 사용하고 .. 2025. 4. 24. 문자열 탐색 알고리즘 {라빈-카프, KMP, 보이어 - 무어} 고지식한 탐색: 본문의 앞에서부터 끝까지 차근차근 탐색하는 알고리즘.본문의 길이를 N, 패턴의 길이를 M이라고 했을 때 최악의 경우 N x M 번 비교를 수행한다.TextSize - PatternSize 위치까지 차례대로 순회. 다시 PatternSize만큼 Pattern 내 문자를 Text 내 문자와 비교.일치하는 부분을 찾으면 그 위치를 반환하고 종료, 본문에 패턴과 일치하는 부분이 없으면 -1을 반환. 라빈-카프 알고리즘: 문자열 탐색을 위해 해시 함수를 사용, 패턴의 해시값과 본문 내의 하위 문자열의 해시 값을 비교하는 방식.매번 해시 값을 계산한다면 비용이 많이 들겠지만 한 번 해시 값을 구한 뒤엔 기존 해시 값에 앞 문자 제거 + 새 문자 추가 방식으로 빠르게 해시 값을 구할 수 있고 패.. 2025. 4. 23. 이전 1 2 3 다음
