자료구조-선형 자료 구조 (1)

배열의 개념과 활용

배열(Array)

• 많은 수의 데이터를 다룰 때 사용하는 자료구조
• 각 데이터를 인덱스와 1:1 대응하도록 구성
• 데이터가 메모리 상에 연속적으로 저장됨

배열의 특징

• 크기(Element의 개수)가 정해져 있음
• 자료구조에 기능(메소드)이 포함되어 있지 않음
• 자료가 메모리상에 빈틈 없이 연속적으로 위치해 있음
• 인덱스를 활용하여 자료에 빠르게 접근 가능
  -> "임의 접근"(random access)

배열의 장점

• 인덱스를 이용하여 데이터에 빠르게 접근 가능
  

배열의 단점

• 배열의 길이는 생성 시 정해져, 변경할 수 없음: 가변 길이 배열은 배열의 크기를 변경할 때마다 새 배열을 만듬
• Element를 제거할 경우, 배열에 빈 틈이 생김
  -> 기존 element의 인덱슬르 유지하기 위해 빈 틈을 유지
  -> 실제로는 element의 삭제가 불가능

Python과 배열

• Python의 리스트는 배열과는 다르며, 고수준의 기능을 포함
• Python에서는 배열과 유사한 자료구조로 array가 제공
  -> 리스트와 달리 특정 자료형 만을 허용
  -> 배열과 같이 메모리상에 연속적으로 배치되는 것을 보장

import array

arr = array.array('b', [10, 40, 22, -4, 9])
print(arr)

• Python array의 자료형 타입 코드
  

배열 리스트(Array List)

리스트(List)

• 순서가 있는 자료를 다루는 추상 자료형
• 추상 자료형이기 때문에, 구현 방법이 명시되어 있지 않음
• 대표적인 리스트를 구현한 자료구조: 배열 리스트, 연결 리스트

리스트의 연산자

• 비어있는 리스트를 생성하는 연산자(__init__())
  

• 리스트가 비어있는지 확인하는 연산자(is_empty())

• 리스트의 앞에 개체를 삽입하는 연산자(prepend())
  

• 리스트의 뒤에 개체를 삽입하는 연산자(append())
  

• 리스트의 첫 머리(head)를 결정하는 연산자(set_head())
  

• 주어진 인덱스에 접근하는 연산자(access(), get())
  

• 주어진 인덱스에 삽입하는 연산자(insert())
  

• 주어진 인덱스의 요소를 제거하는 연산자(remove())
  

배열 리스트(Array list)

• 내부적으로 배열을 이용하여 구현하는 리스트
• 리스트 추상자료형에서 요구하는 연산자를 배열을 활용하여 구현
• 배열의 장점인 임의 접근(random access)가 핵심

Python과 리스트

• Python에는 잘 구현된 리스트 자료형이 있음
• 모든 자료형을 허용하는, 매우 유연한 자료구조
• 지능형 리스트와 Pre-allocation 기법을 이용해 고성능으로 사용가능

배열/리스트 문제 풀이

1) 리스트 arr의 모든 자료에 대해서, 짝수 데이터들의 평균과 홀수 데이터들의 평균을 각각 계산하시오. 출력은 2개의 출력을 리스트로 묶어 출력하시오.

def solution(arr):
    even_arr = arr[1::2]
    odd_arr = arr[::2]
    return [sum(even_arr) / len(even_arr),
            sum(odd_arr) / len(odd_arr)]


if __name__ == '__main__':
    arr = [1, 3, 5, 7, 9, 2, 5, 1, 4]
    sol = solution(arr)
    print(sol)

2) 리스트의 자료 순서를 거꾸로 변경하시오. 추가 리스트를 생성하지 말고, 주어진 리스트에서 in-place로 하시오.

def solution(arr):
    N = len(arr)
    for i in range(N // 2):
        arr[N-i-1], arr[i] = arr[i], arr[N-i-1]
    return arr


if __name__ == '__main__':
    arr = [1, 3, 5, 7, 9, 5]
    sol = solution(arr)
    print(sol)

3) 리스트 arr에 존재하는 모든 피크 값을 출력하시오. 단, 피크 인덱스란 'arr[i-1] < arr[i], arr[i+1] < arr[i]' 를 동시에 만족하는 인덱스 i를 말하며, 피크 값은 이 떄 arr[i]를 말한다.

def solution(arr):
    res = []
    for i in range(1, len(arr)-1):
        if arr[i-1] < arr[i] and arr[i+1] < arr[i]:
            res.append(arr[i])
    return res


if __name__ == '__main__':
    arr = [3, 1, 2, 6, 2, 2, 5, 1, 9, 10, 1, 11]
    sol = solution(arr)
    print(sol)

4) 이차원 리스트 arr를 시계방향으로 90도 회전시킨 결과를 출력하시오.

