ITeus

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

이번 문제는 주어진 모든 경우의수를 찾고, 여기서 소수를 찾는 문제입니다. programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제를 보면 1~7개 사이의숫자가 주어지고 해당 숫자를 가지고 만들어지는 모든 경우의수 중 소수를 찾게됩니다. 그렇다면 간단하게 두 파트로 나누면 됩니다. 1. 주어진 1~7개 사이의 숫자로 가능한 모든 경우의 수를 만든다. 2. 경우의수 중 소수인 값을 찾는다. 1번의 경우, permu..

배열의 Data를 정렬시켰을 때 n번째 위치의 값을 찾는 알고리즘 입니다. 해당 알고리즘은 Quick_Sort알고리즘에서 활용했던 Partition을 재활용합니다 :) teus-kiwiee.tistory.com/8 Quick Sort 퀵 정렬은 파이썬의 유명한 Package인 Pandas에서 보셨을 수 도 있습니다. (Pandas DataFrame을 정렬하는 방법중 하나로 쓰입니다) pandas.pydata.org/pandas-docs/version/0.15.2/generated/pandas.DataFrame.sor.. teus-kiwiee.tistory.com 탐색 방법 살펴보면.. 1. partition을 진행 2. partition 후 바꿀 위치와 내가 찾는 n번째 위치가 동일한지 비교한다. == ..

이진탐색 알고리즘은 분할정복 방법론을 활용한 탐색알고리즘입니다. 이진탐색 알고리즘의 순서를 살펴보면 1. Data를 오름차순으로 정렬한다. 2. Data의 중간위치의 값과 내가 찾을 값을 비교한다 if 내가 찾을 값 = 중간위치값 -> 탐색끝 else if 내가 찾을 값 1~중간값 이전까지의 데이터에서 다시 이진탐색 else if 내가 찾을 값 > 중간위치값 -> 중간값+1~마지막까지의 데이터에서 다시 이진탐색 보면 알수있지만, 한번 탐색을 하고, 그 이후에 데이터를 분할하여 다시한번 알고리즘을 적용한다. 때문이 이러한 알고리즘은 분할정복 알고리즘이라고 부릅니다. 이진탐색 알고리즘의 성능은 T(n) = T(n/2) + O(1), T(1) = 1 을 보입니다. 이걸 점화식을 풀어주면 T..