도전하는 일반인

들어가기 전에 힙에서 새로운 데이터를 추가하거나 제거하는 방법에 대해 살펴보도록 하겠습니다. 학습 목표 힙에서 노드를 추가하거나 제거하는 방법을 설명할 수 있습니다. 핵심 단어 힙 최대 힙과 최소 힙 힙:추가와 제거 힙에 새로운 데이터를 추가하거나 제거할 때 힙의 규칙을 지켜야 합니다. 최대 힙이면 부모 노드가 자식 노드보다 커야 하고 최소 힙은 자식 노드가 부모 노드보다 커야 합니다. 노드 추가 Add: insert next available space tricke up 1. 비어있는 공간에 노드를 추가합니다. 2. 부모 노드보다 큰 숫자인지 확인하고 만약 그렇다면 두 노드를 바꿉니다. (trickle up) 루트 제거 Remove: remove the root replace w/ last elemen..

들어가기 전에 이번 강의에서는 간단하지만 많이 쓰이는 데이터 구조 세 가지를 더 살펴보겠습니다. 이들은 사실 우리가 이미 여태까지 강의에서 은연중에 다뤘던 구조들이기도 합니다. 메모리의 구조에서 잠깐 살펴봤던 ‘스택’과 ‘큐’, 그리고 해시 테이블로 구현할 수 있는 ‘딕셔너리’에 대해 알아보겠습니다. 학습 목표 스택, 큐, 딕셔너리의 원리와 구조를 설명할 수 있습니다. 핵심 단어 스택 큐 딕셔너리 우리가 여태껏 배운 배열, 연결 리스트, 해시 테이블, 트라이 외에도 많은 자료 구조들이 있습니다. 또는 위의 자료 구조를 기반으로 해서 문제를 해결하는데 적합한 새로운 자료 구조를 만들 수도 있습니다. 아래와 같이 세 가지의 대표적인 자료 구조를 간단하게 알아보겠습니다. 큐 큐는 메모리 구조에서 살펴봤듯이 값..

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

들어가기 전에 연결리스트나 트리에서는 값을 검색할 때 O(n) 또는 O(log n)의 시간이 걸렸습니다. 이 시간을 조금 더 단축해서 거의 O(1)에 가깝게 할 수는 없을까요? 이번 강의에서는 이를 가능케 해주는 ‘해시 테이블’ 이라는 자료 구조에 대해 알아보겠습니다. 학습 목표 해시 테이블의 원리와 구조를 설명할 수 있습니다. 핵심 단어 해시 테이블 해시 함수 해시 테이블은 ‘연결 리스트의 배열’입니다. 여러 값들을 몇 개의 바구니에 나눠 담는 상황을 생각해 봅시다. 각 값들은 ‘해시 함수’라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정 됩니다. 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어집니다. 이와 같이 연결 리스트가 담긴 바구니가 여러개 있는 것이 ‘연결..

들어가기 전에 연결 리스트를 활용해서 보다 더 다양한 데이터 구조를 만들 수 있습니다. 연결 리스트에서는 각 요소가 다른 요소를 하나씩만 가리키고 있었습니다. 만약 가리키는 요소가 여러개가 된다면 어떤 장점과 단점이 있을까요? 이번 강의에서는 ‘트리’라는 연결 리스트 기반의 자료 구조를 알아보겠습니다. 학습 목표 트리의 구조를 설명하고 활용하는 코드를 작성할 수 있습니다. 핵심 단어 트리 루트 트리는 연결리스트를 기반으로 한 새로운 데이터 구조입니다. 연결리스트에서의 각 노드 (연결 리스트 내의 한 요소를 지칭)들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있다고 볼 수 있습니다. 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 됩..

들어가기 전에 이번 강의에서는 학생들과 함께 연결 리스트를 직접 시연해보도록 하겠습니다. 또 연결 리스트와 배열을 비교해보고 그 장단점을 생각해 보겠습니다. 학습 목표 연결 리스트와 배열의 장단점을 설명할 수 있습니다. 핵심 단어 연결 리스트 배열 배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있습니다. 하지만 이런 유동적인 구조는 그 대가가 따릅니다. 구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능합니다. 연결 리스트에 값을 추가하거나 검색하는 경우를 생각해 봅시다. 이를 위해서는 해당하는 위치까지 연결 리스트의 각 node들을 따라 이동해야 합니다. 따라서 연결 리스트의 크기가 n 일때 그 실행 시간은 O(n)이 됩니다. 배열의 경우..

들어가기 전에 지난 강의에서 연결 리스트의 정의와 리스트의 기본 단위가 되는 구조체를 정의하는 방법을 배웠습니다. 이번 강의에서는 이 구조체를 이용하여 실제로 연결 리스트를 구현하고 사용해보도록 하겠습니다. 학습 목표 연결 리스트를 구현하고 사용할 수 있습니다. 핵심 단어 연결 리스트 앞서 정의한 구조체를 활용해서 실제로 연결 리스트를 구현해보도록 하겠습니다. 아래 코드의 내용과 각 주석을 따라가 보세요. 생각해보기 연결 리스트의 중간에 node를 추가하거나 삭제하는 코드는 어떻게 작성할 수 있을까요? 나의 생각: 2021 09 29일 아직 위의 코드를 이해하지 못했다. 출처 : https://www.boostcourse.org/cs112/lecture/119039?isDesc=false 네이버커넥트재단

들어가기 전에 우리는 여러 자료형의 데이터를 메모리 상에 저장하고 읽고 삭제하는 방법을 배웠습니다. 컴퓨터 프로그램은 이러한 데이터를 이용해서 다양한 작업을 수행할 수 있습니다. 하지만 좀 더 복잡한 프로그램을 구현하다 보면 기본적인 포인터 구조만 이용해서 메모리를 관리하기에는 다소 번거로울 때가 많습니다. 만약 메모리를 좀 더 효율적으로 관리하고 사용할 수 있다면 어떨까요? 이번 강의에서는 데이터 구조의 개념과 연결 리스트에 대해 알아보겠습니다. 학습 목표 연결 리스트의 정의를 설명할 수 있습니다. 핵심 단어 연결 리스트 데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체입니다. 일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있습니다. 이번 강의에서는 데이터 구조..

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

들어가기 전에 이번 강의부터는 C로 구현할 수 있는 다양한 데이터 구조를 배우게 됩니다. 데이터 구조를 정의하고 관리하는데 있어서 메모리와 포인터에 대한 개념을 정확히 이해하는 것이 중요합니다. 먼저 지난 시간에 배운 malloc 함수와 포인터를 복습할 수 있는 작은 예제를 살펴 보겠습니다. 학습 목표 포인터의 개념과 malloc 함수의 용법을 잘 이해할 수 있습니다. 핵심 단어 포인터 malloc 아래와 같은 main 함수 코드가 있습니다. 여기서 문제가 될 만한 지점을 발견할 수 있나요? main 함수 안의 첫 두 줄에서는 포인터 x와 y를 선언합니다. 그리고 x에는 malloc 함수를 이용해서 int 자료형 크기에 해당하는 메모리를 할당합니다. 그 다음에는 x와 y 포인터가 가리키는 지점에 각각 4..