L.O.K

예제 ) 트럭에 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번 ..

선형검색을 할 때, 결과는 두 가지다. 1. 원하는 값을 찾았는가? 2. 원하는 값을 못 찾았는가? 그래서 if문도 두 가지다. //검색 시작 for(int i =0; i