COMITO

*이진탐색(Binary Search) 분할정복과 이진탐색 분할정복 알고리즘(Divide and Conquer) 문제를 하나 또는 둘 이상으로 나눈다. (Divide) 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.(conquer) 이진탐색 리스트를 두 개의 서브리스트로 나눈다. (Divide) (1) 검색할 숫자(search) > 중간 값 => 뒷 부분의 서브리스트에서 검색할 숫자를 찾는다. (2) 검색할 숫자(search) 앞 부분의 서브리스트에서 검색할 숫자를 찾는다. #코드1 : 재귀호출 사용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import ..

- 재귀용법을 활용한 정렬 알고리즘 1) 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 2) 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬한다. 3) 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. ================================= index : 0 1 2 3 4 5 6 7 value : 49 97 53 5 33 65 62 51 ================================= pivot선택 : (index : 0, value : 49) p1 (1회) [left] - (index : 0, value : 49), (index : 1, value : 97), (index : 2, value : 53), (index : 3, value : ..

- 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모으는 함수를 작성. - 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복. - 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함. ================================= index : 0 1 2 3 4 5 6 7 value : 49 97 53 5 33 65 62 51 ================================= pivot선택 : (index : 0, value : 49) p1 (1회) pivot - (index : 0, value : 49) [left] - (index :..

- 동적 계획법(Dynamic Programing) -> 입력 크기가 작은 부분의 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분문제를 해결하여 최종적으로 전체 문제를 해결하는 알고리즘. -> 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 -> Memorization 기법을 사용 : 프로그램 실행 시 이전 단계에서의 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행속도를 빠르게하는 기술. -> 문제를 잘게 쪼갤 때, 부분문제는 중복되어 재활용됨. ex)피보나치 수열 - 분할정복(Divide and Conquer) -> 문제를 나눌 수 없을 때까지 나누어서 각각 풀면서 다시 합벼하여 문제의 답을 얻는 ..

- 모든 경우를 시도해봄으로써 답을 구하는 방법 - 모든 겨우를 시도해보는 코드를 짜기가 까다로운 경우 예) N개의 카드가 있고, 각각은 1부터 N까지의 번호를 찾는다. 이를 한 줄로 세울 수 있는 모든 경우를 출력하시오 N = 3 (3중 반복문 필요) 123 132 213 231 312 321 - N중 반복문을 돌려야한다? 재귀호출 #아이디어 1 2 3 4 5 6 7 8 9 10 n = 3 def doRecursion(x): # x번 째 for문을 실행 if x > n: pass #print numbers else: for i range(1, n+1): if 아직숫자 i가 없다면, x번 째 for에서 숫자 i를 등록하고, doRecursion(x+1) doRecursion(1) Colored by Co..

: 함수 안에서 동일한 함수를 호출하는 형태. 자기 자신을 호출하는 함수. - 재귀 호출의 일반적인 형태 1) 1 2 3 4 5 6 7 def functino(입력): if 입력 > 일정값: # 입력이 일정 값보다 크면 return function(입력-1) else: return 일정값 # 재귀호출종료 cs #팩토리얼1 1 2 3 4 5 6 7 8 def factorial(num): if num > 1: return num * factorial(num-1) else: return num print(factorial(4)) Colored by Color Scripter cs - 재귀 호출의 일반적인 형태 2) 1 2 3 4 5 def functino(입력): if 입력 > 일정값: # 입력이 일정 값보다..

문제 두 종류의 부등호 기호 ‘’가 k 개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 0 이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들..

문제 임의의 자연수는 그보다 작은 자연수들의 합으로 표현될 수 있다. 예를 들어 4의 경우, 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1 위와 같은 방법으로 표현 될 수 있다. 이 때 , 숫자의 구성이 같으면서 그 순서만이 다른 경우는 같은 경우로 생각하는데, 예를 들어 다음 세 가지 경우는 모두 같은 경우이다. 2 + 1 + 1, 1 + 2 + 1 , 1 + 1 + 2 자연수 n을 입력 받아 이를 n보다 작은 자연수들의 합으로 나타내는 방법을 모두 출력하는 프로그램을 재귀 호출을 사용하여 작성하시오. 입력 첫 줄에 2 이상 20 이하의 자연수 n이 주어진다. 출력 첫째 줄부터 모든 방법을 한 줄에 하나씩 출력한다. 하나의 식 안에는 큰 숫자가 앞으로 오도록 하고, 전체적으로는 앞의 숫자가 ..

문제 서로 다른 n개의 원소들 중에서 r개만을 뽑아 일렬로 나열하는 것을 순열이라 한다. 예를 들어, 3개의 원소 a, b, c 중에서 2개만을 뽑아 나열하면 ab, ac, ba, bc, ca, cb 의 6가지 경우가 있다. n과 r이 주어질 때, n개의 소문자 중에서 r개만을 뽑아 나열하는 모든 경우를 출력하는 프로그램을 작성하시오. 단, a부터 시작하여 연속으로 n개의 알파벳을 갖고 있다고 하자. 입력 첫 번째 줄에 n과 r이 주어진다. ( 1 ≤ n ≤ 10, 0 ≤ r ≤ min(n, 7) ) 출력 각 줄에 n개의 소문자 중에서 r개만을 뽑아 나열하는 경우를 사전순으로 나열한 결과를 출력한다. 예제 입력 4 2 예제 출력 ab ac ad ba bc bd ca cb cd da db dc #내코드 1..

문제 가로 N칸, 세로 M칸으로 이루어진 격자판이 주어지고, 그 중 한 개의 칸에 로봇이 존재한다. 로봇은 동(E), 서(W), 남(S), 북(N) 4 방향으로 움직일 수 있다. 각 칸에는 로봇이 얻을 수 있는 점수가 적혀있거나 장애물이 존재한다. 점수는 자연수로 주어지며, 장애물은 -1로 주어진다. 로봇은 움직일 때 마다 자신이 위치해 있는 곳의 점수를 얻게 되고, 해당 칸의 값은 0으로 바뀌게 된다. 로봇의 초기 위치에는 장애물이 존재하지 않으며, 항상 초기 위치에 있는 점수를 얻으며 움직이기 시작한다. 성우는 총 L회 로봇을 움직일 수 있으며, 각 회마다 성우는 로봇이 이동할 방향과 크기를 정해줄 수 있다. 예를 들어, 한 회에 로봇을 서쪽으로 3칸 움직일 수 있다. 이렇게 로봇이 이동하는 동안 방..