스택, 큐, 딕셔너리의 원리와 구조를 설명할 수 있습니다. 스택 큐 딕셔너리 우리가 여태껏 배운 배열, 연결 리스트, 해시 테이블, 트라이 외에도 많은 자료 구조들이 있습니다. 또는 위의 자료 구조를 기반으로 해서 문제를 해결하는데 적합한 새로운 자료 구조를 만들 수도 있습니다. 아래와 같이 세 가지의 대표적인 자료 구조를 간단하게 알아보겠습니다. 큐 큐는 메모리 구조에서 살펴봤듯이 값이 아래로 쌓이는 구조입니다. 값을 넣고 뺄 때 ‘선입 선출’ 또는 ‘FIFO’라는 방식을 따르게 됩니다. 가장 먼저 들어온 값이 가장 먼저 나가는 것이죠. 은행에서 줄을 설 때 가장 먼저 줄을 선 사람이 가장 먼저 업무를 처리하게 되는 것과 동일합니다. 배열이나 연결 리스트를 통해 구현 가능합니다. 스택 반면 스택은 역시..

문자열의 길이가 일정한 경우 이 문자열들을 저장하고 관리하는데 최적의 자료 구조는 무엇일까요? 연결 리스트, 트리, 또는 해시 테이블이 최선의 방안이 될 수 있을까요? 이번 강의에서는 ‘트라이’라는 자료구조에 대해 알아보겠습니다. 트라이의 원리와 구조를 설명할 수 있습니다. 트라이 ‘트라이’는 기본적으로 ‘트리’ 형태의 자료 구조입니다. 트라이는 retrieval 의 줄임 말이다. 특이한 점은 각 노드가 ‘배열’로 이루어져있다는 것입니다. 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면 이 노드는 a부터 z까지의 값을 가지는 배열이 됩니다. 그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z 배열)를 가리킵니다. 아래 그림과 같이 Hermione, Harry, Hagrid 세 ..

해시 테이블의 원리와 구조를 설명할 수 있습니다. 해시 테이블 해시 함수 해시 테이블은 ‘연결 리스트의 배열’입니다. 여러 값들을 몇 개의 바구니에 나눠 담는 상황을 생각해 봅시다. 각 값들은 ‘해시 함수’라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정 됩니다. 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어집니다. 이와 같이 연결 리스트가 담긴 바구니가 여러개 있는 것이 ‘연결 리스트의 배열’, 즉 ‘해시 테이블’이 됩니다. 쉬운 예로 아래 그림과 같이 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 ‘이름의 가장 첫 글자’인 경우를 생각해 보겠습니다. 그 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳을 시작으로 ..

트리의 구조를 설명하고 활용하는 코드를 작성할 수 있습니다. 트리 루트 트리는 연결리스트를 기반으로 한 새로운 데이터 구조입니다. 연결리스트에서의 각 노드 (연결 리스트 내의 한 요소를 지칭)들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있다고 볼 수 있습니다. 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 됩니다. 아래 그림은 트리의 한 예입니다. 나무가 거꾸로 뒤집혀 있는 형태를 생각하면 됩니다. 가장 높은 층에서 트리가 시작되는 노드를 ‘루트’라고 합니다. 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 합니다. 위 그림에 묘사된 트리는 구체적으로 ‘이진 검색 트리’ 입니다. 각 노드가 구성되어 있는 ..

연결 리스트와 배열의 장단점을 설명할 수 있습니다. 연결 리스트 배열 연결 리스트의 원리를 학생들의 시연을 통해 살펴보았습니다. 배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있습니다. 하지만 이런 유동적인 구조는 그 대가가 따릅니다. 구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능합니다. 연결 리스트에 값을 추가하거나 검색하는 경우를 생각해 봅시다. 이를 위해서는 해당하는 위치까지 연결 리스트의 각 node들을 따라 이동해야 합니다. 따라서 연결 리스트의 크기가 n 일때 그 실행 시간은 O(n)이 됩니다. 배열의 경우 임의 접근이 가능하기 때문에 (정렬 되어 있는 경우) 이진 검색을 이용하면 O(log n)의 실행 시간이 소요 되는 것..

연결 리스트를 구현하고 사용할 수 있습니다. 연결 리스트 앞서 정의한 구조체를 활용해서 실제로 연결 리스트를 구현해보도록 하겠습니다. 아래 코드의 내용과 각 주석을 따라가 보세요. #include #include //연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다. typedef struct node { //node 안에서 정수형 값이 저장되는 변수를 name으로 지정합니다. int number; //다음 node의 주소를 가리키는 포인터를 *next로 지정합니다. struct node *next; } node; int main(void) { // list라는 이름의 node 포인터를 정의합니다. 연결 리스트의 가장 첫 번째 node를 가리킬 것입니다. // 이 포인터는 현재 아무 것도 가리..

연결 리스트의 정의를 설명할 수 있습니다. 연결 리스트 데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체입니다. 일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있습니다. 이번 강의에서는 데이터 구조중 하나인 연결 리스트에 대해 알아보겠습니다. 배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있습니다. 하지만 꼭 그럴 필요가 있을까요? 각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있습니다. 이를 ‘연결 리스트’라고 합니다. 아래 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장합니다. 연결 리스..

컴퓨터 안의 메모리는 마치 사물함과 같은 구조입니다. 우리가 사용하고자 하는 사물함의 개수를 한 번 정한 이후에는, 공간이 모자란다고 해서 주변의 사물함을 마음대로 더 사용할 수는 없습니다. 이미 다른 목적으로 사용되고 있을 수도 있기 때문이죠. 이와 같이 이미 일정한 크기의 메모리가 할당되어 있는 상황에서, 그 크기를 늘리는 일은 생각만큼 단순하지는 않습니다. 이번 강의에서는 포인터와 malloc의 개념을 응용해서, 이미 정의된 배열의 크기를 바꿔보도록 하겠습니다. 배열의 크기를 조정하는 코드를 작성할 수 있습니다. 일정한 크기의 배열이 주어졌을 때, 그 크기를 키우려면 어떻게 해야 할까요? 단순하게 현재 배열이 저장되어 있는 메모리 위치의 바로 옆에 일정 크기의 메모리를 더 덧붙이면 되겠지만, 실제로..