CS50
-
[Data Structure] 스택, 큐, 딕셔너리알고리즘 & 자료구조 2021. 1. 25. 16:49
큐 큐는 값이 아래로 쌓이는 구조이다. 값을 넣고 뺄 때 '선입선출' 또는 'FIFO' 라는 방식을 따르게 된다. 가장 먼저 들어온 값이 가장 먼저 나가는 것이다. 식당에서 주문을 하기 위해 줄을 설때 가장 먼저 줄을 선 사람이 가장 먼저 주문을 하는것 과 동일하다. 배열이나 연결리스트를 통해 구현 가능하다. ***예제 소스코드 바로가기 ====>>> junecode.tistory.com/49 [baekjoon] 10828번 스택 (스택) 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위 junecode.tistory.com 스택 반면 스택은 값이 위로 ..
-
[Data Structure] 트라이알고리즘 & 자료구조 2021. 1. 25. 16:32
'트라이'는 기본적으로 ' 트리' 형태의 자료 구조이다. 특이한 점은 각 노드가 '배열'로 이루어져 있다는 것이다. 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장 한다고 하면 이 노드는 a부터 z까지의 값을 가지는 배열이 된다. 그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z배열)를 가리킨다. 아래 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해보자 루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 된다. 단순히 문자열의 각 문자를 보며 트리를 탐색해나가기만 하면 되기때문에, 위와 같은 트라이에서 값을 검색하는데 걸리는 시간은 '문자열의 길이'에 의해 한정된다. 일반적인 영어 이름의 길이를 n이라고 할때, 검색 시간은 O..
-
[Data Structure] 해시 테이블알고리즘 & 자료구조 2021. 1. 25. 16:13
해시 테이블은 '연결 리스트의 배열' 이다. 여러 값들을 몇 개의 바구니에 나눠 담는 상황을 생각해보자 각 값들은 '해시 함수' 라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정된다. 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결리스트로 이어진다. 이와 같이 연결 리스트가 담긴 바구니가 여러개 있는 것이 '연결 리스트의 배열' , 즉 '해시 테이블' 이 된다. 쉬운 예로 아래 그림과 같이 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 ' 이름의 가장 첫 글자' 인 경우를 생각해보자 그 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며. 각 포인터는 그 알파벳을 시작하는 이름들을 저장하는 연결 리스트를 가리키게 된다. 만약 해시 함수가 이상적이라면, 각 바구..
-
[Data Structure] 연결 리스트 : 트리알고리즘 & 자료구조 2021. 1. 25. 14:15
트리는 연결리스트를 기반으로 한 새로운 데이터 구조다. 연결 리스트에서 각 노드들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어있다고 볼 수 있다. 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 된다. 가장 높은 층에서 트리가 시작되는 노드를 '루트' 라고 한다. 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 '자식 노드' 라고 한다. 위의 그림을 살펴보자, 뭔가 규칙을 찾았는가? 왼쪽이 자식 노드는 자신의 값보다 작고 오른쪽 자식 노드는 자신의 값보다 크다. 따라서 이런 트리 구조는 이진 검색을 수행하는데 유리하다. #include #include //이진 검색 트리의 노드 구조체 typedef struct node { //..
-
[Data Structure]연결 리스트 : 코딩알고리즘 & 자료구조 2021. 1. 24. 23:11
#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 = NULL; //새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킴 node *n = malloc(sizeof(node)); if(n == N..
-
[Data Structure]연결 리스트 : 도입알고리즘 & 자료구조 2021. 1. 24. 16:37
배열에서는 각 인덱스의 값이 메모리 상에서 연이어 저장 되어 있다. 하지만 꼭 그럴필요가 있을까? 각 값이 메모리상의 여러군데 퍼져 있다고 해도 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있을것이다. 이를 '연결 리스트' 라고 한다. 위의 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음값의 주소 (포인터)를 저장한다. 3은 다음값이 없기에 NULL을 다음 값의 주소로 저장한다. 연결 리스트를 사용하기 위해서는 아래 코드와 같이 간단한 구조체로 정의할 수 있다. //typedef struct 대신에 typedef stuct node 라고 'node'를 함께 명시해 주는 것은, //구조체 안에서 node를 사용하기 위함이다. typedef..
-
[Data Structure] 배열의 크기 조정하기알고리즘 & 자료구조 2021. 1. 24. 16:03
소스 코드를 보기전에 먼저 생각해보자 우리가 이미 일정한 크기의 배열을 선언 했다면, 그 크기를 키우려면 어떻게 해야할까? list[0] = 1; list[1] = 2; list[2] = 3; 밑에 표를 메모리라 생각해보자 list[3] 에 4를 저장하고 싶지만 h라는 값이 메모리에 담겨있다. e m m a 1 2 3 h e l l o 단순히 메모리의 위치 바로옆에 일정 크기의 메모리를 덧붙일수 없다. 따라서 안전하게 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨줘야 한다. 이러한 작업은 O(n), 즉 배열의 크기 n만큼의 실행 시간이 소요될것이다. 이 과정을 코드로 나타내면 아래와 같다. #include #include int main(void) { //첫번째 방법 /..
-
[알고리즘] 병합 정렬알고리즘 & 자료구조 2021. 1. 21. 16:31
병합 정렬 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다. 그리고 이 과정은 재귀적으로 구현된다. 아래의 숫자들을 오름차순으로 정렬해 보자 7 4 5 2 6 3 8 1 먼저 숫자들을 반으로 나눈다. 7 4 5 2 | 6 3 8 1 그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눈다. 7 4 | 5 2 | 6 3 8 1 마지막으로 한 번 더 나눠준다 7 | 4 | 5 2 | 6 3 8 1 이제 숫자가 7 과 4로 나뉘어져있다. 두 숫자를 병합 해보자. 단, 작은 숫자가 먼저 오도록한다 4 7 | 5 2 | 6 3 8 1 마찬가지로 5 ,2 역시 나눈 후 병합해보면 4 7 | 2 5 | 6 3 8 1 이제 4 7 | 2 5 부분을 병합 2 4 5 7..