개념 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법 추가적인 메모리를 필요로 하지 않음 항상 O(n log n)정렬의 성능을 발휘 퀵정렬이 힙정렬보다 일반적으로 빠르게 동작 데이터의 순서가 바뀌는 불안정 정렬 1. 원소들을 전부 힙에 삽입 2. 힙의 루트에 있는 값은 남은 수들 중에서 최솟값(혹은 최댓값)을 가지므로 루트를 출력하고 힙에서 제거 3. 힙이 빌 때까지 2의 과정을 반복 시간복잡도 (Worst Case = Best Case = Average Case) O(n log n) 예제 코드 void heapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n ..

개념 분할정복 알고리즘 기법을 사용해서 배열을 작게 나누어 분할한뒤 다시 합치는 (병합, 합병하는) 방식의 정렬 퀵 정렬보다는 성능이 떨어짐 데이터 크기만한 메모리가 필요함 안정적 정렬 n-way 합병 정렬 1. 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할 2.부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성 마지막 남은 부분리스트가 정렬된 리스트 2-way 합병 정렬 1. 리스트의 길이가 1 이하이면 이미 정렬된 상태 2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눔 3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬 4. 결합(combine) : 두 부분 리스..

개념 리스트의 가장 작은 값을 선택하여 앞으로 하나씩 가져오는 방식 (오름차순) 1. 주어진 리스트 중에 최소값을 찾음 2. 그 값을 맨 앞에 위치한 값과 교체 (패스(pass)) 3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체 버블 정렬보다 성능이 좋음 작은 배열을 정렬할 때 삽입정렬이나 선택정렬이 더 빠름 제자리 정렬에 속함 시간복잡도 (Worst Case = Best Case = Average Case) 비교 - O(n^2) 교환 - O(n) 예제 코드 void selectSort(int array[], int n) { int temp; for (int i = 0; i < n - 1; ++i) { int index = i; for (int j = i + 1; j < n; ++j) { i..

2020 KAKAO BLIND RECRUITMENT (2020 카카오 블라인드 채용 문제) 기둥과 보를 세우는 문제입니다. 기둥 조건 1. 아래 기둥 위 2. 아래 왼쪽 보 3. 아래 오른쪽 보 보 조건 1. 아래 왼쪽 기둥 2. 아래 오른쪽 기둥 3. 왼쪽, 오른쪽 보 사이 위의 조건이 부합할때 기둥과 보를 세우고 기둥과 보를 제거할때 인접한 기둥과 보가 위의 조건에 위반되지 않는지 확인 한 후 제거하였습니다. 하드코딩으로 짜서 코드가 길게 나왔는데 다른 해설을 본 결과 위의 조건을 확인하는 함수를 만들고 삽입을 한 후에 전체가 조건을 만족하는지 확인 한 후에 만족하면 성공적으로 삽입이 된 경우이며, 만족하지 않으면 삽입을 할 수 없는 경우이므로 삽입한 것을 다시 제거해줍니다. 제거도 마찬가지로 제거를..

React Native란? (리액트 네이티브) React의 방식으로 동시에 iOS와 Android 모바일 애플리케이션 개발을 할 수있는 페이스 북의 오픈 소스 프레임 워크 *bridge : IOS, Android 네이티브 코드에 접근할 수 있는 일종의 다리 역할을 수행 1. 직접 작성하는 리액트 코드(리액트 웹 코드와 매우 흡사한) 파트 2. 작성한 코드가 시스템에서 해석된 자바스크립트 파트 3. “브릿지"라고 불리는 요소들의 집합 파트 4. 네이티브 파트

개념 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 정렬하는 배열이 작은 경우 효율적, 배열이 길 수록 비효율적 선택 정렬, 거품 정렬과 같은 O(n^2) 알고리즘에 비교하여 빠름 구현이 간단하며 Stable Sort (안정 정렬)임 1. 첫번째 원소를 리스트에 삽입 2. n번째 원소를 리스트에 적절한 위치에 삽입 (반복) 시간복잡도 Worst Case - 비교, 교환 O(n^2) Best Case - 비교 O(n), 교환 O(1) Average Case - 비교, 교환 O(n^2) 예제 코드 void insertionSort(int list[], int n) { int i, j, temp; for (i = 1; ..

개념 하나의 리스트를 피벗을 기준으로 분할하고 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬하는 과정을 반복한 다음, 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬 합병 정렬(Merge Sort)와 달리 퀵 정렬은 리스트를 비균등하게 분할 속도가 빠름 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 수행시간이 오래 걸림 1. 리스트 가운데서 하나의 원소를 고른다. (이렇게 고른 원소 = 피벗) 2. 피벗 앞에는 피벗보다 값이 ..

개념 서로 인접한 두 원소를 비교해서 일정한 기준을 만족하면 서로의 값을 교환하여 정렬하는 방식 코드가 단순해서 구현이 쉬움 비교 작업이 많아서 연산 시간이 오래 걸림 첫번째와 두번째를 비교 후 변경, 두번째와 세번째를 비교 후 변경, ... n번째와 n + 1번째를 비교 후 변경 위의 작업을 한번 수행시 마지막 위치에 가장 큰 값이 위치함 (오름차순 정렬의 경우) 그러므로 n번 수행을 하면 n개가 정렬이 됨 시간 복잡도 (Best Case = Average Case = Worst Case) T(n) = O(n^2) 예제 코드 void buubleSort(int array[], int len) { int temp; for (int i = len - 1; i > 0; --i) { for (int j = 0..