카테고리: 알고리즘

페이지당5 10 20

Dynamic Programming (동적 계획법)

흔히 DP라 불리는 동적 계획법이란, 복잡한 문제를 여러 개의 작은 부분 문제(sub-problem)로 나누어 해결하는 문제 해결 기법입니다. 동적 계획법의 특징 중 하나는 이미 계산된 부분 문제가 다시 발생하면 새롭게 계산하지…

위상 정렬이란 유향 그래프에서 정해진 순서를 위배하지 않도록 나열하는 것입니다. 예를 들면 전략 게임에서의 빌드 오더나 선수강과목을 예로 들 수 있습니다. 전략 게임의 빌드 오더에서 A를 짓지 않으면 B를 지을 수 없고, B를 짓지…

퀵 정렬(Quick Sort)은 배열에 있는 수 중 사용자가 지정한 규칙대로 임의의 pivot을 잡고, 해당 pivot을 기준으로 작거나 같은 수를 왼쪽 파티션, 큰 수를 오른쪽 파티션으로 보내고 다시 왼쪽 파티션 구간에 한하여…

분할정복(Divide and Conquer)은 말 그대로 문제를 분할한 다음, 분할한 문제들 (sub-problems)을 해결하고, 그 결과를 합쳐서 원래의 문제를 해결하는 것입니다. 분할정복의 대표적인 예로는 합병 정렬, 고속…

너비 우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점들을 발견하면 그 간선을 통해 방문하지 않은 정점들을 자료구조 큐에 넣습니다.…