본 게시물은 경희대학교 한치근 교수님의 '알고리즘분석' 강의를 듣고 노트한 내용입니다. 원래는 multistage decision processes라고 불렸으나 정부기관의 관료에게 그럴듯하게 보이기 위해 dynamic으로 명명함 분할정복식은 하향식 해결법 (top-down approach), 서로 상관관계가 없는 문제를 해결하는 데에 적합 그러나, 피보나치 알고리즘은 같은 항이 여러번 호출됨 -> 비효율적 동적계획법 상향식 해결법 (bottom-up approach) 문제를 나눈 후에 작은 문제들을 먼저 푼다. 이항계수 구하기 계산량이 많은 n!과 k!를 계산하지않고 이를 부분으로 나눈다. 1) 분할정복식 *재귀호출을 할 때 같은 계산을 반복해서 수행하게됨. -> 비효율성 증대 2) 동적계획식 2차원 배..
본 게시물은 경희대학교 한치근 교수님의 '알고리즘분석' 강의를 듣고 노트한 내용입니다. 분할정복식 설계 전략 분할(Divide) 문제를 여러개의 작은 부분으로 나눈다. 정복(Conquer) 나눈 문제를 해결한다. 통합(Combine) 해결된 해답을 모은다. -> 하향식(Top-Down) 문제 해결 방법 이분 검색 (binary search) 크기가 n인 정렬된 배열 S에 x가 있는지 결정하는 문제 분할 - 배열을 반으로 나누어 중앙에 위치한 항목보다 크고 작음을 판단해 해당 배열 반쪽을 선택한다. 정복 - 선택된 반쪽 배열에서 x를 찾는다. 통합 - 필요없음 1. 입력파라미터인 n, S, x는 변하지 않는 값이므로 전역 변수 (global)로 선언해 메모리를 절약하라! 재귀호출에서는 인덱스만 넘겨준다! ..
코잘알 학교 선배님이 알려주신 알고리즘&코딩테스트 공부 순서입니다. 까먹지 않게 정리 해두려고요 ㅎㅎ 우선적으로 공부해야할 것 1. 정렬 2. 그리디 3. 백트래킹 4. 다이나믹 프로그래밍 (DP) 이 세가지를 기본적으로 공부해놓을 것. 이후 공부할 알고리즘이나 어려운 코딩 문제들은 2, 3, 4를 베이스로 응용하는 경 우가 많음! (단, 정렬 알고리즘과 자료구조는 기본 중에 기본) 문제를 연습할 곳 1. 백준 - 단계별 문제풀이 2. 코드업 3. 올림피아드 기출문제 (지역 본선은 3번까지, 전국본선은 2번까지가 할만함) 알면 좋은 알고리즘 1. 분할 정복 (이분 탐색) 2. 최단경로 (다잌스트라, 플로이드, 벨만포드) 3. 최소비용트리 (크루스칼, 프림, 유니온파인드) 이 정도로 공부하고 문제 풀이하면..
백준 사이트를 통해 알고리즘 공부를 하던 중, 백트래킹에 대한 개념이 명확하지 않아 정리해봅니다. 이론은 SW expert academy에서, 실습은 백준에서 참고했습니다. N-Queen 문제 N x N 체스판에서 N개의 퀸이 서로를 공격하지 못하게 배치하는 문제 백트래킹 기법이란? 해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 초기 상태에서 목표 상태로 가는 경로를 탐색하는 기법 최적화 문제와 결정 문제를 해결할 수 있음 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 yes or no로 답하는 문제 예) 미로찾기 미로에서 빠져나갈 경로가 존재하는가? -> 결정 문제 미로에서 최단거리로 나갈 수 있는 경로는 무엇인가? -> 최적화 문제 올바른 선택을 계속하면 ..