목차 1. 위상정렬의 개념 2. 위상정렬의 구현 3. 위상정렬 코드 개념 위상정렬은 방향이 있는 그래프에서 정점들 간의 선후 관계를 위배하지 않도록 정렬하는 방법입니다. 위상정렬에 대하여 설명하기 앞서 간단한 위상정렬의 예시에 대해 알아보겠습니다. 위상 정렬은 선수과목이 있는 대학교의 커리큘럼을 생각하면 이해하기 쉽습니다. 다음과 같은 커리큘럼이 존재할 때 임베디드 시스템이라는 과목을 수강하기 위해서는 어떠한 순서로 과목을 수강해야 할까요? 여러가지 방법이 있겠지만 한 예시로 다음과 같은 수강 방법을 들 수 있습니다. UNIX 시스템 → 어셈블리 언어 → 논리회로 설계 → 운영체제 → 컴퓨터 구조론 → 마이크로프로세서 → 임베디드 시스템 하지만 선수과목이 존재하기 때문에 다음과 같은 선후관계는 반드시 지..

목차 1. 이항계수의 정의 2. 이항계수 점화식 3. 파스칼의 삼각형 4. 이항계수 구현 정의 이항계수는 이항식을 이항정리로 전개했을 때 각 항의 계수를 나타냅니다. 이항식 $(x + y)^2$ 를 전개한 결과는 다음과 과 같습니다. $(x + y)^2 = x^2 + 2xy + y^2$ 이 때 위의 전개 식에서 각 항의 계수인 [1, 2, 1] 이 나타내는 것이 바로 이항계수 입니다. 이항계수는 조합을 통해 구할 수 있습니다. 이번 포스팅에서는 조합을 통해 이항계수를 구하는 점화식과 이 점화식을 통해서 재귀적으로 그리고 동적계획법으로 이항계수를 구하는 방법에 대하여 알아보도록 하겠습니다. 점화식 이항계수를 구하는 점화식에 대해 알아보도록 하겠습니다. $(x + y)^n$ 이라는 이항식이 주어졌을 때 이항..

개념 가지치기(Pruning)는 탐색 과정에서 필요없는 과정을 줄여 최적화 시키는 것입니다. 단편적인 예를 들면, 탐색한 값들 중 최솟값을 구하는 문제에서 현재까지 탐색한 결과값보다 값이 커질 경우 더이상 탐색하지않고 종료하는 것이 가지치기입니다. 위 사진*은 특정 방법으로 노드 하나하나 탐색하고 있을때, 결과의 최솟값을 구해야하는 문제에서 모든 곳을 탐색한 경우의 수라고 가정해보겠습니다. 이 문제의 답이 빨간색 노드가 가지고있는 값이 최솟값이라고 하고 파란색 노드가 빨간색 노드의 값보다 커지는 위치라고 했을때, 위처럼 모든곳을 탐색할 필요가 있을까요? 파란색 노드 아래로는 탐색하지 않아도 적어도 최솟값이 아니란걸 알 수 있습니다. 따라서 탐색하지 않고 종료하는것이 가지치기 입니다. * 설명을 위한 사진..

목표 부분집합의 원소를 구할 수 있다. 부분집합의 개수를 구할 수 있다. 이번 부분집합에서는 위 두가지 목표에 대해 조합을 통한 구현과 bitmask를 통한 구현을 알아보겠습니다. 구현 RecursiveSubset 첫번째는 조합을 이용한 풀이인데, 조합에 대한 코드나 지식이 부족하다면 여기를 참고하세요. 부분집합은 " 멱집합(개수) = nC0 + nC1 + nC2 + ... nCr + nCr+1 ... + nCn" 와 같은 성질을 가지고 있습니다. 조합 함수에 파라미터로 r을 넘겨주면 쉽게 구할 수 있습니다. void Comb(int idx, int curr, int r) { if (idx == r) { for (int i = 0; i < r; ++i) cout

개념 서로 다른 n개의 수 중에 r개를 선택 nCr = n! / (n-r)! * r! 리스트를 순서에 상관없이 수를 뽑는 것입니다. 사실 완전탐색으로 풀리는 문제가 있지만 많은 문제들이 그렇지 않습니다. 그럴때 최적화를 하여 답을 도출해 내는것이 중요한데, 최적화하기 앞서서 기본 뼈대가되는 탐색인 조합탐색을 알아보도록 하겠습니다. 구현 재귀 호출을 이용해서 조합을 구성하기 위해서는 네가지 파라미터가 필요합니다. nCr에서 n nCr에서 r 기저 조건을 위한 idx 어느곳을 탐색할지 정하는 curr 그러나 n과 r이 고정되어 있다면 idx와 curr만 사용할수도 있습니다. 이처럼 재귀 호출은 변형에 용이합니다. 그리고 아래와 같은 배열 2가지가 필요합니다. 나열한 수를 담을 배열 나열되어져야 할 수를 담은..

개념 서로 다른 n개의 수 중에 r개를 선택하여 나열 nPr = n x n-1 x n-2 ...... x n-r+1 리스트를 순서대로 수를 뽑아 나열하는 것. 즉, 순서에 의미가 있는 것이 순열입니다. 반대로 순서에 의미가 없다면 조합이 되겠습니다. Itreative function Recursive function Itreative function은 c++의 STL인 next_permutation 방식입니다. 설명과 직접 구현을 해보도록 하겠습니다. Recursive function은 재귀 호출 방식입니다. 마찬가지로 직접 구현 해보도록 하겠습니다. Iterative function (next_permutation) ① 뒤쪽부터 탐색하며 꼭대기를 찾자 꼭대기를 왜 찾아야 할까요? 두 가지 리스트를 가지..