자료구조6 04. 컬렉션(Collection) 컬렉션(Collection) 컬렉션 자료구조는 데이터를 서로 연관시키지 않고 모아두는 컨테이너(container) 이다. 맨버십 연산자 : in 크기 함수 : len 반복성 set and dictionary Set 반복 가능하다. 가변적이며 중복 요소가 없다. 정렬되지 않는 데이터 타입이다. 즉 인덱스 연산을 할 수 없다. 중복 요소를 제거할 수 있다. 시간복잡도 O(1) 이다. 딕셔너리(dictionary) hash table로 구현되어 있다. 특정 객체에 해당하는 임의의 정수 값을 상수 시간 내에 계산한다. 연습문제 단어 횟수 세기 애너그램 문장 또는 단어의 철자 순서를 바꾸는 놀이 주사위 합계 경로 주사위를 두 번 던져서 합계가 특정 수가 나오는 경우의 수와 경로를 구해보자 단어의 중복 문자 제거 .. 2020. 6. 1. 자료구조: 그래프의 개념과 구현 그래프란? 단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조 그래프 구현 방식 1. 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식 2. 인접 리스트(Adjacency list) : 리스트를 사용하는 방식 그래프(Graph)와 관련된 용어 정점(vertex): 위치라는 개념. (node 라고도 부름) 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름) 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배 .. 2019. 9. 5. 자료구조: 순차 탐색(Sequential Search) & 이진 탐색(Binary Search) 순차 탐색(Sequential Search) 이란? 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법이다. O(N)의 시간복잡도를 갖는다. 이진 탐색(Binary Search) 이란? 배열 내부 데이터가 이미 정렬 되어 있는 상황에서 사용 가능한 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 한번 확인할 때마다 확인해야 하는 원소의 개수가 절반씩 줄어든다는 점에서 탐색 시간이 O(logN)의 시간복잡도를 갖는다. 코드 // 순차 탐색(Sequential Search) #define _CRT_SECURE_NO_WARNINGS #include #include #include #define LENGTH 1000 char **array; int founded = 0; .. 2019. 8. 30. 자료구조: 우선순위 큐(Priority Queue) 우선순위 큐란? 우선순위를 가진 데이터들을 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선 순위가 높은 데이터가 가장 먼저 나온다는 특징이 있다. 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다. 우선순위 큐와 큐의 차이점 일반적인 큐는 선형 구조를 가지고 있지만 우선순위 큐는 트리(Tree) 구조로 보는 것이 합리적이다. 일반적으로 우선순위 큐는 최대 힙을 이용하여 구현한다. 최대 힙(Max Heap) 최대 힙은 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리이다. 우선순위 큐의 삽입 완전 이진 트리를 유지하는 형태로 순차적으로 삽입된다. 삽입 이후에는 루트 노드까지 거슬러 올라가면서 최대 힙을 구성한다.(상향식) 우선순위 큐의 삭제 삭제할 때는 루트 노드를 삭제하.. 2019. 8. 30. 자료구조: 이진 트리(Binary Tree) 이진 트리(Binary Tree)란? 자식 노드가 최대 2개의 자식을 가질 수 있는 트리이다. 트리(tree)는 나무를 거꾸로 뒤집어 놓은 듯한 형태의 알고리즘이다. 루트 노드(root node) : 최상단 노드 리프 노드(leaf node) : 현재 트리 구조의 자식 노드가 없는 최하단 노드 길이(Length) : 출발 노드에서 특정 노드까지의 길이 포화 이진 트리(Full Binary Tree) : 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리 완전 이진 트리(Complete Binary Tree) : 모든 노드들이 왼쪽 자식부터 차근차근 채워진 노드 높이 균형 트리(Height Balanced Tree) : 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이 나지 않는 트리 트.. 2019. 8. 29. 자료구조: 기수 정렬(Radix Sort) 기수정렬이란? 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 알고리즘 비교 연산을 하지 않아 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요한다. 각 데이터의 자릿수를 기준으로 분류하므로 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간복잡도를 갖는다. LSD(Least Significant Digit) vs MSD(Most Significant Digit) LSD 기수 정렬은 가장 작은 자릿수부터 정렬을 진행해 나가는 방식이다. 마지막까지 결과를 알수 없는 것이 단점이지만 프로그래밍에서는 장점이 된다. MSD 기수 정렬은 가장 큰 자릿수부터 정렬을 진행해 나가는 방식이다. 끝까지 가지 않아도 중간에 정렬이 완료될 수 있다는 점이 장점이다. 중간에 데.. 2019. 8. 29. 이전 1 다음
