시퀀스(Sequence), 트리(Tree)

msung99·2022년 4월 1일
자료구조
0
post-thumbnail

지난 내용 복습

리스트 ADT

  • 맨앞과 맨뒤의 노드만 위치를 찾아낼 수 있는 그런 방법을 제공하기 위해선, 자연스럽게 더블리 링크드 리스트 구현이 내부적으로 구현하는게 좋다.

  • 벡터가 배열의 확장이라면 리스트는 더블리 링크드 리스트를 확장한 개념

  • postiton 을 저장하는 자료구조로, position 을 통해 access한다.

  • position이 구현된다면 iterator 가되며, iterator 를 통해 access 한다.

    • 실제 STL list 는 더블리 링크드 리스트로 구현되어 있으며, position 으로 iterator를 사용한다.

    • 반복자(이터레이터)를 통해 포지션을 리턴하며, 이는 begin()과 end()로 초기화됨

    • begin()은 시작 원소, end()는 마지막 원소의 다음 주소를 리턴함

  • position을 주소값이라고 생각해도 무방하다. (실제로는 주소를 직접 주는것은 아님!)

  • 주어진 포지션과 해당 포지션의 next, prev를 이용해 연산을 수행하므로
    모든 연산 시간은 O(1)

Q. 반복자를 이동시키는 과정은 O(n) 아님? ⇒ 메서드 밖에서 구현하므로 상관 x

시퀀스

list 의 모든 메소드 뿐만 아니라 인덱스으로도 access 가능한 메소드도 추가되어 있는것

  • 데이터를 일렬로 정렬하는 자료구조의 끝.판.왕

  • 시퀀스를 이용해서 지금까지 배운 모든 자료구조(stack, queue, vector, list) 를 모든 구현할 수 있음 => 저 자료구조들이 지원해줘야 하는 메소드들을 모두 가지고 있다. ( = 모든 기능을 포함하고 있다)

    • 데이터들을 일렬로 줄을 세울 수 있는데, 어떤 연산들을 할 수 있느냐에 따라 스택이 될 수도 있고, 또는 큐, 벡터, 리스트가 될 수도 있다.

메소드

index 와 position 을 모두 사용하여 데이터 element에 access 가능
=> how 가능? : position 을 사용하는 함수 + index 와 position 을 변환하는 함수
의의 : 일렬로 정렬되는 자료구조의 완성형

  • 당연히, 리스트(list) 기반의 메소드들을 모두 포함

  • 추가로 index 를 통해 access 하는 메소드들로 제공

  • 메서드 : 리스트의 모든 함수(포지션 기반) + 포지션과 인덱스를 서로 변환하는 함수
    indexOf(p) - 포지션에 해당하는 인덱스 값 반환
    atIndex(i) - 인덱스에 해당하는 포지션 값 반환

메소드 상세 기능

  1. 리스트(list) 기반의 메소드 ( = position 으로 access 하는 메소드 )
  • insertFront(o)
  • insertBack(o)
  • insert(p,o)
  • eraseFront()
  • eraseBack()
  • erase(p)
  1. index 를 통해 access 하는 메소드
  • atIndex(i) : vector 의 at(i) 와 동일
  • indexOf(p) : vector 에는 없는 메소드. 주소(position) 값을 부여해주면 인덱스로 변환해주는 메소드
  1. 기타 메소드
  • size()
  • empty()

구현 - 배열 기반

요약 : 해당 원소에 자체에 대한 자료구조가 아닌, position에 대한 자료구조이므로, (데이터가 아닌 position을 저장하는 자료구조이므로)
메모리를 할당할 때, 주소에 해당하는 4byte로 모든 원소를 할당할 수 있음
(원래 원소가 몇바이트였는지 상관 없이 모두 4byte로 정렬 가능! ⇒ 메모리 절약)

배열의 각 인덱스에 저장된 포인터의 해당 주소값(position)을 따라가서 그 데이터를 확인해보면, 각 데이터는 int형, double형, 구조체 node형, ... 등 다양한 형태의 데이터 객체일 수 있다.

  • 환형 배열로 구현
    • 맨앞 삽입,삭제 연산(insertFront, eraseFront) 이 발생했을 때 그냥 배열로 구현하면 O(n) 이 걸리므로, O(1) 으로 빠른 처리가 되도록 환형으로 구현

  • f와 l을 사용 : 맨앞, 맨뒤 postition 을 저장 => 마치 큐의 front, rear 와 동일한 기능

  • 배열의 각 인덱스 방에는 position 이 저장되어있는 형태
    => 즉, 각 인덱스 방에 주소값이 저장되어있다.

각 인덱스에 저장된 주소(position)에 대한 객체들의 구성요소 : 데이터 필드, 인덱스 필드

각 position 에 대한 object 들은 데이터 값과 index 값을 저장하고 있다.

