데이터 분석 기술 블로그

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이 아닙니다..

1. 반복(Iteration)과 재귀(Recursion)반복과 재귀는 유사한 작업을 수행할 수 있습니다.반복은 수행하는 작업이 완료될 때까지 계속 반복합니다.루프(for, while 구조)재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 분제의 해를 이용하는 방법입니다.하나의 큰 문제를 해결할 수 있는 (해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합합니다.재귀 함수로 구현2. 반복구조초기화반복되는 명령문을 실행하기 전에 (한 번만) 조건 검사에 사용할 변수의 초기값을 설정합니다.조건검사 (check control expression)반복할 명령문 실행 (action)업데이트 (loop update) : 무한 루프(infinite loop)가 되지 않게 조건이 거짓(false)이 되게 합니..

1. 힙(heap)완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조입니다.최대 힙(max heap)키값이 가장 큰 노드를 찾기 위한 완전 이진트리입니다.{ 부모노드의 키값 >  자식노드의 키값 }루트 노드 : 키값이 가장 큰 노드최소 힙(min heap)키값이 가장 작은 노드를 찾기 위한 완전 이진트리입니다.{ 부모노드의 키값  루트 노드 : 키값이 가장 작은 노드2. 힙을 이용한 우선순위 큐

1. 이진 탐색 트리2. 이진 탐색 트리 - 연산3. 이진 탐색 트리 - 성능4. 이진 탐색 트리 - 연산 연습