2학년 (28) 썸네일형 리스트형 [알고리즘] 정렬 알고리즘(2) 선택 정렬 제일 큰 값을 찾아 맨 뒤의 요소와 교체하는 방법을 반복하여 전체를 정렬하는 알고리즘이다. 시간 복잡도는 최선/최악 모두 O(n^2)이다. 삽입 정렬 점진적으로 정렬 범위를 넓혀 나가는 방식으로 정렬하는 알고리즘이다. 새로운 범위에 포함되는 마지막 원소보다 앞을 탐색하며 자신보다 작은 요소를 찾을 때까지 이동하면서 자리를 교환한다. 시간복잡도는 최선으로는 O(n) , 최악으로는 O(n^2)이다. 쉘 정렬 삽입 정렬 알고리즘을 이용하는 정렬 방식으로, 같은 간격에 있는 원소들을 삽입 정렬 원리로 정렬하는 것을 반복한다. 간격의 초기 값을 1/2 씩 줄이며 반복한다. 퀵 정렬 재귀적인 방법으로 문제를 해결하는 알고리즘으로, 피벗 값을 선택하여 피벗 값보다 작은 값들은 왼쪽으로 보내고 큰 값들은 오.. [알고리즘] 정렬 정렬 1.내부 정렬 정렬한 자료를 주기억장치에 저장한 상태에서 저장 1.1. 정렬 방식 1)교환방식: 버블정렬, 퀵정렬 2)삽입방식: 삽입정렬, 셀정렬 3)병합방식: 2-way병합, n-way병합 4)분배방식: 기수정렬 (키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬하는 방식) 5)선택방식:선택정렬,힙정렬 2.외부 정렬 외부 기억장치(하드 디스크)에 대부분의 데이터가 있고, 그 중 일부만 주기억 장치에 저장된 상태에서 정렬 3. 정렬 알고리즘 정렬 알고리즘은 배열의 원소를 원한느 순으로 배치하는 알고리즘을 의미한다. 입력 인자로 정렬할 자료들이 있는 배열의 시작주소, 원소개수, 비교 알고리즘이 필요하며 수행 후에는 배열 내의 자료들이 원하는 순서로 배치된 상태여야 한다. 모든 경우에 대해서 최적.. [자료구조론]힙 & 덱 힙 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리 1)부모노드와 자식노드간에 절대적 대소관계 성립 2)키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립(형제와는 대소관계 정해지지 않음) 최소힙, 최대힙 두가지 종류가 있다. 힙에서의 삽입 연산: 삽입된 값을 완전 이진트리에서의 맨 마지막 위치에 보낸다. 그 후 힙의 성질에 맞ㄱ게 위치를 재배열한다. 힙에서의 삭제 연산: 루트노드에 한해서만 정의된다. 루트노드를 삭제한 후, 완전 이진트리의 맨 마지막 노드를 루트로 보낸 뒤 힙속성에 맞게 위치를 재배열한다. 성능 Binary min heap에서, heap을 구축한 것을 전제로 했을 때 Find Min : O(1) //최소값 탐색 Delete Min: O(log n) //최소.. [자료구조론] 트리 트리 트리 또한 그래프와 마찬가지로 비선형 자료구조이고, 순환 사이클을 갖지 않아 계층적 구조를 표현할 수 있는 그래프의 일종이다. Node: 트리를 구성하고 있는 원소 그 자체를 말한다. Edge: 노드와 노드 사이를 연결하고 있는 선을 말한다. Root: 트리의 최상위 노드이다. Terminal: 자식이 없는 노드를 말하고, Leaf Node라고도 불린다. Internal: 트리의 최하위를 제외한 모든 노드를 말한다. (자식이 있는 노드) Degree: 트리가 가질 수 있는 최대 자식의 수 Successor node: 현재 key값보다 큰 노드 중 가장 작은 노드 Predecessor node: 현재 key값보다 작은 노드 중 가장 큰 노드 Binary Tree 잎노드를 제외한 모든 노드의 자식이 두.. [자료구조론] 그래프 Graph 그래프는 비선형 자료구조로, 정점과 간선의 집합으로 구성된다. G = (V,E) // vertex(정점) - 여러가지 특성을 가질 수 있는 객체를 뜻하고, 노드(node)라고도 한다. edge(간선) - 정점들 간의 관계를 의미하고, link라고도 한다. 방향성 유무에 따라 방향그래프 여부, 가중치 유무에 따라 가중치 그래프, 순환경로 유무에 따라 순환그래프로 나뉜다. 1) 무향 그래프 : 선은 양방향을 의미한다. (A,B) 이든 (B,A)이든 순서에 의미가 없다. 2)방향 그래프 : 선은 일방향을 의미한다. (순서에 의미가 있다) *가중치 그래프: 각 선에 가중치를 부여한 형태의 그래프로, 간선에 비용을 부과하는 형식으로 가중치가 부과될 수 있다. 차수(degree)란 무방향 그래프에서 정점.. [자료구조론] 스택 & 큐 Stack 선형 자료구조의 일종으로, 가장 마지막에 들어간 자료가 가장 먼저 출력되는 LIFO(Last In First Out) 구조를 갖는다. 스택은 기본적으로 push() 함수를 통해 데이터를 저장하고, pop() 함수를 통해 가장 마지막에 저장된 데이터를 꺼내온다. Implementing a Stack - pop() : 스택의 가장 위의 요소를 제거한다. - push(item) : 스택의 가장 위에 요소를 추가한다. - peek() : 가장 위에 있는 요소를 반환해준다. (제거x) - isEmpty() : 스택이 비어있다면 true를 반환한다. *배열과는 다르게, 스택은 요소에 접근하는데 O(1)의 복잡도가 걸리지 않는다. 하지만 요소의 이동이 필요하지 않기 때문에 제거와 추가에서는 O(1) 의 시.. [자료구조론] Linked List 연결 리스트 배열의 삽입/삭제 연산에서 발생하는 비효율성을 해결하기 위해 등장한 자료구조이다. 논리적,물리적으로 순차적인 배열과 달리, 리스트는 논리적 연결만 순차적이다. 즉, 메모리 주소는 서로 상관관계가 없는 포인터를 가지고 있다. 연결리스트는 노드들이 연속적으로 연결되어 나타난다. 단일 연결리스트(Singly Linked List)는 각각의 노드가 다음 노드의 포인터를 가진다. 이중 연결리스트(Doubly Linked List)는 각각의 노드가 다음 노드와 이전의 노드의 포인터를 가진다. 메모리 주소는 상관이 없는 대신, 각 원소가 다음 위치에 해당하는 메모리 주소를 포인터(링크) 형태로 가지고 있는다. 따라서 삽입/삭제시에 해당하는 위치 앞 뒤의 원소에 대한 물리적 주소만 변경하면 된다. 하지만,.. [자료구조론] 배열과 문자열 & 해시테이블 Array 배열은 논리적 순서와 물리적 순서가 일치한다. 따라서 index 값을 통한 원소 접근이 용이하며 구현이 쉽다. 반면, 삽입/삭제 등에 연산 에 불필요한 오버헤드(간접적인 처리시간)가 발생한다. 삭제의 경우 순서를 맞추기 위하여 삭제된 원소 이후의 원소들을 모두 한 칸씩 앞쪽으로 shift 처리하며, 삽입의 경우 삽입하기 이전에 삽입할 위치 이후의 원소들을 모두 한 칸씩 뒤쪽으로 shift 처리하는 과정을 거친다. 따라서 O(n)이다. 한편, 원하는 n번째 원소에 즉시 접근하는 것은 쉽지만 (O(1)) , 어떤 값을 갖는 원소를 찾고 싶을 때 소요되는 시간은 미리 알 수 없으므 로 O(n)이 걸린다. ArrayUst & Resizable Arrays 몇 언어에서는, 배열들이 자동적으로 사이즈가 .. 이전 1 2 3 4 다음
