L.O.K

예제2) 문자 Arr에 반복되는 문자를 제거할 때 최소비용으로 제거하라. Greedy는 현재를 기준으로 최적을 선택하는 알고리즘이다. 알고리즘 Greedy한 접근방법 : 원소를 하나씩 접근할 때마다 현재를 기준으로 최소제거비용을 구한다. 현재의 Max 비용보다 낮으면 제거한다. 전체 범위 Max 비용을 고려하지 않는다. 참고영상

예제 ) 트럭에 4개의 컨테이너만 실을 수 있을 때, 최대 몇 개의 물건을 실을 수 있는가? Greedy는 현재를 기준으로 최적의 수를 생각하는 방법이다. 트럭에 최대의 물건을 실으려면 1개의 컨테이너에 최대한 많은 물건이 담긴 컨테이너 먼저 실어야 한다. 알고리즘 1) 물건의 개수가 많은 순으로 정렬한다. 2) 앞에서부터 하나씩 트럭에 싣는다. 참고영상

힙 정렬( Heap Sort )은 성능 좋은 정렬 알고리즘이지만 원리를 이해하기 쉽지 않다. 그 이유는 완전 이진 트리를 이용하기 때문이다. [자료구조] 완전이진트리 배열에 저장하기 완전 이진 트리를 이해하기 위해 이진 트리에 대해서 알아보자. 이진 트리란? 위 그림은 이진트리의 가장 기본적인 구조이다. 부모는 자식을 갖는다. 이는 굉장한 의미를 갖는다. 버블정렬, 퀵 lordofkangs.tistory.com 완전이진트리는 위 포스팅에 정리해놓았다. 간단히 요약하면 이진트리는 계층구조에 특별한 조건을 적용하면 탐색효율을 올릴 수 있다. 그 중에서 완전이진트리는 좌측노드부터 빈 노드 없이 채우기에 배열로 구현하기 쉽다. 배열로 구현하려면 부모와 자식간의 인덱스 관계를 알아야 한다. 부모의 인덱스가 N이라..

완전 이진 트리를 이해하기 위해 이진 트리에 대해서 알아보자. 이진 트리란? 위 그림은 이진트리의 가장 기본적인 구조이다. 부모는 자식을 갖는다. 이는 굉장한 의미를 갖는다. 버블정렬, 퀵정렬, 병합정렬은 모든 데이터가 동등한 지위를 갖었다. 그러나 힙정렬은 계층구조를 이용한다. 이런 수직적 구조는 '탐색'에 유용하기에 선택정렬을 응용한 힙정렬에는 알맞는 구조이다. 부모보다 작은 값은 왼쪽 자식, 부모보다 큰 값은 오른쪽 자식에 저장된다고 가정하자. 만약 탐색값이 부모보다 크다면 왼쪽 트리는 탐색할 필요가 없다. 그러므로 탐색할 노드의 수가 절반으로 줄어든다. 이와같이, 이진트리는 부모와 자식간의 규칙을 설정할 수 있다. 규칙은 데이터의 위치를 특정지을 수 있다. 이는 탐색에 유용하다. 그렇다면 구현은 ..

시간복잡도 O(N2)과 O(NlogN)의 차이는 분할정복을 하느냐 안 하느냐의 차이이다. N개의 수를 N번 비교하는게 아니라 (버블정렬) N개의 수를 분할한 수만큼 비교하는 것이다. (퀵정렬) [알고리즘] 버블정렬 향상 시키기 버블정렬은 가장 쉽고 이해하기 쉬운 정렬이다. 그러나 시간복잡도가 O(n2)이어서 효율이 좋지 않다. 7개의 수를 일차원 배열에 저장하였다. 이제 버블정렬을 사용하여 오름차순으로 바꾸어 보 lordofkangs.tistory.com [알고리즘] 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort)은 이름 그대로 정렬을 빠르게 하는 알고리즘이다. 그러나 버블정렬에 비해 빠를 뿐, 이름만큼 가장 빠른 정렬 알고리즘은 아니다. 퀵 정렬(Quick Sort) 알고리즘이란? 정렬 ..

[알고리즘] 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort)은 이름 그대로 정렬을 빠르게 하는 알고리즘이다. 그러나 버블정렬에 비해 빠를 뿐, 이름만큼 가장 빠른 정렬 알고리즘은 아니다. 퀵 정렬(Quick Sort) 알고리즘이란? 정렬 알고리 lordofkangs.tistory.com 이전 포스팅에서 재귀(recursive)함수를 활용한 퀵 정렬(Quick Sort)를 알아보았다. 일반적으로 퀵정렬은 재귀함수로 구현되지만 재귀함수는 한 가지 문제가 있다. 재귀는 메소드를 반복적으로 호출한다. 메소드는 본인의 영역이 있어야 하므로 호출할 때마다, Stack 영역의 메모리를 차지한다. 너무 많은 재귀함수 호출은 스택오버플로우를 발생시킨다. 그러므로 메모리의 효율적 관리를 위해 재귀함수가 아닌..

