본문 바로가기

Computer Science/자료구조24

[자료구조] 후기 코딩은 자고로 독학이라 생각한다 스스로 찾아보고 배우면서 시행착오를 겪어야지만 진정한 실력이 는다고 생각한다 이런 마인드를 가진 나였지만.. 자료구조 수업은 정말 힘들었다 비유를 하자면 알파벳을 알려주고서 바로 영작을 하라는 수준이었다c언어로 연결리스트를 처음 구현할 때의 그 막막함이란.. 진짜 심장이 턱! 하고 막히는 기분이었다 평소에 머리가 나쁘단 소리를 들어본 적이 없고, 수학 잘한다는 소리를 듣던 내가 그 순간만큼은 정말 심각한 바보가 된 것 같았다 손을 쓸 도리가 없었다 그러한 허탈감과 죄책감은 나의 오기를 발동하여 내 안에 있던 독기를 깨우는 듯했다 아마 연결리스트 문제를 세종대 OJ에 170번 submit 한 사람은 내가 유일하지 않을까..라는 생각이 든다 하지만 부끄러움은 단 1도 없다 내.. 2024. 6. 25.
[자료구조] ep8) 분리집합(Disjoint Set) ㅇ분리집합 ADT: 교집합이 없는 집합들서로소집합이라고도 불리며 Union-Find라고도 한다 소속 관계가 분명해야 하는 데이터를 다룰 때 유용하다목적: 원소가 어느 집합에 귀속되어 있는지 (find 함수) 직접 응용: 동치관계(e.g. 그래프), 최소신장트리간접 응용: 알고리즘 구현, 저료구조 구현  - set find(e): 원소 e가 속한 집합을 반환- union(x, y): 집합 x, y를 통합- int size(S): 집합 S 원소의 수를 반환  [구현 방법 2가지]1. 리스트(or 배열)에 기초한 구현 find는 빠르고 union은 느리다2. 트리에 기초한 구현find는 느리고 union은 빠르다  1-1 리스트에 기초한 구현: 분리집합 집단을 레코드의 배열로 표현  1-2 배열에 기초한 구현.. 2024. 6. 11.
[자료구조] ep7++) 결정 트리(decision tree) - 양자택일식 문답시스템 ㅇ결정 트리(decision tree): 의사결정 과정과 연관된 이진트리- 내부노드: yes/no로 답 할 수 있는 질문- 외부노드(리프): 결정    활용) 프로그램 요구사항 다음과 같이 한 프로그램 내에서 양자택일식 문답시스템의 구축과 사용을 연속하여 지원하는 프로그램을 작성하라. 1) 문답시스템 구축 지원 기능 -  결정트리는 배열 또는 연결리스트 가운데 하나를 이용하여 구축되어야 한다. -  1회의 상담은 최소 3회 ~ 최대 5회의 문답을 통해 완료되도록 제한하라(즉, 상담설계자가 이 시스템을 이용하여 최소 8개 ~ 최대 32개의 결정을 포함하는 결정트리의 구축을 지원할 수 있어야 한다). -  설계된 결정트리를 프로그램을 통해 구축하라(즉, buildDecisionTree를 1회 호출). 2) .. 2024. 6. 11.
[자료구조] ep7+) 이진 트리 구현 및 탐색 이번 문제에서는 트리가 고정되지 않고 트리의 모양이 입력으로 주어진다. 1. 트리 만들기 (구현)◦ 트리는 연결이진트리로 구현하며 각 노드에 저장되는 정보는 아래와 같다.◦ 선위순회 순서로 각 노드에 대한 정보가 주어지면, 루트노드부터 확장해 가는 방식으로 트리를 구성할 수 있다.- 노드 번호는 유일한 양의 정수며, 노드 번호에 특별한 순서는 없다. - 각 노드에 대한 정보는 괄호에 싸인 세 개의 정수, 즉 (x y z)로 표현된다.- 여기서 x는 해당 노드의 번호, y는 x의 왼쪽 자식 노드의 번호, z는 x의 오른쪽 자식 노드의 번호를 나타낸다. 해당 자식이 없는 경우에는 번호 0이 주어진다.    2. 트리 탐색◦ 트리 탐색은 루트노드에서 시작하여 자식 링크를 따라 내려가면서 진행된다.- 탐색 도중.. 2024. 6. 11.
[자료구조] ep7-2) 트리 순회(tree traversal) 순회(traversal): 트리의 노드들을 체계적인 방식으로 방문하는 것을 의미트리의 주요 순회로는 크게 3가지가 있고 추가적인 순회로 또 2가지가 더 있다 1. 선위순회(predorder traversal): Root > Left > Right  응용: 구조적 문서를 인쇄, 계층적 파일 시스템의 모든 폴더들을 나열 void preorderTraversal(NODE* node) { // 재귀적 성질을 이용한다 if (node == NULL) { return; } printf(" %d", node->data); // Root preorderTraversal(node->left); // Left preorderTraversal(node->right); // Right}.. 2024. 6. 10.
[자료구조] ep7-1) 트리(Tree) ㅇ트리(Tree) ADT: 계층적으로 저장된 데이터 원소들을 모델링 - 계층적 구조맨 위의 원소를 제외하고, 각 트리 원소는 부모(parent) 원소와 0개 이상의 자식(children) 원소들을 가진다(전제: 트리는 비어있지 않다 - 알고리즘 단순화) 내부 노드(internal node): 적어도 한 개의 자식을 가진 노드(A, B, C, F)외부 노드, 리프(external node, leaf): 자식이 없는 노드(E, I, J, K, G, H, D)형제(siblings): 같은 부모를 가진 노드들(G, H)조상(ancestor): 부모(parent), 조부모(grandparent), 증조부모(grand-grandparent) 등자손(descendant): 자식(child), 손주(grandchild.. 2024. 6. 9.
[자료구조] ep6+) 두 개의 큐로 스택 설계 문제) 두 개의 큐로 스택을 설계하라프로그램 요구사항 S : S에 대해 isEmpty() 호출 (isEmpty)t : S에 대해 top() 호출 (top)p n1 n2 n3 ... : S에 대해 push(n1), push(n2), push(n3) ... 를 차례로 호출 (push)P : S에 대해 push(n)을 100만번 호출 - 여기서 n은 10~99 사이의 정수 난수 (pushMillion) o : S에 대해 pop() 호출 (pop) q : 수행 종료 (quit)  실행예에서 괄호 속의 수는 해당 명령 수행직후의 스택 S 사이즈를 나타낸다. cputime X.XXXXXXXX는 측정된 cputime in milliseconds이다. 이 실행시간은 각 부함수에 대한 호출과 반환 사이에 소요된 cput.. 2024. 6. 9.
[자료구조] ep6-3) 데크(Deque) ㅇ데크(Double-Ended Queue) ADT: 임의의 개체들을 저장하며, 스택과 큐의 합체 방식으로 작동한다삽입(add)과 삭제(delete)는 앞(front)과 뒤(rear)라 불리는 양쪽 끝 위치에서 수행쉽게 말해서, 양쪽 방향으로의 add/delete 가 둘 다 가능하다   역시 마찬가지로 데크는 배열과 리스트 2가지 방법으로 구현할 수 있다 1. 이중연결리스트에 기초한 데크 2. 배열에 기초한 데크똑같이 선형 배열은 비효율적이므로, 원형 배열을 사용한다       문제) 데크는 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 자료구조다. 헤더 노드와 트레일러 노드가 없는 이중연결리스트를 사용하여 아래에 정의된 데크 함수들을 구현하시오.◦ 초기 상태- 주의 : 명령 수행.. 2024. 6. 9.
[자료구조] ep6-2) 원형 큐(Circular Queue) ※ 리스트에 기초한 큐는 ep6) 큐를 보도록 하자https://claremont.tistory.com/entry/ep6-%ED%81%90Queue ep6) 큐(Queue)ㅇ큐 ADT: 임의의 개체들을 저장하며, 선입선출(First-In First-Out, FIFO) 순서를 따른다삽입(enqueue)은 큐의 뒤(rear), 삭제(dequeue)는 큐의 앞(front)이라 불리는 위치에서 수행  - 직접 응용: 대기열, 관료claremont.tistory.com    배열로 선형 큐를 구현하면 공간 낭비, 공간의 재사용 불가 등의 문제가 발생한다그래서 보통은 원형 큐를 사용한다ㅇ원형 큐(Circular Queue): 선형 큐의 문제점을 보완하기 위한 자료구조환형 큐라고도 한다 빈 큐를 만원 큐로부터 차별하.. 2024. 6. 8.

티스토리툴바