알고리즘/수업 복습11 Backtracking Algorithm Design Method (백트래킹 알고리즘) 이번에는 백트래킹 알고리즘에 대해 알아보자. 이 글에서 알아볼 것은 다음과 같다. 백트래킹 기술 설명 백트래킹 기법이 문제 해결에 적절한 접근 방식인지 판단 주어진 문제에 대한 상태 공간 트리 정의 주어진 문제에 대한 상태 공간 트리의 노드가 유망(promising)하거나 비유망(non-promising)한 경우 정의 상태 공간 트리를 제거하는 알고리즘 생성 주어진 문제를 해결하기 위해 백트래킹 기법을 적용하는 알고리즘 생성 여기서 상태 공간 트리(state-space-tree)란 문제 해결의 중간 상태를 각각 한 노드로 나타낸 트리이다. ※ P, NP Problem 백트래킹을 살펴보기 전에 P, NP에 대해 간단히 짚고 넘어가자. 이제 막 알고리즘에 대해 배우고 있는 입장에서 명확히 이해하기 어려운 개.. 2021. 11. 22. Greedy Algorithm Design Pattern 2(탐욕 알고리즘) 이전 게시글에 이어서 Greedy Algorithm(탐욕 알고리즘, GA)의 또 하나의 예시인 허프만 이진 코드 트리(Huffman Binary Code Tree)에 대해 알아보자. 그리고 헷갈릴 수 있는 Dynamic programming(DP)과 GA의 차이점에 대해서도 살펴보자. Huffman Binary Code Tree 해당 알고리즘은 데이터 파일(텍스트, 오디오, 이미지 등)을 효율적으로 인코딩할 때 사용된다. 즉 최대한 압축률을 크게 하는 것이 목적이다. 우선 파일을 어떤 방식으로 나타내는지 부터 알아야겠다. 파일을 나타내는 일반적인 방법은 이진 코드(bit)를 사용하는 것이며 문자는 고유한 코드 워드(이진 문자열)로 표시된다. Type of Binary Code 여기서 이진 코드의 유형을 .. 2021. 11. 8. Greedy Algorithm Design Pattern 1(탐욕 알고리즘) 이번에 알아볼 디자인 패터은 탐욕 알고리즘(GA, Greedy Algorithm)이다. 해당 디자인 패턴은 저번에 알아본 동적 계획법과 마찬가지로 최적화문제(max/min)를 해결하는데 쓰인다. 즉 문제가 최적 부분 구조를 가지고 있어야 한다고 했었다. 이에 대해 다시 짚고 넘어가자면 origin program의 최적해(solution)가 부분 문제의 최적해들로써 구성되어야, 그 문제가 최적 부분 구조를 가졌다고 할 수 있는 것이다. 이전 글의 예시들을 다시 본다면 이해할 수 있을 것이다. 계속하자면, GA의 설계 전략은 최적해를 얻을 때까지 일련의 절차를 따르는데, 이때 현재 단계의 action에 따른 일련의 과거/미래 단계의 action의 잠재적 단점은 고려하지 않는다(\(A_{1} \rightarr.. 2021. 10. 19. Dynamic Programming Design Pattern (동적 계획법) 분할 정복(DC로 줄이겠음)에 이어서 이번에는 Dynamic Programming(동적 계획법, DP로 줄이겠음)이라는 디자인 패턴에 대해 알아보자. Introduction to Dynamic Programming 제목에 DP에 대한 해석을 '프로그래밍'이 아닌 '계획'으로 했다. 즉 DP의 Programming은 컴퓨터 프로그래밍이 아닌 계획을 의미한다. 원래 DP는 다단계의 의사결정을 최적화하기 위한 방법이었는데, 현재는 최적화 기법의 특정 유형으로 제한되는 일반적인 알고리즘 설계 기법이다. 말이 좀 어려운것 같다. 다르게 설명하자면 DP는 중복되거나 종속적인 하위 문제로 문제를 해결하기 위한 기술이다. 일반적으로, recurrence relation에서 하위 문제가 발생한다. 이 방법은 중복되는 하.. 2021. 10. 13. 이전 1 2 3 다음
