Programming/자료구조32 트리의 개념 Tree 이번 포스트부터 몇개의 포스트에 걸쳐 이야기할 자료구조는 '트리(Tree)'입니다. 특히 이번 포스트에서는 트리의 개요에 대해서 따로 다루고 넘어가려고합니다. 그동안 다뤘던 자료구조랑은 또 다른 이해가 필요하기 때문이죠. 1. 트리 개요 트리(Tree) 나무와 스펠링이 같습니다. 보통 우리가 생각하는 나무는 어떻게 생겼죠? 아래는 넒고 위로 갈수록 좁아지는 형태를 갖고있습니다. 이처럼 트리도 위에서 아래로 갈수록 자료가 많아지는 구조를 가지고 있습니다. 가만보면 여태까지 배운 리스트나 큐, 스택, 데크를 보면 뭔가 통 느낌이 났는데 이건 통이라고 하기 애매한 부분이 있는 것 같다고 생각이 듭니다. 왜냐하면 트리는 계층 관계를 표현하는 자료구조이기 때문입니다. 2. 트리 이해하기 트리는 비선형, 1:1이 .. 2021. 9. 19. 데크 Deque 이번에 소개할 자료구조는 데크(덱)입니다. 어떤 문서에서는 데크, 다른 문서에서는 덱이라고 하길래 저는 제가 배웠던 '데크'라는 명칭으로 소개하려고합니다. 1. 데크 데크는 새로운 자료구조 같지만 큐의 변형 자료구조 중 하나입니다. 데크의 의미는 Double Ended Queue로써 끝이 2개인 큐를 의미합니다. 기존의 큐는 아래 그림처럼 한 끝에서만 삽입, 다른 한 끝에서만 삭제가 이루어졌습니다. 하지만 데크는 양 쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다. 한 가지 착각 하지 말아야 하는 점은 연결 리스트처럼 중간 삭제는 불가능하고 스택과 큐처럼 자료구조 양 끝에서만 삽입 삭제가 이루어 진다는 점입니다. 구현 방식은 데크의 특징을 잘 생각해서 다음 두가지만 명심하고 구현하면됩니다. front.. 2021. 9. 18. 원형 큐 Circular Queue 지난 포스트에서 배열을 이용해 큐를 이동하던 중에 원소 이동의 문제로 인해 구현이 실패했었습니다. 그래서 이번엔 순차 자료구조로 그 문제를 해결할 수 있는 방법인 원형 큐를 소개하려고합니다. 1. 원형 큐 지난번에 원소 삭제에서 삭제하고 배열 내부의 원소를 하나씩 앞으로 이동하면 큐가 구현되지만 원소 이동이라는 작업이 오버헤드를 일으켜 구현도 사용도 어렵다고 했었습니다. 그래서 나온개념이 배열 내부의 원소가 아닌 front와 rear를 움직이자! 해서 등장한 자료구조가 원형 큐입니다. 이처럼 기존의 리스트같은 구조를 다음과 같이 동그랗게 말은 구조입니다. (실제로 물리적으로는 동그랗지 않습니다) 자세한 것은 구현하면서 살펴보도록 하겠습니다. 2. 원형 큐 구현 2-1. 큐 생성 큐 생성입니다. 그동안 했.. 2021. 9. 17. 큐 Queue 이번에는 스택과 비슷한 자료구조인 큐를 알아보겠습니다. 1. 큐 큐는 스택처럼 특정한 위치에서 넣고 뺄 수 있는 자료구조입니다. 스택은 입구와 출구가 같아서 나중에 들어간 자료가 먼저 나오는 후입선출 구조였다면, 큐는 입구와 출구가 따로 있어서 먼저들어간 자료가 먼저 나오는 선입선출(FIFO, First Input First Out) 자료구조 입니다. 보통 어딘가 입장할 때 우리는 줄을 섭니다. 그래서 먼저 줄을 선 사람이 먼저 입장하게됩니다. 이 줄이 큐입니다. 혹시 리그 오브 레전드 라는 게임 혹은 다른 게임에서 우리는 게임을 잡기 위해 대기 큐를 잡는다~라고 하죠? 그 큐도 이 큐입니다. 먼저 게임을 잡으려고 한사람부터 게임에 넣어주는 구조이죠. 이제 큐가 무엇인지는 감이 잡히시나요? 그림으로 설명.. 2021. 9. 16. 스택 Stack 이번에 소개할 자료구조는 스택과 큐인데 스택 따로 큐 따로 2개에 나눠서 소개하겠습니다. 그리고 그중에서 스택 부터 보도록 하겠습니다. 1. 스택 소개 스택(Stack)은 데이터를 쌓아올린듯한 자료구조입니다. 마트에 가면 '프루팁스'라고 제가 좋아하는 젤리를 팝니다. 이렇게 생긴 원통형 젤리인데요. 한쪽은 젤리를 꺼낼 수 있는 뚜껑이 있고 반대쪽은 막혀있습니다. 그래서 한쪽으로만 젤리를 넣고 꺼낼 수 있죠. 스택이 마치 이 젤리와 같은 모양의 자료 구조입니다. 스택은 원통형(물론 물리적으로 원통은 아니고 생긴게 그렇다~라는 말입니다.) 자료구조입니다. 데이터를 한쪽으로만 꺼내고 넣을수가 있습니다. 그래서 구조적으로 먼저 들어간 자료가 나중에 나오는데, 이를 후입선출, LIFO(Last In First O.. 2021. 9. 14. 이중 연결 리스트 Doubly Linked List 이번에 소개할 자료구조는 이중 연결 리스트 입니다. 1. 이중 연결 리스트 이중 연결 리스트 혹은 양방향 연결 리스트라고 불리우는 이 자료도 연결 리스트의 일종입니다. 지난번 원형 연결 리스트와 마찬가지로 한 가지 개념만 추가하면 되는데요. 바로 링크필드가 양옆에 있다는 점입니다. 지난번 까지 알아본 리스트의 노드들은 다음과 같이 구성되어있었습니다. 하지만 양방향 링크 필드의 노드는 다음과 같이 구성됩니다. 편의상 앞의 링크 필드는 '왼쪽 링크 필드', 뒤의 링크 필드는 '오른쪽 링크 필드'라고 명명하고 넘어가겠습니다. 왼쪽 링크 필드는 현재 노드의 이전 노드를 가리키고, 오른쪽 링크 필드는 현재 노드의 다음 노드를 가리킵니다. 이렇게 한 노드에서 양방향의 링크를 가리킨다 해서 양방향, 선모양으로 펼쳐놓.. 2021. 9. 10. 이전 1 2 3 4 5 6 다음 300x250
