4. 분할정복 Divide : 문제를 같지만 더 작은 단위로 나눈다. Conquer : 분할된 작은 문제들을 해결한다. Combine : 작은 문제에 대한 해결책을 본래의 문제로 조합하여 대입한다. Recursive case : 분할된 소문제들이 재귀적으로 풀 만큼 충분히 크면 Recursive case라고 부른다. 소문제들을 풀다보면 원래 문제와 동일하지 않을 때도 있는데, 이 떄는 Combine 단계의 일부이다. Recurrences 재귀식을 푸는 세 가지 방법 : 점근적인 Θ 또는 O 상한을 얻는 방법 Substitution method : 수학적 귀납법을 통해 추측을 증명 ...
삽입 정렬 : 점진적인 방법 사용 원소 A[j]를 정렬된 부분 배열 A[1 .. j-1]의 적절한 위치에 삽입 2.3.1 분할정복 접근법 재귀적 구조 : 주어진 문제를 풀기 위해 자기 자신을 재귀적으로 여러 번 호출함으로써 밀접하게 연관된 부분 문제를 다룸. => 분할정복 접근법 분할정복 접근법 : 전체 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고, 부분 문제를 재귀적으로 품. 찾은 해를 결합하여 원래 문제의 해를 만들어 낸다. 분할정복의 3단계 ...
1.개발 진행 및 완료상황 2주차 파이썬 알고리즘 공부 이분탐색 ,분할정복 개념정리 및 문제 1회독 완료 스택 개념정리 및 난이도 하 문제 1회독 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 문제들 중 ‘괄호’관련된 문제에서 어려움을 겪었다. 사실 단순히 완성된 괄호인지를 판별하는 문제는 스스로 만든 코드로 완성되었는데, 이 코드를 이후 계산과 연관된 문제에 적용하니 되지 않았다. 코드를 다시 한번 점검해볼 필요성을 느꼈다. 이분탐색 문제는 변수를 설정함에 따라 목표에 달성했는지, 목표를 달성하면서 변수의 최댓값이나 최솟값을 설정하는 문제가 많았다. pl,pr,pc를 index값으로 설정할 것인지 원솟값으로 설정할지 잘 생각해야 한다. ...