앞에서 보았던 피보나치 수를 재귀 함수로 구하는 프로그램은 "엄청난 중복 호출" 이라는 큰 문제가 존재한다. 이를 해결하기 위해 동적 계획법의 핵심 기술인 memoization에 대해 먼저 알아보자 # memoization 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술 글자 그대로 해석하면 '메모리에 넣기 (to put in memorty)'라는 의미 앞서 구했던 fibo(n)의 값을 계산하자 마자 저장하면 O(2^n) 시간을 O(n)으로 줄일 수 있다. 이제 memoization을 활용한 Dynamic Programming에 대해서 알아보자 # DP(Dynamic Programming) 동적 계획 알고리즘은 그리..

예전 글에서 완전검색(Exaustive Search) 즉, 브루트 포스에 대해서 알아보았다. 경우의 수를 이용하여 문제를 푸는 것이 아닌 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업이다. 검색(Search) 탐색 키(search key) : 자료를 구별하여 인식할 수 있는 키 종류 순차 검색(sequential search) 이진 검색(binary search) 해쉬(hash) 순차 검색 (Sequential Search) 일렬로 되어 있는 자료를 순서대로 검색하는 방법 가장 간단하고 직관적인 검색 방법 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행시간이 급격히 증가하여 비효율 1. 정..

완전검색 기법으로 모든 부분집합 합 문제를 풀기 위해서는, 우선 집합의 모든 부분집합을 생성한 후에 각 부분집합의 합을 계산해야 한다. 어떻게 계산할 수 있을까? 부분 집합의 생성 부분 집합의 수를 우선 구해보자 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개이다. 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다. 예) {1, 2, 3, 4} -> 2 * 2 * 2 * 2 = 16가지 1. 각 원소가 부분집합에 포함되었는지를 loop를 이용하여 확인하고 부분집합을 생성해보자 bit = [0, 0, 0, 0] for i in range(2): bit[0] = i# 0번째 원소 for j in range(2): bit[1] = j..

저번 글에서는 검색과 순열에 대해서 알아보았다. 이번 시간엔 'Greedy'라고 불리는 최적해를 구하는 방법을 알아보자. 탐욕 최적해를 구하는데 사용되는 근시안적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다. 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다. 동작 과정 해 선택 = 선택 절차(Selection Procedure) 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해집합(Solution Set)에..

앞에서는 배열을 선언하고 그 배열을 정렬하는 방법에 대해서 배웠다. 이번 글에서는 경우의 수를 이용하여 문제 해결을 하는 검색이라는 것에 대해서 배워보자. 완전 검색(Exaustive Search) 완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 Brute-force 혹은 generate-and-test 기법이라고도 불림 모든 경우의 수를 테스트한 후, 최종 해법을 도출 일반적으로 경우의 수가 상대적으로 작을 때 유용 특징 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다. 평가 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확..

알고리즘이라는 말은 많이 들어봤을 것이다. 나도 단순한 흐름이라고만 알고 있었지 이게 왜 필요한 것인지 알아보자! 알고리즘 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법 즉, 어떠한 문제를 해결하기 위한 절차 컴퓨터 분야에서 알고리즘을 표현하는 방법을 크게 두 가지이다. 의사 코드(슈도 코드, Pseudocode) 순서도 APS(Algorithm Problem Solving) 과정의 목표 중의 하나는 보다 좋은 알고리즘을 이해하고 활용하는 것!! 그렇다면 좋은 알고리즘이란 무엇일까? 정확성 : 얼마나 정확하게 동작하는가 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가 메모리 사용량 : 얼마나 적은 메모리를 사용하는..