[Algorithm] 자료구조

 

 

 

자료구조와 알고리즘

 

Data Structor 메모리 담당

Algorithm 속도 담당

 

어떻게 하면 최저의 비용으로 최고의 성과를 낼까

 

메모리가 감소하면 속도도 줄어듦 (비용감소)

메모리가 증가하면 속도도 빨라짐 (비용증가)

 

 

 

 

자료구조

데이터를 효율적으로 저장 · 조직화 · 관리하기 위한 방법

>> 알고리즘을 도와주는 요소

자료를 기억장치의 공간 내에 저장하는 방법 + 자료간의 관계, 처리 방법 등을 연구 · 분석한 것

 

선형 구조	배열, 스택 · 큐, 연결리스트, 데크
비선형 구조	트리, 그래프

 

 

목차)

1. 배열(Array)

2. 스택(Stack) · 큐(Queue)

3. 연결리스트(Linked List)

4. 트리(Tree)

 

 

 

1. 배열 (Array)

동일한 유형의 요소들의 데이터들이 연속적인 메모리 공간에 저장되는 자료구조

 

연속적인 메모리 공간

배열의 데이터들이 메모리에서 연속적으로 할당되기 때문에

인덱스를 통해 데이터에 접근할 수 있음

 

고정된 크기

배열은 생성할 때 크기가 결정되며 일단 생성된 배열의 크기는 변경할 수 없음

 

인덱스 기반 접근

시작 요소가 0으로 시작됨

덕분에 빠른 읽기와 쓰기가 가능

 

동일한 유형의 데이터 저장

 

장 점	빠른 속도, 연속적 할당으로 캐시 지역성(Cache Locality) 성능 향상(모여있으니까), 간단, 직관적
단 점	크기 제약, 삭제 삽입 불가, 메모리 낭비

 

 

 

2. 스택 (Stack) · 큐 (Queue)

 

# 스택

 

후입선출(LIFO)

마지막에 삽입된 요소가 가장 먼저 제거됨

 

연산자

push(): 스택의 맨 위에 요소 추가

pop(): 스택의 맨 위의 요소를 제거하고 반환

peak/top() : 스택의 맨 위에 요소를 조회

 

사용처

- 함수 호출과 복귀

함수 호출 시 호출된 함수의 정보(지역변수, 매개변수 등)을 스택에 저장하고

함수가 완료되면 역순으로 복귀

- 괄호 검사

괄호 짝이 맞는지 확인하기 위해

여는 괄호가 나오면 stack에 push하고(닫는 괄호가 나올 때 까지)

짝을 이루면 pop을 함

- 뒤집기

문자열, 배열 등 스택에 넣고 순서대로 꺼내면 역순이 됨

 

class Stack:
    def __init__(self):
        self.stack = []
        
    def is_empty(self):
        return len(self.stack) == 0
    
    def push(self, item):
        self.stack.append(item)
        
    def pop(self):
        if self.is_empty():
            return "Empty"
        else:
            return self.stack.pop()
            
    def peek(self): #최상위 요소 꺼내기
        if self.is_empty():
            return "Empty"
        else:
            return self.stack[-1]
        
        
stack = Stack()

stack.push(10)
stack.push(20)
stack.push(30)

print(stack.pop()) #30
print(stack.pop()) #20
print(stack.pop()) #10

print(stack.is_empty) #True

 

▼ 문제 ▼

>> 괄호 짝 맞추기

>> (), {}, [] 짝이 잘 맞춰져 있는지 확인해보자

>> () : T // (){}[] : T  {] :F  (}[ : F

def couple(a):
    stack = Stack()
    open = "({["
    close = "]})"
    
    for char in a:
        if char in open:
            stack.push(char)
        elif char in close:
            if len(stack) == 0:
                return False
            else:
                top = stack.pop()
                if (char == ')' and top != '(') or (char == ']' and top != '[') or (char == '}' and top != '{[}') :
                    return False
    return len(stack) == 0
        

print(couple('[]')) #T
print(couple('[}](')) #F

 

 

# 큐

 

선입선출(FIFO)

가장 먼저 삽입된 요소가 가장 먼저 제거됨

>> 식당 대기줄

 

연산자

Enqueue() : 큐의 뒤쪽에 요소 추가

Dequeue() : 큐의 앞쪽의 요소를 제거하고 반환

Front/Peak() : 큐의 앞쪽에서 요소를 조회

 

사용처

- 작업 대기열(Task Queue)

여러 작업들이 들어올 때 순서대로 처리하기 위해 사용

- 너비 우선 탐색(BFS Breadth-First-Search)

그래프나 트리 탐색 시 BFS에서 인접한 정점들을 방문한 순서대로 처리

>> 미로찾기

 

class Queue:
    def __init__(self):
        self.queue = []
        
    def __len__(self):
        return len(self.queue)
    
    def is_empty(self):
        return len(self.queue) == 0
    
    def enqueue(self, item):
        self.queue.append(item)
        
    def dequeue(self):
        if self.is_empty():
            return "Empty"
        else:
            return self.queue.pop(0)
        
    def peak(self):
        if self.is_empty():
            return "Empty"
        else:
            return self.queue[0]
        
queue = Queue()

queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)

print(queue.peak()) #10

print(queue.dequeue()) #10
print(queue.dequeue()) #20
print(queue.dequeue()) #30