퀵 정렬(Quick Sort)은 이름 그대로 정렬을 빠르게 하는 알고리즘이다. 그러나 버블정렬에 비해 빠를 뿐, 이름만큼 가장 빠른 정렬 알고리즘은 아니다. 퀵 정렬(Quick Sort) 알고리즘이란? 정렬 알고리즘은 두 가지 원칙에서 비롯된다. 1. 두 수의 대소를 비교한다. 2. 두 수의 위치를 교환한다. '비교' 와 '교환'은 정렬의 근본개념이다. 비교와 교환을 어떻게 하느냐에 따라 다양한 정렬 알고리즘이 만들어진다. 퀵정렬의 비교, 교환 방식을 이해하기 위해 단순한 버블정렬과 비교하여 설명하겠다. 버블정렬은 우측 끝부터 두 수를 비교하는 방식이다. 그래서 포인터가 우측에서 좌측으로 이동하면서 두 수를 비교하여 작은 값을 좌측으로 교환한다.(오름차순) 버블정렬은 동일한 위치에서 비교와 교환이 일어난..

버블정렬은 가장 쉽고 이해하기 쉬운 정렬이다. 그러나 시간복잡도가 O(n2)이어서 효율이 좋지 않다. 7개의 수를 일차원 배열에 저장하였다. 이제 버블정렬을 사용하여 오름차순으로 바꾸어 보자. 버블정렬은 우측 끝부터 두 개씩 대소를 비교하여 위치를 바꾸는 방법이다. 모든 비교가 끝났을 때, 맨 좌측에는 오름차순일 경우 가장 작은 수, 내림차순인 경우 가장 큰 수가 자리잡는다. 이렇게 반복하여 좌측을 하나씩 오름차순 혹은 내림차순으로 정렬하는 방식이 버블정렬이다. 그러나 버블정렬은 효율이 좋지 않다. n개의 수를 정렬한다고 가정해보자. 1회전 : n-1 번 비교 2회전 : n-2 번 비교 3회전 : n-3 번 비교 . . n-1회전 : 1번 비교 (n-1) + (n-2) + (n-3) + .... + 2 ..

우리는 좀 더 빠른 성능의 탐색을 위해 이진탐색트리를 사용한다. 배열은 탐색시, n개의 데이터를 최대 n번 비교한다. 하지만 이진탐색트리는 다르다. 탐색하려는 값과 기준이 되는 노드를 비교하여, 크면 오른쪽으로 작으면 왼쪽으로 가서 매 비교때 마다 탐색할 노드의 수가 반씩 줄어든다. 데이터의 수가 8개가 있다면 배열은 최악의 경우, 8번의 탐색을 해야하지만, 하지만 이진트리는 log 8 즉, 단 3번 만에 원하는 데이터를 찾을 수 있다. 그러므로 이진탐색트리에서 높이(h)의 개념은 중요하다. 트리의 높이는 곧 탐색 횟수를 의미한다. 그러므로 높이(h) = log n 이다. 그러나 이는 균형잡힌 이진트리에서만 적용되는 개념이다. 만약 이진탐색트리가 이렇게 되어 있다면, 배열처럼 n개의 데이터를 최대 n번 ..

지난 포스팅에서는 HashMap의 기본 개념에 대해서 다루었다. HashMap은 key와 value로 구성된 Map 데이터를 해싱함수를 통해 산출된 인덱스 위치의 버킷(배열)안에 저장하는 자료구조이다. 해싱함수(function)는 key 값(X)을 받아 인덱스(Y)를 산출한다. 그래서 key값을 알면, 버킷의 위치를 바로 알 수 있어 HashMap은 시간 복잡도가 O(1)인 빠른 성능을 자랑한다. 그러나 key는 무한하지만 인덱스는 한정되어 있어 key들 간의 인덱스를 향한 충돌은 불가피하다. 그래서 충돌이 일어나는 인덱스에 또 다른 자료구조가 만들어 지는데 충돌 초기에는 Linked List 방식으로 Map 데이터가 저장된다. 그러다가 충돌횟수가 어느 임계점을 넘으면 Linked List 방식의 시간복..