computer_study

[Python, C++] 알고리즘을 위한 대표적인(기본적인) 자료구조 본문

알고리즘/개념정리

[Python, C++] 알고리즘을 위한 대표적인(기본적인) 자료구조

knowable 2020. 7. 14. 15:45

1.  배열(array)

(출처 : ahribori.  https://ahribori.com/article/591a5824c686bd0d48e95f47)

 

  • array 장단점 (기술 대비)

            - 장점 : 빠른 접근이 가능하다.(처음 주소를 알면 다음 애들을 순차적으로 접근가능)


            - 단점 : 1.  연관된 데이터 추가나 삭제가 어렵다. (ex, 추가 시에는 공간을 새로 생성, 삭제 시에는 빈공간이 생김.) 
                          2.  미리 최대 길이를 지정해야된다.

 

 

 

  • 파이썬에서 배열 : list를 사용한다.

     1.  리스트에 요소 추가 ( append )

x = [1, 2, 3]
x.append(4)
# x = [1, 2, 3, 4]

x.append([5,6])
# x = [1, 2, 3, 4, [5, 6]]

 

     2.  리스트에 요소 삭제 ( del )

x = [1, 2, 3]
del x[1]

# x = [1, 3]

 

     3.  리스트 정렬 ( sort )

x = [1, 4, 2, 3]
x.sort()
# x = [1, 2, 3, 4]

x = ['a', 'c', 'b']
x.sort()
# x = ['a', 'b', 'c']

 

 

 

 

 

  • c++에서 배열

      c언어와 같이 int arr[num] , double arr[num] 식으로 사용한다.

 

     1.  배열의 초기화

int arr[3] = {}; // 모두 0으로 초기화
int arr[3] = {1, 2, 3}; // 0번 index부터 1,2,3으로 초기화
int arr[] = {1, 2, 3}; // 초기화를 하면 []안은 생략가능

 

     2.  enum을 사용한 배열

// 숫자로 표기하면, 어느 학생이 어느 점수를 받았는지 헷갈리므로 enum사용.
enum StudentNames {
    KENNY,       // 0 
    KYLE,        // 1 
    STAN,        // 2 
    MAX_STUDENTS // 3
};

int main() { 
    int scores[MAX_STUDENTS];  // allocate 3
    integers scores[STAN] = 76;
    return 0;
}

 

     3.  배열 parameter

// value를 parameter로 넘기면 복사본이 넘겨저 값이 변하지않지만, 
// array를 parameter로 넘기면 실제 array가 넘겨져 값이 변한다.

#include <iostream>
using namespace std;
 
void passValue(int value){ // value는 인수의 복사본이다. 
    value = 99;            // 여기에서 값을 변경해도 인수의 값은 변경되지 않는다.
} 

void passArray(int prime[3]){  // prime은 실제 배열이다. 
    prime[0] = 11;             // 여기에서 요소의 값을 변경하면 실제 배열의 요소의 값이 바뀐다.
    prime[1] = 7;
    prime[2] = 5;
} 

int main() { 
    int value = 1; 
    
    cout << "before passValue: " << value << "\n";
    passValue(value); 
    cout << "after passValue: " << value << "\n";
    
    int prime[3] = { 2, 3, 5 }; 
    cout << "before passArray: " << prime[0] << " " << prime[1] << " " << prime[2] << "\n";
    passArray(prime); 
    cout << "after passArray: " << prime[0] << " " << prime[1] << " " << prime[2] << "\n"; 
	
    return 0;
} 
/*
before passValue: 1
after passValue: 1
before passArray: 2 3 5
after passArray: 11 7 5
*/

 

추가적인 배열에 관한 정보는 ' https://boycoding.tistory.com/194?category=1009770 [소년코딩] ' 에서 확인할 수 있다..

 

 

c++에선 배열 대신 자동으로 메모리가 할당되는 vector 컨테이너를 사용할 수 있다.

blockdmask.tistory.com/70 에서 개념 및 사용법을 확인할 수 있다.

 

 

2.  큐(queue)

( 출처 : 나무위키, https://namu.wiki/w/큐(자료구조) )

 

  • 파이썬에서 queue 라이브러리

 

        1.  일반적인 fifo 

import queue 

data_queue = queue.Queue() # 생성
data_queue.put("test")     # enqueue string
data_queue.put(1)          # enqueue 숫자 
data_queue.qsize()         # queue의 크기
data_queue.get()           # dequeue (fifo에 따라 선택된다.)

 

        2.  Lifo 라이브러리(Last-in, First-out) 

import queue 
data_queue = queue.LifoQueue() # 생성
# size, put, get 똑같이

 

        3.  priorityQueue만들기  ( 번호가 낮은것이 우선순위가 높다. )

import queue 
data_queue = queue.priorityQueue() # 생성
data_queue.put((10,"test"))        # (우선순위, data)
data_queue.put((5,1))              
# get, size는 똑같다. 
# get시 우선순위가 높은게 나온다.

 

 

 

 

 

 

  • c++에서 queue

        1.   <queue> 헤더파일을 include하여 사용할 수 있다.

        2.   fifo 방식으로 동작한다.

        3.   list와 dequeue 에 붙여서 사용가능하며 vector container와는 함께 사용할 수 없다.

              (vector는 앞에서 빼는 동작이 없으므로)

#include <iostream>
#include <queue>

using namespace std;

int main(){

    queue<int> q;                            // queue 생성
    cout << "size : " << q.size() << endl;   // queue의 size
    cout << "empty : " << q.empty() << endl; // 비어있으면(size가 0이면) true 
    
    q.push(1);                               // 원소를 queue의 마지막에 넣는다.
    q.push(2);
    q.push(3);
    
    cout << "front : " << q.front() << endl; // 첫번째 원소 (pop시 나올 원소)
    cout << "back : " << q.back() << endl;   // 마지막 원소 (방금 push한 원소)
    
    q.pop();				     // q.front()에 있던 원소가 나온다.

    return 0;
}

( 출처 : blockdmask.tistory.com/101 )

 

 

3.  스택(stack)

( 출처 : 위키백과, https://ko.wikipedia.org/wiki/스택)

 

스택은 단순하고 빠른 성능을 위해 사용도므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다.

ex) 파이썬은 재귀함수가 1000번까지 가능하다.

 

 

  • stack 장단점 (기술 대비)

            - 장점 : 구조가 단순해서 구현이 쉽고 데이터 저장/읽기 속도가 빠르다

 

            - 단점 (일반적인 스택 구현시) :  데이터의 최대 개수를 미리 정해야 하기 때문에 저장공간의 낭비가 발생할 수 있다.                                

        (일반적인 stack의 단점이고, 만약 linked list를 이용하여 stack을 구현한다면 데이터의 최대 개수를 미리 정하지 않아도 된다.)

   

 

 

  • 파이썬에서 스택 

      1.  리스트에서 제공하는 메서드로 스택. append(push), pop 사용

data_stack = list()
data_stack.append(1) // push
data_stack.append(2)
data_stack.pop()     // pop

 

      2.  pop, push 구현하기

stack_list = list()

def push(data):
	stack_list.append(data)

def pop():
	data = stack_list[-1] // stack_list배열의 마지막 표현법
	del stack_list[-1]    // 값 삭제
	return data

 

 

 

 

 

 

 

  • c++에서 stack

        1.   <stack> 헤더파일을 include하여 사용할 수 있다.

        2.   LIFO ( Last In First Out ) 방식으로 동작한다.

 

#include <iostream>
#include <stack>

using namespace std;

int main(){

    stack<int> s;                             // stack 생성

    s.push(3);                                // top에 원소 추가
    s.push(2);
    s.push(1);

    cout << "top : " << s.top() << endl;      // 현재 top 가져오기 

    s.pop();                                  // top에 있는 원소를 뺀다. 1이 삭제
    s.pop();                                  // 2가 삭제

    cout << "size : " << s.size() << endl;    // 현재 stack의 size를 알 수 있다.

    cout << "empty : " << s.empty() << endl;  // stack이 비어있다면 true

    return 0;
}

 

 

 

 

4.  링크드리스트(linked-list)

 

( 출처 : 위키백과, https://ko.wikipedia.org/wiki/연결_리스트)

 

  • linked list 장단점(기술 대비)

         - 장점 : 미리 데이터 공간을 할당하지 않아도 된다. (cf, 배열은 미리 공간을 할당해야된다.)

 

         - 단점 : 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지않다

                       연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다(head부터 순서대로 탐색해야되므로)

                       중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요하다

 

 

 

  • 파이썬으로 linked list 만들기

 

+) python에서 class 사용하는 이유

python은 객체지향 문법으로, class를 사용하여 변수나 함수를 재 선언하여 발생하는 오류를 해결할 수 있다.

(참고 : server-talk.tistory.com/220 )

 

 

 

      1.  node 구현 

class Node:
    def __init__(self, data): # 이 class를 이용해 객체를 만들 때 마다 node가 하나씩 생성된다.
        self.data = data
        self.next = None

인자로 data만을 받는다.

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

위 구현과 다른방법(class 문법 사용해서 의미있게)

-> 인자로 data와 next 주소를 받게한다. (next가 none이면 그대로 none으로 들어간다)

 

 

    2.  node와 node 연결하기(포인터 활용)

node1 = Node(1)    # node 생성
node2 = Node(2)
node1.next = node2 # node1다음에 node2연결
head = node1       # 처음 node 저장

 

 

      3.  링크드 리스트로 데이터 추가하기 (마지막에 추가)

 

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

    def add(data):
        node = head
        while node next:       # 마지막 node를 찾는다
            node = node.next
        node.next = Node(data) # 마지막에 새로운 node생성

 

      4.  linked list로 데이터 추가(중간에 추가) (ex. 1,2,3,4,5 중 1, 2 사이에 1.5를 추가하고 싶다면)

( 출처 : 코딩도장, https://dojang.io/mod/page/view.php?id=646)

node3 = Node(1.5)
node = head
search = True
while search:          # 1을 찾아서 그 다음에 추가하기 위함
    if node.data == 1:
        search = False
    else: 
    node = node.next
        
node_next = node.next
node.next = node3
node3.next = node_next  # 가르키는 주소값을 바꾼다.

 

      5.  delete 

def delete(self, data):
    if self.head == '':
        print("there's no head")
        return
    if self.head.data == data:     # head 삭제
        temp = self.head
        self.head = self.head.next
        del temp
    else:                          # 삭제 할 data가 head가 아닌경우 (마지막노드 학제 & 중간노드 삭제)
        node = self.head
        
    while node.next:
        if node.next.data == data: # 삭제 할 data라면
            temp = node.next
            node.next = node.next.next
            del temp
            return
        else:
            node = node.next

 

 

      6.  파이썬 객체지향 프로그래밍으로 linked list 구현하기

 

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

class NodeMgmt:  # management
    def __init__(self,data):               # head가 가진 data까지 받아서 head로 지정해준다.
        self.head = Node(data)

    def add(self, data):                   # 무조건 마지막에 추가하는 경우
        if self.head == '':                # head가 비어있다면
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)

    def desc(self):                        # linked list 순회하며 출력
        node = self.head
        while node:
            print(node.data)
            node= node.next

    def delete(self, data):                # 삭제
        if self.head == '':
            print("there's no head")
            return

        if self.head.data == data:         # head 삭제
            temp = self.head
            self.head = self.head.next
            del temp

        else:                              # 삭제 할 data가 head가 아닌경우 (마지막노드 학제 & 중간노드 삭제)
            node = self.head
            while node.next: 
                if node.next.data == data: # 삭제 할 data라면
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    return
                else:
                    node = node.next

def main(): # 사용법
    linkedlist1 = NodeMgmt(0)               # linked list 생성
    for data in range(1,10)
        linkedlist1.add(data)
    linkedlist1.desc().                     # -> 0~9 까지 출력된다.
    linkedlist1.delete(9)                   # 9가 삭제된다
    
if __name__ == "__main__":
    main()

 

 

      7.  double linked list

 

( 출처 : 위키피디아, https://en.wikipedia.org/wiki/Doubly_linked_list)

              양쪽으로 연결이 되어있어, 양쪽으로 탐색이 가능하다.

 

class Node:
    def __init__(self, data, prev=None, next=None): 
        self.data = data
        self.prev = prev
        self.next = next


class NodeMgmt: # management

    def __init__(self,data): 
        self.head = Node(data)
        self.tail = self.head         # 뒤에서부터도 찾을 수 있게하기위함. (처음엔 head == tail)


    def insert(self, data):
        if self.head == None:         # head가 비어있다면
            self.head = Node(data)
            self.tail = self.head
        else:                         # 마지막에 추가 후 tail 바꿔주기
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)            
            node.next = new
            new.prev = node           # 마지막 추가된 new가 앞부분인 node를 가르키도록 한다.
            self.tail = new           # 새롭게 만들어진 new가 마지막 node이므로, 이를 tail로 저장해준다.


    def desc(self):                   # linked list 순회하며 출력
        node = self.head
        while node:
            print(node.data)
            node= node.next


    def search_from_head(self, data): # head 부터 검색
        if self.head == None:         # head가 없으면
            return False
        node = self.head
        while node:                   # head부터 해당 data찾기
            if node.data == data:
                return node           # 찾으면 그 node return
            else:
                node = node.next
        return False                  # 못찾으면 False return


    def search_from_tail(self, data): # tail 부터 검색
        if self.tail == None:         # tail이 없으면
            return False
        node = self.tail
        while node:                   # tail부터 해당 data찾기
            if node.data == data:
                return node           # 찾으면 그 node return
            else:
                node = node.prev
        return False                  # 못찾으면 False return


    def insert_before(self, new_data, target_data):  # before_data앞에 data를 추가한다
        if self.head == None:                        # head가 없으면 data를 추가로 생성
            self.head = Node(new_data)               # 특정 data앞에 추가한다는 조건 무시하게된다.
            return True
        else:
            node = self.tail                         # 현재 node.data가 입력받은 before_data와 
            while node.data != target_data:          # 같을 때 까지 앞으로 이동
                node = node.prev
                if node == None:                     # 해당 node가 없으면
                    return False
                    
            # 위 과정은 search_from_tail로 대체 가능.
            # node = search_from_tail(target_data)
                    
                    
                    
            # 이쪽으로 빠지면 현재 node.data가 target_data
            new = Node(new_data)
            before_new = node.prev
            before_new.next = new
            new.prev = before_new
            new.next = node
            node.prev = new
            return True



def __main__: # 사용법

    double_linked_list = NodeMgmt(0)                    # double linked list 생성
    for data in range(1,10):
        double_linked_list.insert(data)
    double_linked_list.insert_before( 1.5 , 2 )         # 2 앞에 1.5 넣겠다.
    node_3 = double_linked_list.search_from_tail(1.5)   # 뒤에서부터 찾기 시작하여 1.5를 찾는다

'알고리즘 > 개념정리' 카테고리의 다른 글

[python/c++] (key, value)로 변수저장하기 (dictionary, map)  (0) 2020.08.12
[c++] 문자 입력 방법 ( get line( ) )  (2) 2020.08.11
[알고리즘] counting sort (계수 정렬)  (0) 2020.08.07
Recursion  (0) 2020.07.07
'알고리즘/개념정리' Related Articles more
Comments