데이터 분석 기술 블로그

주어진 배열을 두 개로 분할하고 각각을 정렬합니다.병합 정렬과 다른 점은 병합 정렬은 그냥 두 부분으로 나누는 반면에, 퀵 정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킵니다.또, 각 부분 정렬이 끝난 후, 병합 정렬은 "병합"이란 후처리 작업이 필요하나, 퀵 정렬은 필요로 하지 않습니다.

1. 이진트리(Binary Tree)2. 이진 트리 - 특성3. 이진 트리 - 종류4. 이진 트리 - 순회(traversal)5. 트리의 표현6. 트리의 표현 - 연결리스트7. 연습 문제

1. 문제 제시 : 계산기2. 트리(Tree)트리는 사이클이 없는 무향 연결 그래프입니다.두 노드(or 정점) 사이에는 유일한 경로가 존재합니다.각 노드는 최대 하나의 부모 노드가 존재할 수 있습니다.각 노드는 자식 노드가 없거나 하나 이상이 존재할 수 있습니다.3. 트리 용어

1. 상태 공간 트리2. 상태공간트리를 구축하여 문제를 해결 3. 연습문제

1. 문제 제시 : N-Queen 문제2. 백트래킹(Backtracking) 개념여러 가지 선택지(옵션)들이 존재하는 상황에서 한가지를 선택합니다.선택이 이루어지면 새로운 선택지들의 집합이 생성됩니다.이런 선택을 반복하면서 최종 상태에 도달합니다.올바른 선택을 계속하면 목표 상태(goal state)에 도달합니다.

1. 문제 제시 : 병뚜껑 속의 숫자 게임2. 이진 검색(Binary Search)자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법입니다.목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행합니다.이진 검색을 하기 위해서는 자료가 정렬된 상태여야 합니다.3. 분할 정복의 활용병합 정렬은 외부 정렬의 기본이 되는 정렬 알고리즘입니다. 또한, 멀티코어(Multi-Core) CPU나 다수의 프로세서에서 정렬 알고리즘을 병렬화하기 위해 병합 정렬 알고리즘이 활용됩니다.퀵 정렬은 매우 큰 입력 데이터에 대해서 좋은 성능을 보이는 알고리즘입니다.4. 연습 문제

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 여부를 판단합니다.