Stage/Computer Science
-
[자료구조] 스택, 큐, 딕셔너리Stage/Computer Science 2021. 6. 2. 19:04
학습 목표 스택, 큐, 딕셔너리의 원리와 구조를 설명할 수 있다. 1. 큐 사람들이 큐 방식으로 줄을 서있다. 맨 앞 줄에 서있는 사람이 먼저 들어가고, 줄 서 있는 순서대로 입장을 할 것이다. 큐는 값이 아래로 쌓이는 구조인데, 값을 넣고 뺄 때 먼저 들어간 데이터가 먼저 나가는 방식이다. 이를 선입선출 또는 FIFO(First In First Out)라고 한다. 큐는 배열이나 연결리스트를 통해 구현이 가능하다. 2. 스택 책들이 스택 방식으로 쌓여 있다. 사람들이 책을 한 권씩 가져가야 한다고 한다면 보통 사람들은 책이 쌓여 있는 순서대로 책을 한 권씩 가져갈 것이다. 스택은 값이 위로 쌓이는 구조이다. 맨 밑에 깔려 있는 책은 제일 처음 놓여졌을텐데 가장 나중에 들어온 책이 가장 먼저 나가게 되는 ..
-
[자료구조] 트라이Stage/Computer Science 2021. 6. 2. 18:59
학습 목표 트라이의 원리와 구조를 설명할 수 있다. 왜? 문자열의 길이가 일정한 경우 이 문자열들을 저장하고 관리하는 데 최적의 자료 구조는 무엇일까? 연결 리스트, 트리, 해시 테이블이 최선의 방안이 될 수 있을까? 이번엔 트라이라는 자료 구조에 대해 알아보자. 1. 트라이? 트라이는 retrieval의 약자로, 기본적으로 트리형태의 자료 구조이고, 문자열을 빠르게 탐색하게 해주는 자료구조이다. 즉 문자열 탐색에 특화된 자료구조이다. 특이한 점은 각 노드가 배열로 이루어져있다는 것이다. 예를 들어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면, 이 노드는 a부터 z까지의 값을 가지는 배열이 된다. 그리고 이 알파벳은 다음 층의 노드(a~z까지의 배열)를 가리킨다. Hermione, Harry, Ha..
-
[자료구조] 해시 테이블Stage/Computer Science 2021. 6. 2. 08:44
학습 목표 해시 테이블의 원리와 구조를 설명할 수 있다. 왜? 연결리스트나 트리에서는 값을 검색할 때 O(n) 또는 O(log n)의 시간이 걸렸다. 이 시간을 조금 더 단축해서 거의 O(1)에 가깝게 할 수도 있을까? 이것을 가능하게 해주는 해시 테이블이라는 자료 구조에 대해서 알아보자. 1. 해시 테이블? 해시 테이블은 연결 리스트의 배열이다. 여러 값들을 바구니에 나눠 담는 상황을 생각해보자. 각 값들은 해시 함수라는 맞춤형 함수를 통해서 어떤 바구니에 들어갈지 결정이 된다. 각 바구니에 들어가있는 값이 여러 개라면 그 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어진다. 한 바구니에 1, 3, 4가 들어있다면 1, 3, 4는 연결 리스트로 이어진다. 이처럼 연결 리스트가 담긴 바구니가 여..
-
[자료구조] 연결리스트 : 트리Stage/Computer Science 2021. 6. 2. 08:21
학습 목표 트리의 구조를 설명하고 활용하는 코드를 작성할 수 있다. 1. 트리 트리는 연결리스트를 기반으로 한 새로운 데이터 구조이다. 연결리스트에서는 각 노드들의 연결이 1차원적으로 구성되어 있다면, 트리에서 각 노드들의 연결은 2차원적으로 구성되어 있다고 볼 수 있다. 연결리스트에서 각 노드들이 다음에 오는 노드를 가리키는 메모리 주소를 기억하고 있었다면, 트리에서 노드는 다음에 오는 노드들을 가리키고 있다. 이 그림은 트리의 예를 보여주고 있는데, 나무가 거꾸로 뒤집혀 있는 모습을 생각해보면 된다. 가장 높은 층에서 트리가 시작되는 노드를 루트라고 한다. (4번 노란색 노드) 연결 리스트에서 node 라는 이름의 구조체에서는 *next 필드가 정의 되어 있었다면, 그림에서 보면 알 수 있듯이 트리는..
-
[자료구조] 연결 리스트 : 코딩 그리고 시연Stage/Computer Science 2021. 6. 1. 23:27
학습 목표 연결 리스트를 구현하고 사용할 수 있다. 연결 리스트와 배열의 장단점을 설명할 수 있다. 1. 코드 #include #include //연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다. typedef struct node { //node 안에서 정수형 값이 저장되는 변수를 name으로 지정합니다. int number; //다음 node의 주소를 가리키는 포인터를 *next로 지정합니다. struct node *next; } node; int main(void) { // list라는 이름의 node 포인터를 정의합니다. 연결 리스트의 가장 첫 번째 node를 가리킬 것입니다. // 이 포인터는 현재 아무 것도 가리키고 있지 않기 때문에 NULL 로 초기화합니다. node *list ..
-
[자료구조] 연결리스트 : 도입Stage/Computer Science 2021. 6. 1. 23:25
학습 목표 연결 리스트의 정의를 설명할 수 있다. 1. 데이터 구조 기본적인 포인터 구조만 이용해서 메모리를 관리하기에는 다소 번거로울 때가 많다. 데이터 구조는 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체이다. 쉽게 기억하기 위해, 일종의 메모리 레이아웃 또는 메모리 지도라고 생각하자. 2. 연결 리스트 배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있다. 하지만 다음 인덱스의 값이 메모리상에서 멀리 떨어져 있다면 안되는 걸까? 각 인덱스 값이 메모리상에 여러 군데 나뉘어져 있다고해도 자기 바로 뒤에 오는 값의 메모리 주소만 기억하고 있다면 그 값을 연이어서 읽어들일 수 있다. 이것을 연결 리스트라고 한다. 크기가 3인 연결 리스트 이다. 이 연결리스트는 각 인덱스가 메..
-
[자료구조] 배열의 크기 조정Stage/Computer Science 2021. 6. 1. 23:23
학습 목표 배열의 크기를 조정하는 코드를 작성할 수 있다. 1. 배열의 크기 조정 배열의 크기를 키우려면 어떻게 해야 할지 생각해보자. 배열의 크기가 3이고, 이 크기를 4로 하고 싶다면 단순히 생각하면 크기가 3인 배열 바로 옆에 한 바이트의 공간만 더 붙이면 된다. 실제로도 이런 방식으로 배열의 크기를 조정할 수 있을까? 실제로는 키우려는 배열 메모리 주위에는 다른 메모리들로 둘러 쌓여있을 확률이 높다. 기존에 사용하고 있던 메모리 뒤에는 다른 데이터들이 담겨 있을 수 있는데 이 상태에서 데이터를 메모리를 새로 할당하지 않고 메모리 크기를 키운다면 뒤에 있던 메모리에 데이터를 덮어쓰는 일이 발생할 수 있다. 따라서 안전하게 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮..
-
[자료구조] malloc과 포인터 복습Stage/Computer Science 2021. 6. 1. 23:21
학습 목표 포인터의 개념과 malloc 함수의 용법을 잘 이해할 수 있다. 1. 오류 파악하기 아래 코드를 보고 문제가 될 만한 지점이 어디인지 찾아보자. int main(void) { int *x; int *y; x = malloc(sizeof(int)); *x = 42; *y = 13; } malloc 함수는 할당하고 싶은 크기를 인자로 받는다. 의미를 바로 파악하지 못한 부분: *x = 42 = x의 주소로 가서 42를 저장해라. 문제가 되는 부분은 *y = 13; 이 부분이다. 위 코드에서 x에는 메모리를 할당해줬는데, y에는 아무런 액션을 취한 것이 없다. y는 포인터로는 선언되었는데, 어디를 가리킬지에 대해서는 아직 정의가 되지 않았다. 초기화 되지 않은 *y는 프로그램 어딘가를 임의로 가리키..