알고리즘 & 코딩 테스트/종만북 검색 결과

해당 글 9건

08. 동적 계획법

08. 동적 계획법 8.1 도입 동적 계획법과 분할 정복은 같은 접근 방식이라고도 볼 수 있습니다. 동적 계획법은 문제를 나누는 방식에서 차이가 납니다. 둘 다 부분 문제로 나누는 것은 같지만 동적 계획법에서의 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기에 cache 라는 곳에 부분 문제의 결과를 저장해두어 활용한다. 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다가 재활용하는 최적화 기법을 메모이제이션(memoization) 이라고 합니다. 메모이제이션은 함수의 반환 값이 그 입력 값만으로 결정되는 참조적 투명성 함수 에만 적용할 수 있다. 메모이제이션 구현 패턴 굉장히 자주 접하게 될 메모이제이션은 한 가지 패턴을 정해두고 항상 같은 형태로 구현 하면 버그를 ..
알고리즘 & 코딩 테스트/종만북 2021. 7. 18. 11:16

[종만북] 06. 무식하게 풀기

06. 무식하게 풀기 6.1 가장 큰 실수는 쉬운 문제를 어렵게 푸는 것이다. 이런 실수를 방지하기 위해 문제를 처음 마주치고 나면 스스로에게 질문해보자. 무식하게 풀 수 있을까? 이렇게 구현된 알고리즘들은 거의, 흔히 완전 탐색이라고 불린다. 재귀 호출 '더 이상 쪼개지지 않는' 최소한의 작업(기저 사례) 에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 한다. 기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용하여 계산할 수 있도록 신경써야 한다. BOGGLE 4. 5. 6. .2 1. 2. 3. 4. 5. 6. .3 1. 2. 3. 4. 5. 6.
알고리즘 & 코딩 테스트/종만북 2021. 6. 4. 22:50

[종만북] 05. 알고리즘의 정당성 증명 (미완)

05. 알고리즘의 정당성 증명 5.1 도입 5.2 수학적 귀납법과 반복문 불변식 알고리즘의 증명을 공부해야 하는 가장 큰 이유는 많은 경우 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문이다. 결정적으로 필요한 깨달음이 증명에 담겨 있는 경우가 많다. 이를 통해 나중에 자신이 설계한 알고리즘의 정당성을 더 쉽게 증명할 수 있는 직관 같은 것이 생긴다. 증명부를 소홀히 여기지 마시고 이들을 모두 공부하기 바랍니다. 수학적 귀납법 4. 5. 6. .2 1. 2. 3. 4. 5. 6. .3 1. 2. 3. 4. 5. 6.
알고리즘 & 코딩 테스트/종만북 2021. 5. 23. 15:06

[종만북] 4. 알고리즘의 시간 복잡도 분석 ② (미완)

4. 알고리즘의 시간 복잡도 분석 ② 4.5 시간 복잡도 시간 복잡도란 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것입니다. 기본적인 연산이라는 것은 사칙연산, 대입, 대소 비교 등을 뜻하며 반복문 같은 것들은 포함하지 않는다. 시간 복잡도가 낮다고 해서 항상 더 빠르게 동작하는 것은 아니다. 입력의 크기가 작고 시간 복잡도가 높은 알고리즘이 입력의 크기가 크고 시간 복잡도가 낮은 알고리즘보다 빠르게 동작할 수 있다. 입력의 종류에 따른 수행 시간의 변화 알고리즘에 따라서, 어떤 입력(배열)이 들어오느냐에 따라 수행 시간이 달라질 수 있다. 만약, 배열에서 주어진 숫자를 찾아서 그 idx 를 반환하는 함수가 있다고 생각했을 때, 최선 : 찾는 숫자가 맨 앞에..
알고리즘 & 코딩 테스트/종만북 2021. 5. 23. 14:59

[종만북] 04. 알고리즘의 시간 복잡도 분석 (1)

04. 알고리즘의 시간 복잡도 분석 (1) 4.1 도입 4.2 선형 시간 알고리즘 알고리즘의 속도를 어떻게 측정할 것인가. 결국은 반복문이 지배한다. 대개 우리는 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정한다. M 개 의 이동 평균을 구하는 알고리즘을 알아보자. (vecotr 관련 글) vector movingAverage1(const vector(double)& A, int M) { vector ret; int N = A.size(); for (int i = M - 1; i < N; i++){ double partialSum = 0; for(int j = 0; j < M; j++) partialSum += A[i-j]; ret.push_back(partialSum / M); } return ..
알고리즘 & 코딩 테스트/종만북 2021. 5. 20. 22:56

[종만북] 03. 코딩과 디버깅에 관하여 (2)

03. 코딩과 디버깅에 관하여 3.4 디버깅과 테스팅 디버깅에 관하여 디버거는 유용하지만, 프로그래밍 대회에서의 코드는 길지 않기 때문에 소스를 읽어 가며 검증하는 것이 가능하며 더 빠르다. 그러므로, 디버거 없이 프로그램의 버그를 찾아내는 연습을 해야 한다. ① 오동작하는 작은 입력을 먼저 찾아내면 디버깅하기 용이하다. ② 단정문 assertion 을 사용하여 내부 상태를 검증해본다. ③ 프로그램의 중산 계산 결과를 출력하여 검사한다. 프로그램이 런타임 오류를 내며 종료할 때 디버거가 용이할 것이다. 테스트에 관하여 스캐폴딩 이라는 유용한 테스트 기법이 있다. 임의의 작은 입력을 자동으로 생성해 프로그램을 돌려 보고, 그 답안을 검증하는 프로그램을 짜는 것이 스캐폴딩이다. 내 코드와 비교할 대상이 없다..
알고리즘 & 코딩 테스트/종만북 2021. 5. 15. 23:11