본문 바로가기

개발새발 개발자/자료 구조

 (37)
[자료구조] 5-4. 특수한 큐 큐에는 원형 큐, DEQ(디이큐 or 데크), 우선 순위 큐가 있다. 큐의 문제점은 rear가 maxSize-1이면 front에 빈 공간이 있어도 full이라고 판단하는 것이다. 이를 해결하려면 rear에 증가시킨 1을 다시 앞으로 보내면 된다. 0부터 n-1까지의 인덱스가 있다고 치면, n-1에 1을 더한 값을 n이 아니라 0으로 만들려면 어떻게 해야 할까?(n -1 + 1)%n, 즉 n-1에 1을 더한 뒤, 모듈러 연산으로 N을 걸어주면 된다. maxSize를 n이라고 하면 인큐를 할 때마다 리어에 +1을 한 다음 n으로 나눈다. 디큐를 할 때도 front + 1을 한 뒤 모듈러 n을 걸어준다. 모듈러 n을 한다는 얘기는 (n - 1) + 1 = n을 한 뒤, n % n = 0을 만드는 것이다. 즉,..
[자료구조] 5-3. 스택의 응용 위 보기들의 공통점은 무엇일까? 모두 줄을 서야한다는 공통점이 있다. 내가 첫번째로 줄을 섰다면 첫번째로 나갈 것이고, 마지막으로 들어왔다면 마지막으로 나갈 것이다. 큐는 이렇게 원소와 그 도착 시간을 저장한 리스트이다. 스택과 큐의 공통점: 리스트 안에서 순서를 바꾸지 않는다.스택과 큐의 차이점: 스택은 입출구가 같으나, 큐는 입구와 출구가 다르다. 큐의 새로운 원소는 항상 rear에 대기하고 front에서 빠져나간다. 따라서 원소의 추가와 제거가 양 끝에서 일어난다고 할 수 있다. 다른 말로는 First-In, First-Out. 즉, FIFO(피포)라고 한다. = Last-In, Last-Out LILO(라일로). 보통은 FIFO라고 한다. 정리하자면 rear는 원소가 추가되는 곳이고, front는..
[자료구조] 5-2. 스택의 응용 여러 응용 프로그램에서 stack은 매우 중요한 역할을 한다. 첫번째 응용 스택은 system statck이다. call stack이라고도 하는데, 함수 호출에 사용된다. 특히 재귀 호출에서 많이 사용된다. 아래의 예시를 보자. 이렇게 재귀 함수를 쓰면 맨 마지막의 1! = 1 이라는 종결 조건을 제시해줘야 한다. 이 함수를 사용해서 3을 집어넣었다고 생각해보자. fact(3)을 호출하면 메인 함수는 스택에 저장된다. fact(3)은 fact(2)를 부르고 또 다시 fact(3)이 스택에 저장된다. fact(1)을 부르면 또 그때 fact(2)가 스택에 저장된다. 가장 먼저 불린 main이 가장 아래에 있는 것이 보인다.(First In) 그리고 제일 마지막에 호출된 fact(2)가 TOP에 있다.(La..
[자료구조] 5-1. 스택과 연산 이번 시간에는 스택에 대해 공부한다. 병원에 가는 엘리베이터를 타야한다고 생각해보자. 엘베에서 내리면 바로 접수대가 있고 사람들 모두 빨리 접수하길 원한다. a, b, c, d, e 다섯명이 있을 때 나는 a라고 가정하면, 나는 맨 먼저 접수하기 위해 몇 번째로 엘리베이터에 타야 할까? 답은 다섯번째이다. 타는 문과 내리는 문이 같으며, 엘베 안에서 순서를 바꾸지 않기 때문이다. 이러한 형태를 스택이라고 부른다. 스택이란, 원소를 도착한 시간의 반대로 저장한 리스트이다. 도착 순서는 별도로 표기한다. 그리고 찾기 쉽게 순서대로 정렬한다. 그러면 순서가 인덱스와 비슷하게 되기 때문에 순서를 생략하고 그냥 원소만 써도 괜찮다. 이런 구조는 반드시 들어가고 나가는 곳이 하나여야 한다. 또한, 원소 추가와 제거..
[자료구조] 4-3. 이중 연결 리스트 이중 연결 리스트는 단일 연결 리스트와 달리 이전 원소의 링크까지 동시에 갖고 있는 것을 말한다. 다음에 오는 링크를 next, rlink(right link)라고 하며 이전에 오는 링크를 previous, llink(left link)라고 부른다. 이중 연결 리스트의 node는 내가 저장하려는 item과 llink, rlink라는 두 개의 포인터로 구성되어 있다. 단일 연결과 마찬가지로 head node를 가질 수 있다. 이중 연결 리스트의 생성과 검색은 단일 연결 리스트와 비슷하기 때문에 추가와 제거에 대해서만 알아본다. 추가 연산을 하려면 먼저 데이터를 추가할 새로운 node를 만든다. 이제 연결을 해야하는데, next와 previous가 연결이 되어야 해서 4개의 포인터 값을 바꾸는 복잡한 과정을..
[자료구조] 4-2. 단일 연결 리스트 단일 연결 리스트의 node는 내가 저장하려는 데이터(item)과 그 다음 node를 가리키는 link로 이루어져 있다. 단일 연결 리스트를 효율적으로 관리하기 위해 데이터는 없지만 첫번 째 node를 가리키는 link만 있는 head node를 추가로 사용하기도 한다. 단일 연결 리스트의 연산은 굉장히 다양한데 이 중에서 앞에 있는 4가지만 알아볼 것이다. 연결 리스트에도 정렬된 것과 정렬되지 않은 것이 있다. 역시 이번에도 정렬된 연결 리스트만 대상으로 알아볼 것이다. 또한, 배열과 달리 이진 검색이 허용되지 않는다. 먼저 생성을 살펴보자. 아직 원소를 하나도 추가하지 않았기 때문에 맨 앞에 있는 head node만 선언해주면 연결 리스트가 생성된다. 검색은 내가 찾는 원소를 저장한 node를 가리키..
[자료구조] 4-1. 연결 리스트 직원을 리스트로 관리한다고 가정하자. 총 8칸인데 이미 다른 카페의 직원 2명이 써있어서 6명만 들어갈 수 있다. 문제는 남은 6칸이 띄엄띄엄 있다는 것이다. 써있는 칸을 빼고 그냥 쭉 쓰는 방법이 있다. 이때, 우리 카페 직원을 다른 카페와 어떻게 구분할 것인지, 우리 직원을 어떻게 순서대로 부를 것인지 고민해야 한다. 일단 리스트에는 번호를 붙일 수 있다. 그리고 다음 사람을 쓰는 칸을 하나 더 만든다. 이렇게 하면, 돌이, 순이, 영이, 옥이, 철이, 훈이 순인 것을 알 수 있으며, 훈이는 다음에 올 사람이 없어서 -1로 표시한다. 이와 같이 다음 직원의 이름을 저장하는 형태를 연결 리스트라고 부른다. 저번 시간에 리스트의 정의에 대해 위와 같이 알아보았다. 리스트는 유한한 원소의 나열이며 인덱스를..
[자료구조] 3-3. 배열의 추가와 제거 배열의 추가 연산에 대해 알아보자. 추가 연산은 배열의 적절한 위치에 새로운 원소를 삽입하는 것이다. 정렬된 배열에 대해서 구현하기 때문에 위치가 어디로 지정될 지 모르는 상태에서 수행하게 된다. arr이라는 배열에 대해 DAT라는 원소를 삽입하려고 한다. 알파벳 순으로 보면 C와 E 사이에 오면 된다. 하지만 연속된 메모리 공간을 차지하고 있기 때문에 index 1과 2 사이에 빈 공간을 찾는 것은 불가능 하다. 따라서 DAT가 CAT의 다음 주소로 들어가면 그 뒤에 있는 모든 원소들이 한 칸씩 물러나게 된다. 하지만 이 과정에서 실제로 DAT가 어디에 들어갈지는 명시된 것이 아니라, 묵시적으로 서로 비교를 한 다음 결정한다는 특징이 있다. 추가 연산 수행은 4단계로 이루어진다. 1. 새로운 원소를 넣..

티스토리툴바