자료구조
-
[Data Structure] 자료구조 - 큐(Queue)CSE/Data Structure 2015. 6. 12. 16:14
큐(Queue) 개념: 스택과 마찬가지로 삽입, 삭제의 위치와 방법이 제한되어있는 유한 순서 리스트(Finite ordered list)지만, 스택과 달리 리스트의 한쪽 끝에서는 삽입 작업이 이루어지고, 반대쪽 끝에서는 삭제 작업이 이루어져서 삽입된 순서대로 삭제되는 선입선출(FIFO: First In First Out) 구조 입니다! 흔한 예로 볼수 있는게 놀이동산의 놀이기구 기다리는 줄이 있죠. 표로 조금 정리를 해서 스택과 큐의 연산을 비교해 보도록 하겠습니다! 항목 자료구조삽입연산삭제연산연산자삽입 위치연산자삽입 위치스택pushtoppoptop큐enQueuereardeQueuefront 이처럼 큐의 삽입은 rear에서 일어나고 큐의 삭제는 front에서 일어납니다! 아래는 큐의 구조입니다! 위에 보..
-
[Data Structure] 자료구조 - 스택 (Stack)CSE/Data Structure 2015. 6. 12. 16:12
스택(Stack) 개념: 스택은 같은 구조와 크기의 자료를 top 이라고 정한 한 곳에만 쌓을 수 있고, top으로만 접근하도록 제한하여 만든 자료구조 스택에서 top을 통해 들어온 자료가 일정한 방향으로 차곡차곡 쌓입니다. 마치 뷔페식당의 쌓인 접시나 책상위에 차곡차곡 쌓아 둔 책 과 같이 말이죠~ 스택에서 자료를 삭제할 때도 top을 통해서만 가능하기 떄문에 top이 가리키고 있는 스택의 마지막 자료만 삭제할 수 있습니다. 따라서, 스택은 시간순서에 따라 자료가 쌓이고, 삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO: Last In First Out)의 구조를 갖습니다. 스택의 구조 위처럼 data1,2,3이 차곡차곡 쌓이고 stack에서 top의 위치는 data 3을..
-
[Data Structure] 자료구조 - 연결 리스트(Linked List) - 이중 연결 리스트(Double Linked List)CSE/Data Structure 2015. 6. 12. 16:10
3. 이중 연결 리스트 이번에는 이중 연결 리스트에 대해 포스팅을 진행해 보도록 하겠습니다!!! 개념: 노드에 두 개의 링크 필드와 한 개의 데이터 필드로 구성된 연결리스트 입니다!! 그림으로 삽입, 삭제 연산을 먼저 짚고 넘어가죠!!! 다시 등장한 우리의 진짜 사나이들!!! 이제는 서병장, 호주 물개, 선착수로를 못 본다는게 슬프네요 ㅠㅠ 자 이렇게 서로 서로 참조를 하고 있는 구조가 이중 연결 리스트 입니다. 삽입 연산 여기서 수로형님이 샘과 헨리의 중간에 삽입이 된다고 보죠!! 이렇게 들어갔습니다!!! 그럼 링크에 대해 수정이 좀 가해지겠죠??? 먼저 김수로의 왼쪽 참조를 샘으로 설정!!! 그러고나서 김수로의 오른쪽 참조를 헨리로 설정!!! 그리고 샘의 오른쪽 참조를 김수로로 설정하고 헨리의 왼쪽 ..
-
[Data Structure] 자료구조 - 연결 리스트(Linked List) - 원형 연결 리스트(Circular Linked List)CSE/Data Structure 2015. 6. 12. 16:06
a2. 환영 연결 리스트 자 2번째는 환영 연결 리스트(Circular Linked List) 입니다! 개념: 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드(Head)를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트 그림을 통해서 먼저 삽입, 삭제 연산을 알아보도록합시다! 이번에도 진짜사나이 친구들이 나옵니다! 삽입 연산 단순 연결 리스트랑 다르게 형식이도 다음 사람의 이름을 가지고 있는 겁니다! 이젠 기차가 아니라 강강 수월래 라고 할수 있겟죠?? 저렇게 셋이서 강강 수월래~ 하고 있는데!! 헨리가 이번에도 끼어서 하고 싶다네요~ 그래서 샘과 형식 사이에 끼려고 합니다!!! 이렇게 말이죠~ 아 그럼 어떻게 해야 할까요???? 헨리가 샘과 형식 중간에 끼어들었군요. 그러면 서로 참..
-
[Data Structure] 자료구조 - 연결 리스트(Linked List) - 단순 연결 리스트(Singly / Linear Linked List)CSE/Data Structure 2015. 6. 12. 16:04
1. 연결 자료구조 개념: 순차 선형 리스트(배열)는 논리적인 순서와 물리적인 순서가 같기 때문에 원소의 위치를 찾아 액세스하기 쉽다는 장점이 있지만, 삽입 연산이나 삭제 연산에 원소들을 이동시키는 추가적인 작업과 시간이 필요함. 원소의 개수가 많고, 삽입, 삭제 연산이 많이 발생하는 경우에는 원소들의 이동 작업으로 인한 오버헤드가 증가함. 결국, 메모리 사용의 비효율성의 문제를 갖음. 이로 인한 문제를 개선한게 바로 연결 자료구조!!! 각 원소에 저장되어 있는 다음 원소의 주소에 대한 참조에 의해서 연결되는 방식! 효율적으로 메모리 사용을 할 수 있다! 종류: 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트 1-1. 노드 개념: 연결 자료구조 방식에서 원소는 연결될 다..
-
[Sort] 힙 정렬(Heap Sort]CSE/Sort 2015. 6. 12. 15:52
힙 정렬(Heap Sort) 정의: 힙이라는 자료구조를 이용하여 정렬하는 방법 힙은 삭제 연산을 수행하면 가장 최상위 루트원소를 반환한다. 최상위 루트원소는 힙 내부에서 가장 큰 원소이다. 힙정렬.... 힙을 이용해서 정렬을 하므로 굉장히 쉽게 사용되죠~ 왜냐면 힙 구현해 놓고 삭제 연산을 하면 정렬이 되니깐요!!! 한번 봅시다 ! 1단계 자 이렇게 최대 힙이 구성이 되어있습니다!!! 여기서 힙의 삭제연산을 합니다!! 삭제 연산은 루트 를 반환한다고 했죠??? 루트를 반환하고 힙은 다시 최대 힙을 구성합니다! 아래처럼 말이죠~ 1단계 끝!! 2단계 삭제 연산을 진행해야 겠죠??? 아래처럼 진행됩니다!! 계속 힙안에 있는 원소를 삭제 시키는 겁니다... 3단계 계속 삭제... 힙이 보잘것 없어서 아예 없어..
-
[Sort] 기수 정렬(Radix Sort)CSE/Sort 2015. 6. 12. 15:49
기수 정렬(Radix Sort) 1단계 2단계 [출처: gifsoup] 정의: 분배 방식의 정렬 방법으로 정렬할 원소의 키값에 해당하는 버킷에 원소를 분해하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복하며 정렬함. 그림으로 보시겠습니다!!! 1단계 자 이게 첫 단계의 그림인데요~ 좀 이전의 정렬과는 다른 양상을 보이죠??? 기수 정렬은 기수를 이용한 정렬이니깐 저렇게 버킷이 존재합니다!! 1단계에서는 기수 즉, 정렬할 값들의 1의 자리를 가지고 정렬을 시도 합니다!! 음... 힌트를 드리자면, 저 위의 숫자에서 지금 단계에서 중요한건 0 1 2 6 8 9 위의 숫자들이란 겁니다!!! 버킷의 갯수를 보시면 10개 입니다. 왜냐하면 0 부터 9까지 넣겠다는 겁니다. 그래서 정렬할 숫자들의 1의 자리 수..
-
[Sort] 합병 정렬(Merge Sort)CSE/Sort 2015. 6. 12. 15:46
합병 정렬(Merge Sort) [출처: 위키] 정의: 여러 개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 방법 Divide & Conquer !!!! 1단계 자 위와 같이 숫자를 두고 정렬을 해봅시다!! 합병 정렬의 개념은 일단 다시 그림을 그려서 설명해야 겠네요~ 이렇게 처음에는 붙어있다고 생각하세요!! 여기서 1개의 원소집합을 갖는 부분 집합으로 쪼갭니다~ 처음엔 요렇게 2등분 했다고 보죠 다음은 분리된 걸 또 분리. 또! 분리... 각각 1개의 원소로 분리 됬네요~? 네 여기까지 분할 단계를 끝마치네요~! 2단계 이젠 다시 합쳐야 할 시간입니다!!! 합치면서 정렬됩니다!! 자 위 그림에서 등분된 집합이 다시 합쳐지는 꼴을 봅시다!! 이렇게 4개의 부분 집합으로 다시 합쳐졌죠?..