C19 이진 탐색 트리 처음에 트리를 소개하며 조직도이야기를 했듯이, 트리라는 자료구조는 어떤 자료를 찾는데 이점을 갖는 구조입니다. 하지만 트리의 높이가 높아지면 탐색하는데 오래걸리거나, 위치를 안다고 해도 도달하는데 연산이 필요합니다. 그래서 우리는 트리를 특정 기준으로 나누어서 만들려고 합니다. 이것이 이진 탐색 트리입니다. 1. 이진 탐색 트리 이진 탐색 트리는 트리를 실제로 사용하기 위해 정의한 구조입니다. 이때 특정 기준에 따라서 트리 노드를 정렬하는데 보통 노드의 원소 크기를 기준으로 정렬합니다. 이때 노드의 원소를 우리는 키(key)라고 부르고, 이 값에 따라 탐색 등의 연산을 실행하게 됩니다. 우리는 종종 업앤 다운 게임을 합니다. 특정 숫자를 부르고 이 숫자보다 특정 숫자가 크면 업, 작으면 다운이라고 말하죠.. 2021. 9. 30. 이진 트리 구현 두개의 포스트에 걸쳐서 이진 트리를 설명했으니 드디어 구현에 들어가볼 차례입니다. 1. 배열로 이진 트리 구현하기? 트리도 배열을 이용해서 구현할 수는 있습니다. 그림처럼 노드에 번호를 부여하고 배열의 인덱스와 노드 번호를 일치시켜 데이터를 저장하죠. 다시 말하자면 배열의 크기를 (노드의 수+1) 만큼 잡고 인덱스 0번을 제외한 나머지 번호를 이용해서 구현합니다. 하지만 크기 가변이 힘들고, 위와 같은 그림의 완전 이진 트리가 아닌경우에, 비는 인덱스가 생긴다는 등의 문제로 인해서 일반적으로 트리를 배열로 구현하지는 않습니다. 물론 이진 트리 마지막에 소개드릴 '히프'라는 자료구조가 있는데, 이 구조에서 배열을 이용하게 됩니다. 2. 연결 리스트로 이진 트리 구현하기 노드 특히 양방향 노드를 이용하면 이.. 2021. 9. 24. 데크 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. 이중 연결 리스트 Doubly Linked List 이번에 소개할 자료구조는 이중 연결 리스트 입니다. 1. 이중 연결 리스트 이중 연결 리스트 혹은 양방향 연결 리스트라고 불리우는 이 자료도 연결 리스트의 일종입니다. 지난번 원형 연결 리스트와 마찬가지로 한 가지 개념만 추가하면 되는데요. 바로 링크필드가 양옆에 있다는 점입니다. 지난번 까지 알아본 리스트의 노드들은 다음과 같이 구성되어있었습니다. 하지만 양방향 링크 필드의 노드는 다음과 같이 구성됩니다. 편의상 앞의 링크 필드는 '왼쪽 링크 필드', 뒤의 링크 필드는 '오른쪽 링크 필드'라고 명명하고 넘어가겠습니다. 왼쪽 링크 필드는 현재 노드의 이전 노드를 가리키고, 오른쪽 링크 필드는 현재 노드의 다음 노드를 가리킵니다. 이렇게 한 노드에서 양방향의 링크를 가리킨다 해서 양방향, 선모양으로 펼쳐놓.. 2021. 9. 10. 이전 1 2 3 4 다음 300x250
