본문 바로가기

c & c++/algorithm10

순열과 조합 순열이란? - 순열(permutation)이란 순서가 정해진 임의의 집합을 다른 순서로 섞는 연산 - ex) 1, 2, 3이렇게 있을 때 1, 3, 2 이런식으로 다른 순서로 섞는 연산을 순열이라고 한다. - n 개의 집합 중 n개를 고르는 순열의 개수는 n!이라는 특징을 가지고 있다 1, 2, 3 = 3 * 2 * 1 = 6 - nPr = n! / (n - r)! -> 3개중에 3개 = 6 / 1 = 6 2023. 1. 18.
재귀함수 재귀함수란? - 재귀함수(Recursion)는 정의 단계에서 자신을 재참조하는 함수 - 전달되는 상태인 매개변수가 달라질 뿐 똑같은 일을 하는 함수 - 큰 문제를 작은 부분문제로 나눠서 풀 때 사용한다. 주의사항 - 반드시 기저사례를 써야 한다. (종료조건) - 사이클이 있다면 쓰면 안된다. ex) f(a)가 f(b)를 호출한 뒤 f(b)가 다시 f(a)를 호출하는 것 - 반복문으로 될 거 같으면 반복문으로. (함수호출에 대한 코스트) # 예시 - 팩토리얼 n! : 그 이전의 항을 모두 곱하는 것. 곱한다는 행위의 반복? - 피보나치 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 2023. 1. 18.
계수정렬(Counting Sort) Goal - Counting Sort 에 대해 설명할 수 있다. - Counting Sort 과정에 대해 설명할 수 있다. - Counting Sort를 구현할 수 있다. - Counting Sort의 시간 복잡도를 계산 할 수 있다. 1. Counting Sort Summary - '범위 조건'이 있는 경우에 한해서 제일 빠른 알고리즘 O(N) - '크기의 기준으로' 세는 알고리즘 2. Counting Sort Processing - 원소의 크기 범위만큼 배열을 만든다 - 각각 값들이 몇개인지 확인 후 그 개수만큼 출력 3. Counting Sort Coding //계수정렬 #include int main(void) { int i , j, temp; int count[5]; int array[30] =.. 2022. 7. 12.
힙 정렬(Heap) Goal - Heap Sort 에 대해 설명할 수 있다. - Heap Sort 과정에 대해 설명할 수 있다. - Heap Sort를 구현할 수 있다. - Heap Sort의 시간 복잡도를 계산 할 수 있다. 1. Heap Sort Summary - 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬방법 - 최솟값과 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리 - 이진 트리에 대한 이해 필요(완전 이진 트리) - 최대힙 = '부모 노드'가 '자식 노드' 보다 큰 힙 - 힙 생성 알고리즘 (Heapify Algorithm) 을 사용해야함 - 힙 생성 알고리즘 = 특정한 노드의 두 자식 중에서 더큰 자식과 자신의 위치를 바꾸는 알고리즘 2. Heap Sort Proces.. 2022. 7. 11.
병합 정렬(Merge Sort) Goal - Merge Sort 에 대해 설명할 수 있다. - Merge Sort 과정에 대해 설명할 수 있다. - Merge Sort를 구현할 수 있다. - Murge Sort의 시간 복잡도를 계산 할 수 있다. 1. Merge Sort Summary '반으로 쪼개고 나중에 합치기' 시간 복잡도 O(N * logN)을 보장해줌 2. Merge Sort Processing 1. 작은 순서대로 배열에 삽입 2. 남은 데이터 삽입 3. 정렬된 배열을 삽입 3. Merge Sort Coding #include int number = 8; int sorted[8]; //정렬 배열은 반드시 전역 변수로 선언 void merge(int a[], int m, int middle, int n) { int i = m; .. 2022. 7. 1.
퀵 정렬(Quick Sort) Goal - Quick Sort 에 대해 설명할 수 있다. - Quick Sort 과정에 대해 설명할 수 있다. - Quick Sort를 구현할 수 있다. - Quick Sort의 시간 복잡도를 계산 할 수 있다. 1. Quick Sort Summary '특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눔' 2. Quick Sort Process - 배열 가장 왼쪽 원소를 고른다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다. (key 값) - 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기 준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다. - 하나의 피벗이.. 2022. 6. 28.
삽입정렬(Insertion Sort) Goal - Insertion Sort 에 대해 설명할 수 있다. - Insertion Sort 과정에 대해 설명할 수 있다. - Insertion Sort를 구현할 수 있다. - Insertion Sort의 시간 복잡도를 계산 할 수 있다. 1. Insertion Sort Summary '각 숫자를 적절한 위치에 삽입하는 방법' '다른정렬 방식들은 무조건 위치를 바꾸는 방식이었다면 삽입정렬은 필요할때만 위치를 바꿈' 2. Insertion Sort Process - 앞에있는 원소들이 이미 정렬이 되어있다고 가정 - 앞에 원소들 자리에서 적절한 위치를 찾음 3. Insertion Sort Coding 4. Insertion Sort 시간 복잡도 장점 - 삽입 정렬은 정렬이 되어있다고 가정 한다는점에서 특.. 2022. 6. 28.
버블정렬(Bubble sort) Goal - Bubble Sort 에 대해 설명할 수 있다. - Bubble Sort 과정에 대해 설명할 수 있다. - Bubble Sort를 구현할 수 있다. - Bubble Sort의 시간 복잡도를 계산 할 수 있다. 1. Bubble Sort Summary '옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내기' '알고리즘 중에서 구현은 가장 쉽지만 가장 비효율적인 알고리즘' 2. Bubble Sort Processing 1. 첫번째 원소와 두번째 원소를 , 두번째 원소와 세번째 원소를.... 마지막-1 번째 원소와 마지막 원소 비교 2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 1회전 수행할 때마다 정렬에서 제외되는 데이터가 늘어난다. 3. Bubble Sort Coding 4... 2022. 6. 28.
선택정렬(selection sort) Goal - Selection Sort 에 대해 설명할 수 있다. - Selection Sort 과정에 대해 설명할 수 있다. - Selection Sort를 구현할 수 있다. - Selection Sort의 시간 복잡도를 계산 할 수 있다. 1. Selection Sort Summary '가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘' '가장 원시적이고 기초적인 방법 중 하나' 2. Selection Sort Processing 주어진 배열 중에 최소값을 찾는다. ↓ 그 값을 맨 앞에 위치한 값과 교체한다. ↓ 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 3. Selection Sort 구현 #include int main(void) { int i, j, min, index, te.. 2022. 6. 28.
알고리즘(algorithm) 산법, 셈법, 계산절차 알고리즘 정의 1. 수학과 컴퓨터 과학에서 어떠한 '문제를 해결하기 위해 정해진 일련의 절차' 2. 논리이며 수학이고 실질적인 개발에 적용되는 기초적인 아이디어. 3. 알고리즘은 정밀성, 유일성, 타당성, 입력, 출력, 유한성 을 만족해야 한다. 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다. 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다. 타당성 : 구현할 수 있고 실용적이어야 한다. 입력 : 정의된 입력을 받아들일 수 있어야 한다. 출력 : 답으로 출력을 내보낼 수 있어야 한다. 유한성 : 특정 수의 작업 이후 에 정지해야 한다. 2022. 6. 28.

티스토리툴바