그리디 알고리즘이란? Greedy algorithm은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 한마디로 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들이다. 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스러운 선택 조건(greedy choice property)과 최적 부분 구조 조건(opti..

Algorithmic Problem Solving Strategies  개인적으로 읽고 정리한 요약입니다. 아래 링크에 문제 풀이 예제가 있습니다. GitHub - chanheki/AlgorithmicProblemSolvingStrategies: Algorithm Book Study Algorithm Book Study. Contribute to chanheki/AlgorithmicProblemSolvingStrategies development by creating an account on GitHub. github.com 동적 계획법 도입 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나. 최적화 문제를 연구하는 수학 이론에서 파생, 우리가 전산학 전반에서 일반적으로..

Algorithmic Problem Solving Strategies  개인적으로 읽고 정리한 요약 입니다. 아래 링크에 문제 풀이 예제가 있습니다. GitHub - chanheki/AlgorithmicProblemSolvingStrategies: Algorithm Book Study Algorithm Book Study. Contribute to chanheki/AlgorithmicProblemSolvingStrategies development by creating an account on GitHub. github.com 분할 정복 도입 분할 정복(Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 간단하게 설명된다. 분할 정복 패러다임을 차용한 알고리..

Algorithmic Problem Solving Strategies  개인적으로 읽고 정리한 요약 입니다. 아래 링크에 문제 풀이 예제가 있습니다. GitHub - chanheki/AlgorithmicProblemSolvingStrategies: Algorithm Book Study Algorithm Book Study. Contribute to chanheki/AlgorithmicProblemSolvingStrategies development by creating an account on GitHub. github.com 무식하게 풀기 도입 문제를 처음 볼때 가장 먼저 스스로에게 물어볼 것. 무식하게 풀 수 있을까 ? 무식하게 푼다 == Brute Force 컴퓨터의 빠른 계산 능력을 가능한 경우..

BackTracking / 백트래킹 / 퇴각검색 여러 후보 해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘. 해를 찾는 도중 막히면 돌아가 다시 해를 찾아간다. 1. 해를 찾아가는 과정은 '루트'에서 부터 시작. (루트 또한 하나의 부분해) 2. 현재 위치한 부분해에서 선택이 가능한 다음 부분해의 목록을 얻음. 3. 2 에서 얻은 목록의 부분해들을 하나씩 방문. 4. 방문한 부분해가 요구하는 조건을 만족시키면 그 자리에서 2, 3 과정을 수행하고, 그렇지 않으면 그 이전 부분해로 돌아 나와 다른 부분해를 시도. 5. 최종해를 얻을 때까지, 또는 모든 경우의 수를 확인해도 해가 없음을 확인했을 때 까지 2,3,4 과정을 차례대로 반복.