Computer Science/Data Structures & Algorithms (13) 썸네일형 리스트형 [Lecture 10] Heap / 힙 #Heap 이란 컴퓨터의 기억 장소에서 그 일부분이 프로그램들에 할당되었다가 회수되는 작용이 되풀이되는 영역. 스택 영역은 엄격하게 후입 선출(LIFO) 방식으로 운영되는 데 비해 히프는 프로그램들이 요구하는 블록의 크기나 요구/횟수 순서가 일정한 규칙이 없다는 점이 다르다. 대개 히프의 기억 장소는 지시자(pointer) 변수를 통해 동적으로 할당받고 돌려준다. 이는 연결 목록이나 나무, 그래프 등의 동적인 자료 구조를 만드는 데 꼭 필요한 것이다. 쉽게 말해 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리이다. 짧게 힙(Heap)이라고 줄여서 부른다 영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻을 지니고 있다. 힙은 항상 완전 이진 트리의 형태를 띠.. [Lecture 20] Sorting Analysis / 정렬 알고리즘 분석 #개요 이번 포스트에서는 정렬 알고리즘들의 시간 복잡도 / time complexity를 분석해보자 #Insertion Sort 이제 정렬 알고리즘 하나인 삽입 정렬에 대해 알아보자. 삽입 정렬 알고리즘이란 한 번에 한 개씩 적당한 위치를 찾아 삽입·배치하는 알고리즘이다. 배열 내 데이터를 순회하며 정렬이 필요한 요소를 적당한 위치에 삽입하는 알고리즘이다. 즉 새로운 데이터를 이미 정렬된 데이터들 사이의 적절한 자리에 집어넣는 정렬방식이다. 삽입 정렬 자바 코드: public void insertionSort(T[] A) { int j; for (int p = 1; p 0 && temp.compareTo(A[j-1].. [Lecture 18] Sorting Algorithm / 정렬 알고리즘 #정렬 알고리즘 컴퓨터 분야에서 중요시되는 알고리즘 가운데 하나로 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 알고리즘이다. 실제 컴퓨터 분야에서 사용하는 데이터의 경우 숫자의 순서나 어휘의 순서대로 정렬한 다음 사용해야 되는 경우가 거의 항상 발생하는데 이걸 얼마나 효과적으로 해결할 수 있느냐가 정렬 알고리즘의 핵심이다. 정렬 알고리즘이란 데이터 요소의 집합을 일정한 순서로 배열하는 알고리즘이다. 쉽게 말해 정렬(sort)이란 데이터를 일정한 규칙에 따라 재배열하는 것을 의미한다. 각 요소 내의 1개 또는 복수의 1개 또는 복수의 키값을 바탕으로 하여 배열하는 경우도 있다. 정렬 알고리즘으로는 버블 정렬, 분산 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 등이 있다. [네이버 지식백과 / 나.. [Lecture 16] Weighted Graph / 가중 그래프 #Weighted Graph 수학의 그래프 이론 분야에서, 그래프 번호매김(graph labeling)은 전통적을 정수로 표현되는 라벨을 그래프의 모서리나 꼭짓점, 또는 둘 다에다 붙이는 것이다. 공식으로 표현하면 그래프 G = (V, E)가 주어졌을 때, 꼭짓점 번호매김(vertex labeling)은 V에서 라벨의 집합으로 가는 함수이다. 이런 함수가 정의된 그래프는 꼭짓점-라벨 그래프(vertex-labeled graph)라고 부른다. 유사하게, 모서리 번호매김(edge labeling)은 E에서 라벨의 집합으로 가는 함수이다. 이 경우에, 그래프는 모서리-라벨 그래프(edge-labeled graph)라고 부른다. 모서리 라벨이 순서 집합(예, 실수)의 원소라면, 이 그래프는 가중 그래프(weig.. [Lecture 15] Graph Traversal / 그래프 운행법 #Graph Traversal 그래프 운행법, 그래프 트래버설 또는 그래프 순회란 그래프를 구성하는 모든 정점들을 체계적으로 방문하는 방법이다. 큐를 이용한 넓이 우선 탐색 방법과 스택을 이용한 깊이 우선 탐색 방법이 있다. 또 부모 노드를 먼저 검사하고 왼쪽 노드에서 오른쪽 노드의 순으로 방문하는 방법인 전위 운행법과 왼쪽 노드, 부모 노드, 오른쪽 노드의 순으로 방문하는 방법인 중위 운행법, 왼쪽 노드에서 오른쪽 노드의 순으로 방문한 후 부모 노드를 검사하는 방법인 후위 운행법이 있다. [네이버 지식백과] 그래프 운행법 [graph traversal] 일부 알고리즘은 그래프의 모든 정점을 정확히 한 번 방문해야 한다.정점이 방문되는 순서는 중요할 수 있으며 특정 알고리즘에 따라 달라질 수 있다. 이 .. [Lecture 14] Graph / 그래프 #Graph 그래프는 꼭짓점과 변의 집합을 이루는 순서쌍을 의미하며, 관계를 간선과 정점으로 표현한 구조이다. 간선으로 연결한 두 정점을 '인접(Adjacent)해 있다' 혹은 '이웃 관계'라고 표현하며, 그래프에서 정점들이 연결된 다양한 노선을 경로라고 표현한다. 쉽게 말해 데이터의 원소에 해당하는 정점(Vertex)과 정점간의 관계를 간선(Edge)으로 연결하여 표현한 형태의 자료구조이다. 일반적으로 정점은 원으로 표현하고 변은 화살표나 선분으로 표현한다. 변을 화살표로 나타내는 경우에는 해당 방향으로만 이동할 수 있으며, 이러한 그래프를 유향 그래프(Directed graph)라고 말한다. 반대로 선분으로 표현되는 경우에는 양방향 모두 이동이 가능하며, 이러한 그래프를 무향 그래프(Undirecte.. [Lecture 13] B-Tree / B-트리 #B-Tree Intro 전산학에서 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 쉽게 말해 다방향 탐색 트리이다. 대용량의 파일을 효율적으로 검색하고 갱신하기 위해 고안된 트리 형태의 자료 구조이다. 방대한 양의 저장된 자료를 검색해야 하는 경우 검색어와 자료를 일일이 비교하는 방식은 비효율적이다. B-트리는 자료를 정렬된 상태로 보관하고, 삽입 및 삭제를 대수 시간으로 할 수 있다. 대부분의 이진 트리는 항목이 삽입될 때 하향식으로 구성되는 데 반해, B-트리는 일반적으로 상향식으로 구성된다. n개의 키 (s1,s2,s3...,sn)가 있는 한 노드를 .. [Lecture 7] 점근(asymptotic) 표기법/ Big-O 표기법 #Big-O 표기법 점근 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다. 대표적으로 다음의 세 가지 표기법이 있다. 대문자 O 표기법 알고리즘의 상한 및 상한은 필요한 시간의 가장 많은 양(최악의 경우 성능)으로 정의된다. 빅 오 표기법은 점근적 상한을 설명하는 데 사용된다. 수학적으로, 만약 f(n)가 알고리즘의 실행 시간을 설명한다면, f(n)는 O(g(n)이고, 양의 상수 C가 존재하고 n이 존재한다면, 모든 n >= n0에 대해 0 0과 N > 0이 존재한다면 f(n)는 Ω(g(n)이라고 말한다. Big-Ω는 n의 충분히 큰 값에 대해 함수의 성장률에 대한 하한을 나타낸다. #Bi.. 이전 1 2 다음
