본문 바로가기

분류 전체보기

 (49)
Palindrome (회문) palindrome (회문) 회문 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다. Ex) TENET, 기러기, 수박이박수 가장 직관적인 방법은 가장 첫글자와 마지막글자, 두번째 글자와 마지막에서 두번째 글자를 서로 다 비교해 보는 것이다. string s; bool palindrome (string s) { int N = s.length()-1; for (int i = 0; i #a#b#d#c#c#d# 각 자리 사이사이에 같은 문자(#)를 넣어 홀수개의 스트링 길이로 만들어주면 된다. 구현 #include #include #include #..
할 수 있는 것과 할 수 없는 것 모든 일을 하고 싶은 것과 하기 싫은 것으로 나누지 말고 할 수 있는 것과 할 수 없는 것으로 나눠 할 수 있는 것을 다 하다보면 하고 싶은 것이 할 수 있는 것이 되어 있지 않을까 생각을 해본다.
14. Graph Basics Graph 그래프란? 정점(V, vertex)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조 = 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 용어 정점(Vertex, V): 꼭짓점 (node라고도 부름) ex) 위 그래프에서 정점은 총 7개 0,1,2,3,4,5,6 이 있다. 간선(Edge, E): 꼭짓점 간의 관계, 꼭짓점을 연결하는 선 (link, branch라고도 부름) ex) 위 그래프에선 간선이 총 6개 [(0-1) ,(1-2), (1-3), (2-5), (2-6), (3-4)] 있다. 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점 ex) 위 그래프에선 정점 1의 인접 정점은 정점 0, 2, 3이 있다. 정점의 차수(degree)..
11. AVL tree AVL tree 모든 BST 연산은 $ O(d) $ (d는 트리의 높이) 이다. $ d = \lfloor \log_2 N \rfloor $ (N은 트리의 총 노드 갯수) best case: $ O(\log N) $ worst case: $ O(N) $ 여기서 차이가 나는 이유는 트리의 균형의 문제이다. BST의 균형을 맞추기 위해 고안된 알고리즘이 많다. AVL tree: Adelson-Velskii and Landis (AVL) trees (height-balanced trees) Weight-balanced trees Red-black trees Splay trees and other self-adjusting trees B-trees and other (e.g. 2-4 trees) multiway ..
10. Heapsort Heapsort 전략 i. Heapify: N개의 정렬되지 않은 array를 max Heap 구조로 만들기 ii. maximum 키를 순차적으로 pop 내림차순 정렬을 위해서는 최대힙, 오름차순 정렬을 위해서는 최소 힙을 만들면 된다. 동작 i) Heapify Bottom-up method로 최대 힙을 만들자. 이 경우 마지막 Internal node 3-node heap에서 시작한다. 이미 T가 루트인 3-node heap은 heap 구조를 만족하므로 패스 ii. 순차적으로 maximum key를 지운다. 한 번에 하나씩 최대값을 제거합니다. null을 제거하는 대신 배열에 그대로 두십시오. 이런식으로 쭉쭉 하다보면 이렇게 정렬이 된다. // 실행 과정 Enter a word to sort: SORTE..
9. Heap, Priority Queue Heap 힙은 완전 이진 트리의 일종으로 priority queue를 구현하기 위해 만들어진 자료구조 특징 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 반정렬 상태(느슨한 정렬 상태) 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) Priority Queue 우선 순위가 있는 큐, 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. Ex) 은행에서 줄을 설 때 먼저 온 순서대로(FIFO) 서비스를 받을 수 있습니다. 하지만 노인이나 장애인이 줄을서는 경우 그들에게 우선권을 부..
8. Binary Search Tree Binary Search Tree 정의: binary tree in symmetric order Binary Tree: 노드로 구성되며, 각 노드는 최대 두 개의 자식(왼쪽과 오른쪽 자식)을 가진다. Symmetric Order 모든 노드는 키를 갖는다. 모든 노드의 키는 왼쪽 하위 트리의 모든 키보다 큼 오른쪽 하위 트리의 모든 키보다 작음 중복된 노드가 없어야 한다. 이 트리에서 키 값이 가장 작은 노드 키 값이 가장 큰 노드 왼쪽 서브트리에서 가장 큰 키 값의 노드 오른쪽 서브트리에서 가장 작은 키 값의 노드 를 구하는 방법을 알아보자. 구조 Node structure Key: Value: Left: Right: BST node structure typedef int Key; typedef char..
7. Tree Tree 정의: Direct Acyclic Graph 노드로 구성된 자료구조 Term level( =degree): leaf nodes( =internal nodes): 자식이 없는 노드 height(=depth): 루트 노드에서 가장 깊숙히 있는 노드의 깊이 root: 첫 번째 노드 sibling: 같은 부모를 가지는 노드 List representation: (A (B (E (K, L), F), C (G), D (H (M), I, J) ) ) Binary Tree 각 노드에 왼쪽 child and/or 오른쪽 child가 있는 트리 (정확히 두 자녀는 중간 아이가 아닌 왼쪽 아이와 오른쪽 아이를 의미하기 때문에) 즉 얘들도 binary tree 이다. Full Binary Tree : depth가 $..

티스토리툴바