알고리즘19 [알고리즘] [7] 조합 1. 조합 (Combination) 서로 다른 n개의 원소 중 r개를 순서 없이 택하는 것 nCr = n-1Cr-1 + n-1Cr 의 재귀적 표현이 가능하다. nC0 = 1 재귀를 이용한 조합 생성 // nCr input[]; // n 개의 원소를 가지는 배열 numbers[]; // 조합을 저장할 r 크기의 배열 comb(cnt, start) { // cnt : 현재까지 선택한 원소 개수. start : 조합할 원소의 시작 인덱스 if (cnt == r) { return; } else { for (i = start; i < n; i++) { numbers[cnt] = input[i]; comb(cnt + 1, i + 1); } } } 2. 중복조합 순서가 무관하지만 원소의 중복이 가능한경우 nHr = .. 2024. 1. 31. [알고리즘] [6] 완전탐색, 순열 1. Baby-gin Game 0 ~ 9 사이의 숫자 카드에서 임의로 6장을 뽑았을 때 3장의 카드가 연속 번호를 가지는 run과 3장의 카드가 동일한 번호를 가지는 triplet으로만 구성되는 경우를 baby-gin이라고 한다. 6자리 숫자를 입력받았을 때 baby-gin 여부를 판단하는 프로그램을 작성한다. (1, 2, 3, 1, 2, 3) 정렬하여 확인하는 등 탐욕 알고리즘적인 접근은 해답을 찾지 못할 수도 있다. 2. 완전 검색 (Exhaustive Search) 모든 경우의 수를 나열하고 확인하는 기법 Brute force 혹은 generate-and-test 기법이라고 부른다. 상대적으로 빠른 시간에 알고리즘 설계가 가능하며 경우의 수가 작은 경우 유용하다. 수행 속도는 느리지만 해답을 찾아내.. 2024. 1. 30. [알고리즘] [5] 재귀 1. 반복 (Iteration)과 재귀 (Recursion) 수행하는 작업이 완료될 때까지 계속 반복하는 것을 반복이라고 한다. 재귀 : 주어진 문제의 해를 구하기 위해 더 작은 문제로 쪼개고 그 결과를 합하는 것 반복은 현재 행위를 끝내고 다음 반복으로 가므로 다시 돌아올 수 없다! 재귀 함수 (recursive function) 함수의 정의 및 역할을 명확히 한다. >> 현재의 동작과 같은 형태를 취할 수 있어야 한다. 함수 수행에 필요한 매개 변수를 설계한다. 재귀의 종료 조건이 반드시 필요하다. 기본 부분 (basic part)와 유도 부분 (inductive part)로 구성된다. >> 재귀의 끝과 재귀 파생 함수 호출은 스택 메모리 구조를 사용한다. 2024. 1. 29. [알고리즘] [4] 문제 해결 1. 알고리즘 컴퓨터 분야에서 알고리즘을 표현하는 방법은 크게 의사코드와 순서도 두 가지다. 의사코드는 자연어를 활용하여 서술하는 형태로 작성할 수 있다. 좋은 알고리즘? 정확성 : 얼마나 정확하게 작동하는지 >> 반례를 찾는다. 작업량 : 더 적은 연산으로 결과를 얻어낸다. 메모리 사용량 : 더 적은 메모리를 사용한다. 단순성 최적성 : 더 이상의 개선의 여지 없이 최적화 시간 복잡도 : 연산의 작업량, 수행 시간 Best Case : 빅 오메가 표기법 Worst Case : 빅 오 표기법 >> 알고리즘 문제 해결 시에는 빅 오 표기법을 사용한다. Average Case : 빅 세타 표기법 공간 복잡도 : 메모리 사용량, 생성하는 객체, 배열 등의 크기 복잡도의 점근적 표기 시간 복잡도 함수 중 가장 .. 2024. 1. 29. 이전 1 2 3 4 5 다음