목록분할 정복 (1)

데이터 분석 기술 블로그

분할 정복

1. 문제 제시 : 가짜 동전 찾기n개의 동전들 중에 가짜 동전이 하나 포함되어 있다. 가짜 동전은 진짜 동전에 비해 아주 조금 가볍다. 진짜 동전들의 무게가 동일하다고 할 때 양팔 저울을 이용해서 가짜 동전을 찾아보자.양팔 저울을 최소로 사용해서 가짜 동전을 찾는 방법은 무엇인가?예를 들어 동전이 24(진짜 23, 가짜 1)개 있다면?2. 분할 정복 기법설계 전략분할(Divide) : 해결한 문제를 여러 개의 작은 부분으로 나눕니다.정복(Conquer) : 나눈 작은 문제를 각각 해결한다.통합(Combine): (필요하다면) 해결된 해답을 모은다.3. 거듭 제곱4. 병합 정렬(Merge Sort)여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식입니다.분할 정복 알고리즘 활용..
알고리즘 2024. 6. 25. 21:25
이전 Prev 1 Next 다음