![]()
시간 복잡도란?알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다.시간 복잡도는 낮으면 낮을수록 좋다. 예시만약 1차원 배열에 값이 들어가 있고, 특정 값을 배열의 맨 앞에서 순서대로 검색한다면 연산 횟수가 가장 적을 때와 가장 많을 때는? 연산 횟수가 가장 적은 경우다음 그림과 같이 찾는 값이 검색 시작 위치에 바로 있는 경우이다. 연산 횟수가 가장 많은 경우찾으려는 값이 아에 없거나 가장 마지막에 위치한 경우이다.이러한 경우 시간 복잡도는 연산 횟수가 가장 적은 경우 시간 복잡도가 낮다라고 표현할 수 있다. 빅오 표기법점근적 표기법인 상한선을 활용하여 시간 복잡도를 표기하는 방법이다.어떤 프로그램 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 계수를 지워 ..
요세푸스 순열이란요세푸스 문제에서 나온 순열이다.두 자연수 n과 k가 주어졌을 때 (n > k).n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다.남은 n - 1명에서 다시 다음부터 순서를 세서 k번째 사람을 모임에서 제외한다.이것을 아무도 남지 않을 때까지 계속해서 반복한다.이 때 제외되는 사람의 순서를 요세푸스 순열이라고 한다.마지막으로 제외되는 사람을 구하는 것이 요세푸스의 문제이다. Ex) n = 7, k = 3인 경우 3, 6, 2, 7, 5, 1 순서로 제거된 후 4가 마지막으로 남는다. Pythonn = 7, k = 3일 때 요세푸스 순열을 구하라.n, k = map(int, input().split());arr = [];result = [];ind..
![]()
유클리드 호제법이란두 양의 정수 혹은 두 다항식의 최대 공약수를 구하는 방법이다.호제법이란 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 말한다. 알고리즘두 양의 정수 a, b (a > b)에 대하여 a를 b로 나눈 나머지를 r이라 하면, a, b의 최대 공약수는 b와 r의 최대 공약수와 같다.이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. Ex) 78696, 19332의 최대 공약수를 구하시오.더보기78696 = 19332 x 4 + 136819332 = 1368 x 14 + 1801368 = 180 x 7 + 108180 = 108 x 1 + 72108..
