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..

이번에는 순서규칙을 맞춘 경우만 선택하는 스킬트리 문제입니다. programmers.co.kr/learn/courses/30/lessons/49993?language=python3 코딩테스트 연습 - 스킬트리 programmers.co.kr 바람의 나라를 예로 들어봅시다. 화염주, 화열참주, 진화열참주, 극진화열참주 가 있다고 해보겠습니다. 이름부터 화염주 화열참주 를 배우는 것은 문제가 되지 않습니다. (이때 화염주 계열 이외에는 기술의 순서가 없다고 생각합니다) 하지만 화열참주 -> 저주 -> 중독 -> 진화열참주 순으로는? 앞에 화염주는 배우기 전이기 때문에 불가능한 스킬트가 됩니다. 이러한 방법으로, 불가능한 경우의수를 정리하면 1. 상위 기술이 하위기술보다 먼저 배우는 경우 2. 상위 기술이 하..

이번 포스팅은 최대공약수/최소공배수를 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..

이번 문제는 컴퓨터 그래픽스의 선분 Plot과 유사한 문제입니다. programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 문제를 예시를 보면, 아래와 같습니다. 모눈종이 위에 직선을 긋고, 해당 직선이 지나가는 경우에는 해당 부분을 제거한 다음 남아있는 회색의 정사각형 갯수를 반환해야 합니다. 이때 컴퓨터그래픽스 내용을 포스팅하면서, 선분을 Plot하는 DDA방법이 있다고 말씀드렸었습니다. DDA방법을 ..

이번 포스팅은 프린터 대기열을 처리하기 문제입니다 programmers.co.kr/learn/courses/30/lessons/42587?language=python3 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 문제를 살펴보면 간단한 Queue 대기행렬 문제의 응용버전 입니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 우..