Algorithm (8)

Writings on Algorithm.

조합(Combination)

Introduction 이번에는 조합(Combination)을 구하는 방법에 대해서 알아보자. 우선 조합의 개수를 구하는 수식을 보자. * nCr = nPr/r! 이 수식이 의미하는 바는 무엇인가? 5개의 당구공이 있는데 3개를 골라내야 한다면 다음과 같이 골라낼 수 있을 것이다. * 남은 5개의 당구공에서 한 개를 골라내는 5가지 선택지가 있다. * 남은 4개의 당구공에서 한 개를 골라내는 4가지 선택지가 있다. * 남은 3개의 당구공에서 한 개를 골라내는 3가지 선택지가 있다. 여기까지는 순열의 개수이다. 하지만 골라낸 개수에 따라서 중복되는 개수가 생긴다. 당구공 3개를 골랐을 때 중복되는 개수는 다음과 같은 과정으로 구할 수 있다. * 남은 3개의 당구공 중에 하나를 고르는 경우의 수는 3가지이다. * 남은 2개의 당구공 중에 하나를 고르는 경우의 수는 2가지이다. * 남은 1개의 당구공 중에 하나를 고르는 경우의 수는 1가지이다. 순열(nPr)에서

  • Algorithm

순열(Permutation)

Introduction 순열(Permutation)을 구하는 방법에 대해서 알아보자. 우선 순열의 개수를 구하는 수식을 보자. * nPr = n!/(n-r)! 이 수식이 의미하는 바는 무엇인가? 5개의 당구공이 있는데 3개를 골라내야 한다면 다음과 같이 골라낼 수 있을 것이다. * 남은 5개의 당구공에서 한 개를 골라내는 5가지 선택지가 있다. * 남은 4개의 당구공에서 한 개를 골라내는 4가지 선택지가 있다. * 남은 3개의 당구공에서 한 개를 골라내는 3가지 선택지가 있다. 순서에 의미가 있기 때문에 중복되는 당구공을 골라내더라도 다른 순열로 봐야 한다. 따라서 중복되는 당구공을 골라내는 경우는 신경 쓸 필요가 없다. Algorithm 순열을 구현하는 가장 쉬운 방법은 재귀적으로 접근하는 것이다. 다음처럼 접근해보자. * 기존에 선택한 당구공들로 만든 순열에 나머지에 대한 순열을 구해서 더한다. * 당구공들이 더 이상 남아있지 않으면 모든 당구공에 대한 순

  • Algorithm

하노이의 탑(Tower of Hanoi)

Introduction 하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다. 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있어서는 안 된다. Algorithm 피보나치와 더불어 재귀적으로 문제를 해결하면 좋은 대표 문제이다. 큰 흐름은 다음과 같다. * 맨 마지막 원판 위의 나머지 원판들을 임시 기둥으로 옮긴다. * 맨 마지막 원판을 목적한 기둥으로 옮긴다. * 임시 기둥에 있는 원판들을 목적한 기둥으로 옮겨준다. 이 과정에서 나머지 원판들에 대해서도 위의 과정을 똑같이 거친다. 이것을 재귀적으로 호출하면 마지막에는 원판이 한 개인 경우부

  • Algorithm
2021 © Cinntiq's Studio