ITeus

순열이란 영어로는 Permutation으로 n개의 물체를 순서를 고려해서 m개를 뽑는 경우의수를 의미합니다. 중고등학교 시간에 배웠던 nPm입니다. 경우의 수가 몇개인지 구하는 것은 간단합니다. n!/m!을 해주면 갯수는 구할 수가 있습니다. 하지만 컴퓨터과학에서 모든 경우의수를 탐색하는 완전탐색을 위해서는 경우의 수의 갯수가 아니라, 모든 경우의 수를 구해야 하는 일이 있습니다. 1. Python의 내장라이브러리인 itertools의 permutations 매쏘드를 사용할 수 있습니다. 2. 직접 산출하는 함수를 지정하는 방법에 대해서 살펴봅시다. 일단 우리는 nPm의 경우의수 개수를 알고 있습니다. 해당 방법을 활용해서 경우의수를 모두 구하게 됩니다. 첫번째 Pick의 가능한 경우의 수는 nPm입니다..

이번 포스팅은 최대공약수/최소공배수를 Computer를 이용해서 구하는 방법입니다. 1. 단순탐색 컴퓨터를 사용하지 않을 경우 구했던 방법을 생각해보면 1. a와 b가 있다. 2. a = a_1*a_2*a_3...., b = b_1*b_2*b_3....의 형태로 인수분해 한다. 3. 이때 인수분해 된 값들 중 교집합을 찾는다. Prime Number를 구하는 포스팅을 참고하면, N의 숫자가 있을 때 N을 인수분해 하기 위해서는 1~1/N까지의 값으로 N을 나눤서 0이되는 값을 찾아야 합니다. 하지만 이 방법은 O(N)의 시간복잡도를 갖기 때문에, 숫자가 커질수록 알고리즘의 성능이 떨어집니다. 2. 유클리드 호제법 다른 방법으로는, 두 수의 나눗셈결과를 이용하는 유클리드호제법이 있습니다. ko.wikipe..

소수(Prime Number)는 1이외에 어떠한 값으로도 나눠지지 않는(나머지가 없는) Number를 의미합니다. 이런 소수는 암호악에서 주로 사용되며, 매우 큰 Number가 소수인지 소수가 아니면 어떻 값과 곱해지는지를 사용하는 방법이 사용됩니다.(공개키 암호) 컴퓨터가 해당 Number가 소수인지, 소수가 아니면 어떤 값과 곱해지는지 확인하는 방법은 1. 1~Number까지 나눠서, 나눈 나머지를 확인한다 1_1. 만약 나머지가 0이면 1 이외에 나눠지는 값이 있으므로, 소수가 아님 2. Number의 1/2까지 진행 후 알고리즘 종료 Number의 1/2를 넘어가면, 어차피 Number를 나눠도 1보다 작아지기 때문에 의미가 없습니다. 이렇게 되면 O(1/2N) = O(N)의 시간복잡도를 갖는 P..

이번 포스팅은 컴퓨터가 어떻게 사칙연산을 처리한는지에 대한 포스팅 입니다. 사칙연산 식을 표현할때는 3가지가 있다고 할 수 있습니다. 1.전위표기 2.중위표기 3.후위표기 자 그러면 이제 이런 표기법이 왜 필요한지 의문이 드실겁니다. 우리가 Programming 언어로 Code를 짜고, 해당 Code를 기반으로 Computer가 동작합니다. 사람은 중위 표기법을 바로 이해할 수 있지만 컴퓨터가 중위표기법을 순서대로 해석할 경우 문제가 발생합니다. 사람의 경우 /와 *가 +, -보다 우선순위인걸 알기 때문에 식 전체를 보고, 우선순위부터 계산합니다. 하지만 컴퓨터가 중위표기법 그대로를 받는다면 순서대로 들어온 operand를 계산하기 때문에 실제 필요한 결과와는 다른 값이 나오는것을 확보실 수 있습니다. ..

이번포스팅은 간단한 알고리즘 입니다. 정보처리기사나, 다른 알고리즘 관련된 내용을 공부하시다보면 특수한 형태를 Display 해라(Ex. 삼각형, 나무, Tree모양....)라는 문제가 가끔 등장합니다. 이번 형태는 HourGlass(모래시계) 모양 입니다. 저도 예전 C언어 과제를 하면서, 이걸 못만들어서 엄청 고생했던 기억이 있네요 ㅎㅎ 만들어 지는 과정은. 1. HourGlass 크기만큼의 Frame을 생성한다. 2. 첫번째 Row를 가득 채우로, 그 다음 Row부터 양쪽을 1씩 좁혀나간다. 3. Row를 채워야할 값이 0보다 작거나 같아지면 다시 좌우의 양쪽을 1씩 넓히면서 Fill Python으로 간단하게 구현한 HourGlass 형태의 결과물 만들기입니다~ import random class ..

유전알고리즘은 최적화 알고리즘의 한 종류로, 적절한 정보의 Coding을 통해서 유전/진화 Modeling을 구축하고, 최적해를 구하는 알고리즘 입니다. 말 그대로 유전, 적자생존 + 돌연변이발생이라는 생명체의 진화과정을 모사한 알고리즘이라 할 수 있습니다. 이때, 각 자손은 유전자(Parameter)를 가지고 있고, 이 유전자에 따른 우월성을 따지게 됩니다. 적자생존 이기 때문에, 우월한 유전자는 상대적으로 유리하게 살아남아 유전자를 다음 세대로 전달하고 그렇지 못한 유전자는 사라지게 됩니다. 이때 유전알고리즘의 특징으로 교차와 돌연변이가 있습니다. 1. 교차 교차는 두개의 개체를 임의 or 우월성에 따라 추출하고, 두 개체의 교배(유잔자 혼합)을 하는것을 의미합니다. 개체를 선택하는 방법은 랜덤, 우..