데이터 분석 기술 블로그

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

1. 탐욕 기법을 통한 Baby-gin 문제 해결2024.06.17 - [알고리즘] - 완전검색 그리디 - 완전 검색 기법탐욕 기법을 통한 Baby-gin 문제 해결완전검색이 아닌 방법으로 풀어봅시다.6개의 숫자는 6자리의 정수 값으로 입력됩니다.counts 배열의 각 원소를 체크하여 run과 triplet 및 baby-gin 여부를 판단합니다.

1. 회의실 배정하기2. 활동 선택(Activity-section problem) 문제3. 탐욕 알고리즘의 필수 요소

1. 문제 제시 : 거스름돈 줄이기손님이 지불한 금액에서 물건값을 제한 차액(거스름돈)을 지불하는 문제를 생각해 봅시다."어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까요?"2. 탐욕(Greedy) 알고리즘탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 됩니다.여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달합니다.각 선택 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해달을 만들었다고 해서, 그것이 최적이라는 보장은 없습니다.일단, 한 번 선택된 것은 번복하지..

1. 조합2. 참고3. 연습문제

1. 부분 집합집합에 포함된 원소들을 선택하는 것입니다.다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것입니다.예) 배낭 짐 싸기(knapsack)N개의 원소를 포함한 집합자기 자신과 공집합 포함한 보든 부분집합(power set)의 개수는 2n개원소의 수가 증가하면 부분집합의 개수는 지수적으로 증가2. 부분 집합 생성 방법바이너리 카운팅을 통한 사전적 순서(Lexicographic Order)부분집합을 생성하기 위한 가장 자연스러운 방법입니다.바이너리 카운팅(Binary Counting)은 사전적 순서로 생성하기 위한 가장 간단한 방법입니다.

1. 문제 제시 : 여행사 BIG sale!2. 순열(Permutation) 3. 순열 생성 방법4. 참고5. 연습문제

1. 문제 제시 : Baby-gin Game설명0 ~ 9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet이라고 합니다.그리고, 6장의 카드가 run과 triplet로만 구성된 경우를 baby-gin으로 부릅니다.6자리의 숫자를 입력받아 baby-gin 여부를 판단하는 프로그램을 작성하세요.입력 예667767은 두 개의 triplet이므로 baby-gin입니다. (666, 777)054060은 한 개의 run과 한 개의 triplet이므로 역시 baby-gin입니다. (456, 000)101123은 한 개의 triplet가 존재하나, 023이 run이 아니므로 baby-gin이 아닙니다..