Computer Science (28) 썸네일형 리스트형 자료 구조 | 트라이 학습 목표 트라이의 원리와 구조를 설명할 수 있다. 트라이 트라이(trie)는 기본적으로 트리 형태의 자료 구조다. 트라이는 각 노드가 배열로 이루어져 있다는게 특징이다. 예시를 보자. 영어 알파벳으로 이루어진 문자열 값을 저장한다고 생각해보자. 노드는 a부터 z까지의 값을 가지는 배열이 될 것이다. 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z배열)를 가리킨다. 트라이의 시간 복잡도 앞선 예시와 같은 트라이에서 값을 검색하는데 걸리는 시간은 문자열의 길이에 의해 정해진다. 일반적인 영어 이름의 길이를 n이라고 했을 때, 검색 시간은 O(n)이지만, 대부분의 이름은 그리 크지 않은 상수이기 때문에 O(1)이나 마찬가지다. 생각해보기 트라이가 해시 테이블에 비해 가지는 장점과 단점은 무엇일까. 트라.. 자료 구조 | 해시 테이블 연결 리스트나 트리에서 값을 검색할 땐 O(n) 또는 O(log n)의 시간이 걸린다. 이 시간을 단축해서 거의 O(1)에 가깝게 할 수 있을까? 학습 목표 해시 테이블의 원리와 구조를 설명할 수 있다. 해시 테이블 해시 테이블(hash table)은 자료 구조 중 하나로 연결 리스트의 배열을 사용해 데이터를 저장한다. 각각의 데이터는 해시 함수를 통해 고유한 인덱스를 생성하고, 이를 활용해 값을 저장하거나 검색하게 된다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 쉬운 예시를 보자. 예시에서는 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 '이름의 가정 첫 글자'이다. 이 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳을 시작으로 하는 이름.. 자료 구조 | 연결리스트(3) 트리 연결 리스트에서는 각 요소가 다른 요소를 하나씩만 가리키고 있었다. 만약 가리키는 요소가 여러 개가 된다면 어떻게 될까. 학습 목표 트리의 구조를 설명하고 활용하는 코드를 작성할 수 있다. 연결 리스트와 트리 트리는 연결 리스트를 기반으로 한 데이터 구조다. 연결 리스트에서 각 노드들의 연결이 1차원적이었다면, 트리에서는 2차원적으로 구성되어 있다. 각 노드는 일정한 층에 속하고 다음 층의 노드를 가리키는 포인터를 가진다. 트리가 시작되는 노드를 루트라고 한다. 루트는 다음 층의 노드를 가리키며 이를 자식 노드라고 한다. 이진 검색 트리에서 하나의 노드는 두 개의 자식 노드를 가진다. 왼쪽 자식 노드는 자신의 값보다 작고, 오른쪽 자식 노드는 크다. 이러한 트리 구조는 이진 검색을 수행하는데 유리하다. .. 자료 구조 | 연결 리스트(2) 코딩 및 특징 학습 목표 연결 리스트를 구현하고 사용할 수 있다. 연결 리스트와 배열의 장단점을 설명할 수 있다. 연결 리스트 코딩 구조체를 이용하여 실제 연결 리스트를 구현해보자. 지난 포스팅에서 본 그림을 생각하며 코드를 살펴보자. #include #include typedef struct node{ int number; struct node *next; } node; int main(void) { // list라는 이름의 node 포인터 정의 // 아무 것도 가리키고 있지 않기 때문에 NULL로 초기화 node *list = NULL; // 새로운 node를 위해 포인터를 정의하고 메모리 할당 node *n = malloc(sizeof(node)); if(n == NULL){ return 1; } // n의 nu.. 자료 구조 | 연결 리스트(1) 도입 이제껏 여러 자료형의 데이터를 메모리 상에 저장하고 삭제하는 방법을 배웠다. 이번 강의부터는 메모리를 좀 더 효율적으로 관리하고 사용하는 법을 배운다. 데이터 구조의 개념과 연결 리스트에 대해 알아보자. 학습 목표 연결 리스트의 정의를 설명할 수 있다. 데이터 구조와 연결 리스트 데이터 구조는 메모리를 좀 더 효율적으로 관리하기 위해 새로 정의하는 구조체다. 연결 리스트(linked list)는 데이터 구조 중 하나이다. 배열에서는 각 인덱스의 값이 메모리 상에 연이어 저장되었다. 하지만 메모리 상의 어디에 있든 주소만 알고 있다면 연이어 값을 읽을 수 있다. 이러한 개념을 사용한 것이 연결 리스트이다. 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 다음 값의 주소(포인터)를 저장한다. 연결 리.. 알고리즘 | 재귀 ✔ 학습목표 함수를 재귀적으로 사용하는 코드를 작성할 수 있다. 재귀 동일한 작업을 반복할 때는 사용자 정의 함수를 사용하면 보다 효율적으로 코드를 만들 수 있다고 배웠다. 하지만 함수 내에서 동일한 작업이 반복되는 경우에는 어떻게 해야 할까. 본 글에서는 함수를 함수 내에서 재사용하는 방법, 즉 재귀적으로 호출하는 방법을 공부한다. 우리는 이제껏 int main(void){}안에서 프로그램을 작성하고 함수를 호출했다. 그런데 생각해보면 main()도 역시 함수이다. 함수 안에서 또 다른 함수를 사용해온 것이다. 이 사실을 알게 되면 함수가 본인 스스로를 호출해서 사용할 수 있는지에 대한 의문이 생긴다. 답은 할 수 있다 이다. 이를 재귀(Recursion)라고 한다. # ## ### #### #####.. 알고리즘 | 병합 정렬 ✔ 학습목표 재귀를 활용한 병합 정렬을 구현할 수 있다. 병합 정렬 병합 정렬(merge sort)은 원소가 한 개가 될 때까지 계속해서 나누다가 다시 합쳐가며 정렬을 하는 방식이다. 합병 정렬이라고도 한다. 이는 분할 정복(divide and ) 알고리즘의 하나이다. 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아 원래의 문제를 해결하는 전략이다. 병합 정렬의 단계 병합 정렬은 세 단계로 이루어진다. 1) 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 2) 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할한다. 3) 결합(Combine): 정렬된 부분 배열들을 하나의 배열로.. 알고리즘 | 정렬 알고리즘의 실행시간 ✔ 학습목표 1. 여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Bio O와 Big Ω로 정의할 수 있다. 2. 조건문을 사용해 좀 더 효율적인 알고리즘을 만들 수 있다. 알고리즘의 실행 시간 이제껏 배운 선형 검색(Linear search), 이진 검색(Binary search), 버블 정렬(Bubble sort), 선택 정렬(Selection sort)의 실행시간(시간 복잡도)은 각각 어떻게 되는지 정리해보자. 상한은 다음과 같다. O(1) O(log n) O(n) O(n log n) O(n^2) Linear search o Binary search o Bubble sort o Selection sort o 하한은 다음과 같다. Ω(1) Ω(log n) Ω(n) Ω(n log n) Ω(n^2) L.. 이전 1 2 3 4 다음
