algorithm/theory
분할 정복(Divide and Conquer)
👉 주어진 문제를 n개의 부분 문제들로 나눈 후, 각 부분 문제들의 해를 구하여 원래 문제의 해답으로 결합하는 방법이다. 👉 부분 문제들은 원래의 문제와 같은 유형이며, 처리해야 할 데이터의 크기만 작다. 👉 보통 순환 호출을 사용하여 해결한다. if(문제의 크기가 충분히 작으면) return 해답 else{ 문제를 더 작은 n개의 부분 문제들로 나눈다 나눈 부분 문제들에 대해서 다시 순환호출 return 부분 문제들의 해답 결합 } 1. 이진 탐색(이분탐색) 1.1 문제 : 정렬된 상태의 리스트에서 x의 값이 존재한다면, 그 위치를 결정하라 👉 분할 정복 기법 적용 n=1이면(원소가 1개 있을 때) { x=원소 return 해 x!=원소 return -1 } n>1이면 { 기준 원소보다 앞의 원소들 집..
→2021.05.19
algorithm/theory
알고리즘 설계기법 정리
알고리즘이란? - 문제를 해결하는 방법을 순서대로 명확하게 기술한 것 - 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것 - 문제 해결에 필요한 계산 절차 또는 처리 과정의 순서 - 제한된 시간과 공간 안에서 데이터를 어떻게 처리할 것인지 정의한 로직 - 알고리즘을 통해 특정한 입력을 받아서 실행한 결과인 해를 출력 1. 분할정복(Divide and Conquer) 1.1 정의 주어진 문제를 같은 유형의 더 작은 부분 문제들로 더 이상 나눌 수 없을 때까지 나눈다. 그리고 각각의 부분 문제들을 해결한 후, 다시 합병하여 문제의 답을 얻는 알고리즘이다. 1.2 전략 ① 분할(Divide) : 문제를 동일한 유형의 여러 하위 문제로 나눈다. ② 정복(Conquer) : 가..
→2021.05.19

• 이전
• 1
• 다음