자료구조15 힙 정렬 힙 정렬부터는 갑자기 생각해야 할 것들이 많아 졌다. 힙 정렬은 말 그대로 자료구조의 힙을 이용한 정렬 방식이다. 우선 힙의 특징은 - 완전 이진트리 구조를 가진다. - 노드 중에 최대값 or 최소값을 빠른시간 내에 찾기위해 만든 자료구조다. 힙 정렬은 힙에 정렬 대상을 모두 넣었다가 다시 하나하나 꺼내면서 정렬을 한다. 장점은 성능이 앞에서 배운 버블, 선택, 삽입 정렬에 비해 월등히 우수하고 추가 메모리가 필요하지 않다. 단점은 데이터 구조에 따라 다른 정렬에 비해 늦을 수 있다는 점이며, 안정성이 보장되지 않는다. (안정성이 보장되지 않는다는게 정확이 무슨 뜻인지는 잘 모르겠다.) 힙 정렬 코딩시 알아두어야 할 점은 노드하나를 i라고 가정할 때 노드 i의 부모노드 인덱스 : i/2 (단, i>1) .. 2018. 1. 11. 버블,선택,삽입 정렬 오늘은 정렬을 정리해보려 한다.먼저, 버블정렬 버블정렬은 인접한 인덱스끼리 값을 비교하여 큰 값을 뒤로 보내는 방식이다. 구현하기가 쉬우나, 복잡한 프로그램은 비교횟수가 많아져 사용하지 않는다. 다음은 선택정렬 선택정렬은 a[0]번의 인덱스를 하나하나 비교해가면서 최소값을 찾아 자리를 바꿔주는 방식이다. 삽입정렬은 이동을 하면서 값을 비교해 삽입 할 위치를 결정하는 방식이다. 정렬완료된 부분과 그렇지 않은 부분을 나눠놓고, 정렬되지 않은 부분의 값을 정렬완료된 부분의 인덱스와 하나하나 비교해가면서 조건이 맞는 곳에 삽입이 되는 방식이다. 또한, 성능이 좋은 편이어서 다른 정렬의 일부분으로도 쓰인다. 하지만 데이터 한개의 크기에 따라 성능 편차가 심하다. 2018. 1. 10. 배열을 이용한 스택 13년도 이후로 자료구조를 펴보지 않아 기억이 나지 않아서 당분간은 자료구조를 보려고한다..오늘은 스택! 스택(Stack)은 후입선출(Last - Input, First-Out)LIFO 구조를 가진 자료구조이며,Top : 스택의 맨 윗 부분Bottom : 스택의 맨 아래 부분Push : 스택에 데이터를 푸쉬(넣는 것)를 의미Pop : 스택에서 데이터를 빼는 것을 의미Peek : 스택에서 Top 위치에 있는 데이터를 확인 하는 것을 의미, 데이터가 증가하거나 감소하지 않음.Stack Underflow : 스택이 비어있을 때 Pop하려는 경우 발생, 더 이상 감소시킬 데이터가 없기 때문에Stack Overflow : 스택이 꽉차있을 때 Push하는 경우 발생, 더 이상 공간이 없는데 추가를 하려했기 때문에로.. 2018. 1. 3. 이전 1 2 3 다음
