th42500의 TIL

Greedy Algorithm Greedy? 사전적 의미로는 탐욕스러운, 욕심 많은이라는 의미를 담고 있음 Greedy Algorithm 그리디 알고리즘은 Greedy의 사전적 의미인 "탐욕스러운"이라는 의미를 따와 탐욕법이라고도 불림 현재 상황에서 지금 당장 좋은 것만 고르는 선택을 반복적으로 활용하여 문제를 해결하는 방법 Greedy Algorithm의 필수 요소 탐욕적 선택 속성(Greedy Choice Property) 👉단순히 가장 좋아 보이는 방법을 선택했을 때 최적의 해를 보장할 수 있는지 검토함으로써, 탐욕적 선택이 항상 안전함을 보여야 함 최적 부분 구조(Optimal Substructure Property) 👉 현재 상황에서 가장 최적의 해를 구한 이후, 나머지에서 또 최적 해를 구하는..

순열(Permutation)과 조합(Combination) 순열(Permutation) https://ichijeochi.tistory.com/9?category=1012068 순열 (Permutation) 순열 (Permutation) 순열(Permutation) ? 👉 서로 다른 n개의 원소 중 r개를 순서대로 골라내어 한줄로 나열하는 것 순열의 수식 nPr = n개의 원소 중에 r개를 선택하여 일렬로 나열했다는 의미 nPn = 팩토리 ichijeochi.tistory.com 조합(Combination) https://ichijeochi.tistory.com/389?category=1012068 조합 (Combination) 조합 (Combination) 조합 (Combination) ? 👉 서로 다..

재귀 함수(Recursive Function) 함수 내에서 직접 혹은 간접적으로 자기 자신을 반복적으로 호출하는 함수 기저조건(Basis Part)과 유도파트(Inductive Part)로 구성 - 기저조건(Basis Part) : 재귀 함수 호출이 종료되는 조건 - 유도파트(Inductice Part) : 동일한 형태의 자기자신을 호출하되 더 작은 해를 반환하는 재귀문을 호출하는 파트 프로그램 메모리 구조에서 스택을 이용하며, 재귀의 Depth가 너무 깊으면 스택 오버 플로우가 발생하게 되므로 기저조건을 잘 판단해야 한다. 반복(Iteration) VS 재귀(Recursion) 반복과 재귀는 유사한 작업을 수행한다. 그래서 반복문으로 구현된 코드의 대부분은 재귀문으로 변환할 수 있으며 반대로 재귀문으로..

순열 (Permutation) 순열(Permutation) ? 👉 서로 다른 n개의 원소 중 r개를 순서대로 골라내어 한줄로 나열하는 것 순열의 수식 nPr = n개의 원소 중에 r개를 선택하여 일렬로 나열했다는 의미 nPn = 팩토리얼(Factorial)이라 불리며, n부터 1까지의 모든 수를 곱한 값 위의 식을 보면 반복되는 공식이 존재하므로, 순열은 재귀함수를 적용하여 나타낼 수 있음 재귀함수를 모른다면 밑의 링크를 참고해보자. 재귀함수 👉 https://ichijeochi.tistory.com/11 재귀 (Recursive) 재귀 함수(Recursive Function) 함수 내에서 직접 혹은 간접적으로 자기 자신을 반복적으로 호출하는 함수 기저조건(Basis Part)과 유도파트(Inductiv..