데이터 필드에는 그냥 데이터 값말고도 또 다른 데이터 객체에 대한 포인터 변수 주소값이 저장되어 있는 형태일 수 있다.

  • 각 인덱스에 저장된 주소를 따라가보면 무슨 타입인지는 몰라도 그 주소에 있는 object는 데이터 필드에 데이터와 인덱스를 나타내는 인덱스 필드에 index를 저장하고 있다.

    • 그 데이터 필드도 단순한 데이터 값이 아닌, position (주소값) 을 또 저장하고 있는 연결고리 형태일 수 있다.

    • 그 데이터 필드에 있는 데이터(구조체 포인터 변수 주소값)가 100바이트인 경우, 인덱스는 정수이므로 4바이트이므로 100+4 = 총 104바이트 크기를 차지한다.

    • 즉, 104바이트 짜리의 구조체 포인터 변수가 환형 배열 각 인덱스 방 안에 들어있게 된다.

배열의 인덱스와 시퀀스의 인덱스

(시퀀스 : 말그대로 연속적으로 저장된 데이터들. 배열의 각 인덱스에 저장된 주소를 따라갔을 때 있는 객체들을 의미한다)

  • 배열의 인덱스와 시퀀스의 인덱스가 불일치하는 경우 처리 방법

    • erase 연산 : front가 1증가하면서 배열의 원소들이 다 한칸씩 뒤로 밀리는 방법으로 구현할것

    • insert 연산 : rear 가 1증가하면서

    • 즉, 가령 0번 인덱스에 0번 시퀀스 객체를 저장하고 있었는데 이제 1번 인덱스에 0번 시퀀스 객체를 저장하게 된다.
      (배열의 인덱스:0->1, 그 인덱스에 대한 시퀀스 객체의
      인덱스 필드의 값 : 0 그대로 유지)

  • 구현 방법이 까다롭다!

구현 - 더블리 링크드 리스트 기반

  • atIndex(i), indexOf(p) 만 추가적으로 구현하면 끝

  • 배열을 기반으로 구현했기 때문에 list 연산은 다 포함하고 추가적인 연산이 있다. 결국 배열을 이용해서 리스트를 구현해야 하는 것과 마찬가지다.

환형 배열기반의 Sequence 메소드 구현

  1. insert(p,e) : O(n)
    • 환형 배열 중간 어딘가에 삽입하는 경우

환형 배열의 저장되있는 position 값들을 뒤로 한칸씩 미루고 확보된 공간에 새로 할당받은 position값인 p를 넣어야한다.
최악의 경우 n개를 다 미뤄야하므로 O(n) 이다.

  • position을 저장하는 환형 배열의 특정 위치p 에다 데이터 e를 넣는경우

  • 시퀀스 객체를 새로 생성

    • 인덱스 필드:시퀀스 객체들 사이에서 기준으로 3번째 객체라면, 인덱스 값 2를 부여
    • 데이터 필드 : 객체 e를 가리키는 포인터(주소값)을 저장.)
      => 환형 배열에는 특정 인덱스 방에 position(주소값) 값인 p를 저장해서 시퀀스 객체를 가리키게 하고, 시퀀스 객체는 데이터 필드에 새로운 객체 e의 주소값(position)을 저장함으로써 연결고리 형태로 또 새로운 객체 e를 가리키는 형태가 된다.

  • 환형 배열의 특정 셀에다 주소값 p를 저장하기 위해선, 기존에 배열에 저장되어있던 position 값들을 뒤로 한칸씩 다 밀어줘야한다. (공간 확보를 위해) => 최악의 경우 O(n) 이 걸린다.

  • 환형 배열의 position 값들을 한칸씩 이동시켜준 순간, 각 position들에 대한 시퀀스 객체들의 인덱스 필드 값을 1 증가시켜줘야한다.

    ( ex. 인덱스 필드가 3이 저장되어 있는 시퀀스 객체를 4로 바꿔주면서 이 시퀀스 객체는 4번째 객체가 되었음을 명시해준다 )

  1. insertFront, eraseFront, insertBack, eraseBack : O(1)
    • 환형 배열 맨앞에 대해서 insert, front 하는 경우
      ( insertBack, eraseBack 은 과정이 너무 쉬우니 설명 생략 ~)

  • insertFront : 인덱스 f의 앞 셀에다 position을 삽입후 f를 한칸 뒤로 미룬다 (맨앞 인덱스인 f의 " 앞 " 셀에다 insert하는 것이므로, 환형배열의 저장되있는 값들을 한칸씩 뒤로 미룰 필요x)

    • 연산후에 환형배열의 가장 앞 인덱스가 최신화 되었으므로, f 를 1 감소시킨다.

  • eraseFront : 인덱스 f의 값을 1증가시켜서 f를 한칸 뒤로 이동시킴

그 값을 얼마만큼 실제로 0에서 떨어져있는지를 구현을 잘 해내서 알고있다면,