def solution(arr):
    N = len(arr)
    M = len(arr[0])
    
    res = [[0 for _ in range(N)] for _ in range(M)]
    for i in range(N):
        for j in range(M):
            res[j][N-i-1] = arr[i][j]
    return res


if __name__ == '__main__':
    arr = [[ 1,  2,  3,  4,  5],
           [ 6,  7,  8,  9, 10],
           [11, 12, 13, 14, 15]]
    sol = solution(arr)
    print(sol)

연결 리스트 이론

연결 리스트(Linked list)

• 리스트를 구현한 자료구조로, 자료를 연결하여 관리하는 자료구조
• 자료의 순서는 정해져 있으나 메모리에서의 연속성은 보장하지 않음

연결 리스트의 장점

• 자료가 차지할 메모리를 미리 할당할 필요가 없음
• 자료의 추가, 제거가 용이함

연결 리스트의 단점

• 자료 간의 연결을 위한 추가 메모리 필요
• 원하는 인덱스의 자료를 찾는 접근 속도가 느림, 임의 접근(random access)이 불가능함
• 배열 리스트에 비해 구현이 상대적으로 복잡함

연결 리스트의 구조

• 단방향 연결 리스트: 자료의 값과 연결 정보를 가진 노드(node)로 구성
  

• 양방향 연결 리스트: 양방향으로 노드를 연결하는 이중 연결 구조
  

연결 리스트의 연산자

• 비어있는 리스트를 생성하는 생성자 (__init__())
  

• 리스트가 비어있는지 확인하는 연산자 (is_empty())

• 리스트의 앞에 개체를 삽입하는 연산자 (prepend())
  

• 리스트의 뒤에 개체를 삽입하는 연산자 (append())
  

• 리스트의 첫 머리를 결정하는 연산자 (set_head())
  

• 주어진 인덱스에 접근하는 연산자 (access(), get())
  

• 주어진 인덱스에 삽입하는 연산자 (insert())
  

• 주어진 인덱스의 개체를 제거하는 연산자 (remove())
  

연결 리스트 구현

class Node:
    def __init__(self, value, next):
        self.value = value
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None
    
    def is_empty(self):
        return self.head is None

    def prepend(self, value):
        # 1. 일반적인 경우에 잘 동작 하는가?
        # 2. 처음에 연결리스트가 비어있을 떄 잘 동작 하는가?
        node = Node(value, self.head)
        self.head = node

    def append(self, value):
        # 1. 일반적인 경우에 잘 동작 하는가?        
        curr = self.head

        if curr is None:
            # 2. 처음에 연결리스트가 비어있을 떄 잘 동작 하는가?
            self.head = Node(value, None)
            return

        while curr.next is not None:
            curr = curr.next
        node = Node(value, None)
        curr.next = node

    def set_head(self, index):
        # 1. 일반적인 경우에 잘 동작 하는가?
        curr = self.head
        for _ in range(index):
            # 2. index > N
            if curr is None:
                return
            curr = curr.next
        # 3. index == N
        if curr is None:
            return
        self.head = curr

    def access(self, index):
        # 1. 일반적인 경우에 잘 동작 하는가?
        curr = self.head
        for _ in range(index):
            # 2. index > N
            if curr is None:
                return None
            curr = curr.next
        # 3. index == N
        if curr is None:
            return None
        return curr.value

    def insert(self, index, value):
        # 2. 0번 인덱스에 삽입하는 경우
        if index == 0:
            self.prepend(value)
            return

        # 1. 일반적인 경우
        curr = self.head
        prev = None
        for _ in range(index):
            if curr is None:
                return
            prev = curr
            curr = curr.next
        node = Node(value, curr)
        prev.next = node

    def remove(self, index):
        # 3. 비어있는 연결리스트에 적용하는 경우
        if self.head is None:
            return

        # 2. index = 0인 경우
        if index == 0:
            self.head = self.head.next
            return

        # 1. 일반적인 경우
        curr = self.head
        prev = None
        for _ in range(index):
            if curr is None:
                return
            prev = curr
            curr = curr.next
        
        # 4. index == N인 경우
        if curr is None:
            return

        prev.next = curr.next

    def print(self):
        curr = self.head
        while curr is not None:
            print(curr.value, end=' ')
            curr = curr.next
        print()



if __name__ == '__main__':
    my_list = LinkedList()
    my_list.print()

    for i in range(10):
        my_list.append(i + 1)

    my_list.print()

    for i in range(10):
        my_list.prepend(i + 1)

    my_list.print()

    value = my_list.access(3)
    print('my_list.access(3) = ' + str(value))

    my_list.insert(8, 128)
    my_list.print()

    my_list.remove(4)
    my_list.print()

    my_list.set_head(10)
    my_list.print()

이 글은 제로베이스 데이터 취업 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다