print(queue.is_empty()) #True

 

▼ 문제 ▼

>> 숫자 뒤집기

def reverse(x) :
    queue = Queue()

    while x > 0:
       digit = x % 10
       queue.enqueue(digit)
       x //= 10
    
    number = 0
    
    
    while queue:
        digit = queue.dequeue()
        number = number * 10 + digit
    
    return number

print(reverse(12345))
print(reverse(987654321))

 

 

 

 

 

 

3. 연결리스트 (Linked List)

노드들이 포인터로 서로 연결되어 있는 자료구조

>> 노드: 데이터와 다음 노드를 가르키는 포인터 (집주소)

 

- 삽입(insertion)

- 삭제(deletion)

 

 

☞  단일 연결 리스트 (Single Linked List)

각 노드는 데이터 필드와 다음 노드를 가르키는 포인터 필드로 구성됨

마지막 노드의 포인터 필드값은 보통 NULL이며 이는 리스트의 끝을 나타냄

 

기본구조

 

장 점	삽입 · 삭제가 효율적이고 간단함(앞 · 뒤 노드만 수정하면 되기 때문에) 동적 크기 조정 가능
단 점	특정 위치에 직접 접근하기 위해서는 처음부터 순차적으로 탐색해야 함(탐색시간 증가)

 

예시)

class Node {

    int data;

    node next;

}

 

insert(java)

delete(java)

delete 과정에서

Node prevNode = null, currentNode = head;

>> 노드는 두개만 쓰임 ▼

전에꺼 현재꺼 다음꺼

다음꺼가 필요 없게 됨

예시

 

---

 

☞  이중 연결 리스트 (Doubly Linked List)

각 노드는 데이터 필드와 이전 노드를 가르키는 포인터필드, 다음 노드를 가르키는 포인터필드로 구성됨

첫번째 요소와 마지막 요소에도 접근 가능

 

예를 들면 이렇게 생김

ㅇㅖ시

삽입과 삭제 예시

 

 

장 점	양방향으로 탐색이 가능하여 특정 위치에서의 삽입과 삭제가 단일연결리스트보다 효율적 역방향 탐색 및 반대방향에서의 삽입 · 삭제가 가능
단 점	이전(prev) 포인터를 유지해야하므로 추가 메모리 공간을 사용함

 

예시)

class Node {

    int data;

    Node prev;

    Node next;

}

 

 

 

 

 

 

4. 트리(Tree)

정점과 선분을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태

 

비선형 계층구조를 표현하는 자료구조

노드들의 집합

하나의 루트노드와 0개 이상의 부분 트리(subtree)로 구성

또한 각 부분 트리는 또한 0개 이상의 부분 트리(subtree)로 구성

또한 · · ·

 

 

☞  이진 트리 Binary Tree

최대 두개의 자식을 가질 수 있는 특별한 형태의 트리

각각의 노드는 최대 2개의 자식 노드를 가지며, 왼쪽 자식과 오른쪽 자식으로 부름

 

▼ 이렇게

 

 

 

 

1) 정 이진 트리(Full Binary Tree)

모든 레벨(깊이)에서 노드가 꽉찬 이진트리

모든 부분 트리들이 2개의 자식 노드를 가지고 있으며 같은 깊이에 존재함

 

 

2) 완전 이진 트리(Complete Binary Tree)

마지막 레벨을 제외하면 모든 노드가 완전히 채워져 있으며,

마지막 단계에서도 왼쪽부터 순서대로 채워져있는 이진트리

 

 

3) 편향 이진 트리 (Skewed Binary Tree)

각각의 내부 노드들이 하나만 있는 경우

왼쪽으로 치우쳐지면 Left S, 오른쪽으로 치우쳐지면 Right S 라고 부름

 

 

4) 이진 탐색 트리 (Binary Search Tree)

각 노드의 왼쪽 서브트리에 있는 모든 노드의 값이 해당 노드의 값보다 작고

오른쪽 서브트리에 있는 모든 노드의 값이 해당 노드의 값보다 큰 구조로 설계됨

>> 검색, 삽입, 삭제 등의 연산을 평균적으로 O(log n) 시간 복잡도에서 처리할 수 있음

검색 (Search) 

루트에서 시작해서 찾으려는 값이 현재 노드와 같으면 해당 노드값을 반환함

찾으려는 값이 현재 노드값보다 작으면 왼쪽으로, 크면 오른쪽으로 이동

 

삽입 (Insertion)

루트에서 시작해서 삽입하려는 값이 현재 값보다 작으면 왼쪽, 크면 오른쪽으로 이동

 

삭제 (Deletion)

삭제할 노드가

- 리프노드(맨끝단)인 경우, 단순 노드 삭제

- 자식노드를 하나 가지고 있을 경우, 그 위치에 자식노드를 올림

- 자식노드를 두개 가지고 있을 경우, 보통은 오른쪽 중 최소값을 찾아서 그 위치로 올림

>> 리프 노드(Leaf Node, 잎노드) = 단말 노드(Terminal Node) = 자식이 없는 노드 = degree가 0인 노드

 

 

 

 

 

 

 

 

 

그 외

 

1. 왼쪽 ↔ 오른쪽  서로 바꿔줄 수 있어야 함

 

2. 이러캐