(insert(0), erase(0), insertFront, eraseFront 등에서 연산을 할때마다 f를 증감하는 카운트를 잘 해서 시작 위치인 인덱스 f를 제대로 저장하도록 구현 되있는 경우)

f와 처음 인덱스 0과의 차이를 계산하면 몇칸만큼 떨어져있는 알 수 있으므로 insertFront, eraseFront 등을 구현 가능하다.

  1. atIndex( i ) : O(1)

시퀀스의 인덱스와 환형배열의 인덱스가 불일치할 수 있다는 점을 고려해야 한다.

  • i : 환형 배열에서의 인덱스가 아닌, 시퀀스 객체에서의 인덱스를 의미

  • 환형 배열에서 인덱스로 접근하는 법

    • 시퀀스의 인덱스와 환형배열의 인덱스가 불일치할 수 있다는 점을 고려해야 한다!

ex ) i=3 이고, f=1 인 경우 i=3의 시퀀스 객체에 대한 환형 배열의 position 은 환형배열에서 3+1 = 4번째 인덱스에 저장되어 있다.

따라서 환형배열의 인덱스 4번방에 저장되있는 position을 통해 해당 시퀀스 객체를 찾아내고, 그 시퀀스 객체의 데이터 필드에 저장되있는 값을 리턴받으면 된다.

  1. indexOf(p) : O(1)
  • 실제 주소값을 주기 때문에 간단함. 환형 배열에서
    주어진 주소값 (position) 에 해당하는 시퀀스 객체를 바로 찾아내고, 그 시퀀스 객체의 인덱스 필드의 값을 리턴받으면 됨

insertFront, eraseFront 의 시퀀스 객체 인덱스 값 최신화

insertFront, eraseFront 를 계속 진행하다보면 환형배열의 인덱스 값과 시퀀스 객체의 인덱스 값이 불일치할 수 있다.

예를들어 eraseFront가 된 경우 f가 한칸 증가해서, 시퀀스에 들어있던 각 객체들의 인덱스 필드의 인덱스 값이 모두 1감소해야 할까?

  • 이렇게 하면 O(1) 이 아닌 O(n) 이 되므로 비효율적이다. 환형배열의 맨앞 원소에 대한 insert,erase 연산이 O(1) 으로 빠른 연산이 가능하다는 메리트 성질을 잃게 됨.

  • 그냥 중간 원소에 대한 insert, erase 는 어짜피 환형배열에서 주소값들을 한칸씩 옮겨야 해서 O(n) 이 걸리므로, 시퀀스 객체들의 인덱스 값들을 최신화 해줘도 O(n) 이여서 상관없다. 하지만 insertFront, eraseFront 는 그러면 비효율적이라는 말이다.

=> eraseFront 가 되면 f가 1감소하는 횟수를 카운팅해서 따로 저장해 놓는다. 그러고 나중에 언젠가 한밤중에 기회가 될때 카운팅한 정보를 기반으로 불일치하던 인덱스를 일치시키도록 다시 sorting 시킨다.

  • 맨 앞에서의 insert, delete 연산이 자주 안 일어나면 O(n) 으로 사용해도 무방

  • O(1) 으로 구현한다면 환형배열의 인덱스 값과 그 인덱스에 해당하는 시퀀스 객체의 인덱스 값이 불일치 함을 감안하고 적절하게 코딩(구현) 할것

    • insertFront, eraseFront 의 횟수를 카운팅한다.

    • insertFront를 할때마다 f가 1감소, 또 eraseFront를 할때마다 f가 1증가한다.

    • 이런 연산의 횟수가 몇번이냐에 따라서 시퀀스 객체에 저장된 인덱스와 환형배열에 실제로 저장된 인덱스가 일치하지 않을 수 있다.

    • 아예 시퀀스 객체에 인덱스 필드를 없애버려서 해결하는 방법이 있긴함. 근데 이건 쫌..

더블리 링크드 리스트로 구현

atIndex, indexOf(p) : O(n)

atIndex : 인덱스에 해당하는 실제 position 을 찾아가서 데이터에 access 하라는 것.

  • 그러나 링크드 리스트는 인덱스가 객체에 없어서 맨 처음 begin()부터 시작해서 for문을 조져서 따라가서(=O(n)) 도착후 해당 방에 대한 시퀀스의 데이터를 조회(=O(1))해야함.

indexOf(p) : 실제 주소값을 준것.

  • 해당 객체에서 부터 시작해서 역방향으로 맨앞 head에 도달할때 까지 카운팅해서 몇번 카운팅 됐는지를 리턴

시간 복잡도 정리

  • 환형 배열 : insert(p,e), erase(p) 는 O(n). 이를 제외한 모든 연산 O(1)
  • 더블리 링크드 리스트 : atIndex, indexOf(p)는 O(n). 나머지 연산 모두 O(1)

profile
msung99
https://haon.blog
이전 포스트

[JAVA] 클래스

다음 포스트

트리의 기본속성들

0개의 댓글