Algorithm32 분할과 정복 내용정리 분할 정복 알고리즘 이란? 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. 일반적으로 재귀 함수로 구현한다. 설계 단계 Divide (분할) : 문제가 분할이 가능한 경우, 원래 문제를 분할하여 더 작은 하위 문제들로 분할한다. Conquer (정복) : 나누어진 문제가 여전히 분할이 가능하다면, 다시 Divide 수행하고 그렇지 않다면 문제를 해결한다. Combine (합치기): Conquer한 문제들을 통합하여 원래 큰 문제의 답을 얻는다. 장단점 장점 문제를 나눔으로써 어려운 문제를 쉽게 해결할 수 있다. 단점 재귀 함수를 호출한다는 점에서 함수 호출로 인한 오버헤드 발생, 스택에 .. 2021. 9. 13. [python] 2108번 - 통계학 문제 파이썬 풀이 보통 통계값을 파이썬으로 구할 때에는 numpy 라이브러리를 사용했었다. 그러나 알고리즘 풀이에서 numpy 라이브러리를 사용할 수 없다고 해 사용하지 않고 통계값을 구해보았다. import sys input = sys.stdin.readline from collections import Counter n= int(input().rstrip()) l = [int(input().rstrip()) for _ in range(n)] avg = round(sum(l)/n) l.sort() middle = l[n//2] rang = l[-1] - l[0] c = Counter(l) result = c.most_common(2) if len(result) == 2 and result[0][1] =.. 2021. 9. 8. 재귀 알고리즘 내용 정리 재귀 재귀란? 재귀의 사전적 정의는 다음과 같다. 재귀(recursion)란 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 재귀 호출 따라서 재귀 호출이란 함수 내부에서 함수가 자기 자신을 다시 호출하는 행위를 의미한다. 재귀 호출의 주의점은 자기 자신을 계속해서 호출하므로, 함수 내에서 호출을 일정 조건을 만족하면 중단할 수 있도록 조건이 변경될 명령문을 반드시 포함해야 한다. 재귀 호출과 반복문 비교 반복문 메모리 : 메모리 힙을 사용한다. 속도 : 빠름 무한 루프는 CPU 사이클을 반복적으로 사용한다. 코드 길이가 길어지고 변수 사용이 많아진다. (가독성이 떨어짐) 재귀 호출 메모리 : 스택 메모리를 사용한다. 속도 : 느림 무한 재귀는 스택 오버플로우를 일으킴 코드의 길이도 짧고 변수.. 2021. 9. 6. [python] 18870번 - 좌표 압축 문제 문제 풀이 자신보다 작은 수의 개수를 출력하는 문제이다. 크기 순대로 정렬하면 자신의 인덱스 번호가 자신보다 앞에 있는 원소의 수가 된다. 이를 이용하여 문제를 풀면 될 것 같으나, 신경 써야 할 점이 두 가지가 있다. 중복된 숫자의 경우 그대로 인덱스를 출력하면 같은 중복 횟수만큼 인덱스가 커져 자신보다 작은 원소의 수가 아니게 된다. 따라서 중복된 원소 처리를 신경 써야 한다. 리스트를 정렬 시 기존 리스트의 순서를 보존해야 출력 시 알맞게 출력할 수 있다. 1번의 경우 중복이 허용되지 않는 자료형인 집합 자료형을 이용하여 중복을 제거하였고, 2번의 경우 sorted를 이용하여 기존 리스트는 보존하고 정렬하여 새로운 변수에 저장하였다. import sys input = sys.stdin.read.. 2021. 9. 3. 이전 1 ··· 4 5 6 7 8 다음
