재민

내부 정렬 중 버블정렬은, 인접한 두개의 원소를 비교하여 자리를 교환하는 방식이다. 첫번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬되게 된다. (마지막으로 배열되는 원소는 비교를 끝까지 진행하므로!) 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 하여 bubble 정렬이라 지어졌다고 한다. 버블 정렬의 경우, 선택 정렬과 달리 best case와 worst case로 나누어 보아야 한다. best case는 이미 정렬이 완료된 상태로, 비교만 진행하고 자리 교환은 이루어지지 않아도 된다. worst case는 자리 교환이 이루어져야 하기 때문에 시간이 더 필요하다. ..

Sorting은 순서없이 배열된 자료를 오름차순/내림차순 순서로 재배열 하는 것으로, sorting상에서 key는 자료를 정렬하는데 사용하는 기준이 되는 특정 값을 뜻한다. 내부정렬 중 선택정렬은, 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬하는 sorting방법으로서, 전체 원소들 중 가장 작은 원소를 찾아 첫번째에 위치 > 두번째로 작은 원소를 찾아 두번째에 위치 를 마지막 원소까지 진행하는 방식이다. 선택정렬의 경우 시간복잡도는 O(n^2)가 된다. (비교 횟수는 첫번째 원소는 n개, 두번째는 n-1개 ...1개까지 비교하므로 전체 합은 n^2). 어느 경우에나 비교 횟수가 같은 것이 특징이다. [python 코드] def selection_sort(arr):..

다익스트라 알고리즘은 최단 경로 알고리즘 중 가장 많이 사용되는 알고리즘으로, 무방향 그래프와 방향 그래프 모두에서 사용 가능한 알고리즘이다.모든 간선은 음이 아닌 비용을 가진다는 가정을 바탕으로, 시작 정점으로부터 G의 모든 다른 정점까지의 최단 경로를 구하는 것을 목표로 한다. 다익스트라 알고리즘의 개념은 다음과 같다. 시작 정점 v에서 정점 u까지의 최단 경로 dist[u]를 구해 정점 u가 집합 S에 추가되면 새로 추가된 정점 u에 대해 단축되는 경로가 있는 지를 확인한다. 현재 알고 있는 dist[w]를 새로 추가된 정점 u를 거쳐서 가는 dist[u] + cost[u][w]를 계산한 경로를 비교해 경로가 단축되면 dist[w]를 단축된 경로값으로 수정함으로써 최단 경로를 찾는다. [python..

Graph는 연결되어 있는 원소들 사이의 다대다 관계를 표현하는 비선형 자료구조로서, 버스노선도나 지하철 노선도와 같이 여러 원소들이 맞물려 있는 경우에 사용하는 자료구조형이다. 그래프는 두개의 집합 V와 간선 E로 구성되어 있다. 표기는 G = (V,E)로 한다. 그래프는 무방향 그래프와 방향그래프, 부분그래프, 가중 그래프로 나눌 수 있다. 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프로서, 간선을 나타내는 쌍에 순서가 없다. 즉 간선을 통해서 양방향으로 갈 수 있는 그래프이다. 방향 그래프는 모든 간선이 방향을 가지는 그래프로서, 방향은 정점의 쌍 의 정점의 순서로 표시한다. 간선을 통해서 한 쪽 방향으로만 갈 수 있다. 부분그래프는 원래의 그래프에서 정점이나 간선을 일부만 제외하여..

Tree는, 하나 이상의 노드로 이루어진 유한집합으로서, 하나의 루트 노드와 분리 집합으로 분할된 다른 노드들의 집합이다. 앞서 다루었던 다른 자료구조와 달리(stack,queue,linkedlist) 원소들 간에 1:n 관계를 가지는 비선형 자료구조이며, 원소들 간에 계층 관계를 가지는 계층형 자료구조이다. [Tree의 주요 용어 및 개념] node: 트리의 구성 요소 서브트리: 하나의 노드와 그 노드들의 자손으로 이루어진 트리 노드의 차수: 노드의 서브트리 개수 루트 노드: 부모가 없는 노드(최상위 노드) 단말 노드: 자식이 없는 노드, 차수 0 형제 노드: 부모가 같은 자식들 트리의 차수: max{노드의 차수} 노드 레벨: 트리의 각 층의 번호 트리의 높이: max{노드 레벨} 조상: 루트까지의 경..

연결리스트를 이용하여 큐를 구현하는 예제이다. Node class와 Queue class를 이용하여 queue를 구현하였다. class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.front = None self.rear = None def is_empty(self): return self.front is None def enqueue(self, data): new_node = Node(data) if self.is_empty(): self.front = self.rear = new_node else: self.rear.next = new_node self.rear..

스택을 구현하기 위해 배열을 사용할 경우, 일차원 배열 stack[MAX_STACK_SIZE] 를 사용한다. 스택의 변수 top은 가장 최근에 삽입된 요소를 가리키는 변수로, 초기값을 -1로 세팅한다(공백 스택을 의미) 스택에서 가장 먼저 삽입된 요소는 stack[0]에, 가장 최근에 삽입된 요소는 stack[top]에 저장된다 (스택의 개념) [c코드로 스택 구현] #include #define MAX_STACK_SIZE 100 typedef struct { int stack[MAX_STACK_SIZE]; int top; } Stack; // 스택 초기화 void initializeStack(Stack *s) { s->top = -1; // 초기값으로 -1을 설정하여 공백 스택을 나타냄 } // 스택이..

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있어서, 양방향으로 탐색이 가능하며, 삭제 시 양쪽의 연결을 수정해야 한다. Doublely Linked List에서 노드의 삭제는 다음과 같은 순서로 이루어진다. 1) 삭제할 노드의 오른쪽 노드와 왼쪽 노드를 탐색한다. 2) 삭제할 노드의 오른쪽 주소를 삭제할 노드의 왼쪽 노드의 rlink에 저장한다. 3) 삭제할 노드의 왼쪽 노드 주소를 삭제할 노드의 오른쪽 노드의 llink에 저장한다. 4) 삭제할 노드를 삭제한다. [코드로 구현하기] #include #include // 이중 연결 리스트의 노드 구조체 정의 struct Node { int data; struct Node* llink; // 왼쪽 노드를 가리키는 포인터..

Doubly Linked List는 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트이다. linked list에서와 마찬가지로 중간노드, 첫번째 노드, 마지막 노드 삽입을 나누어서 보도록 하겠다. https://imsunbow.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Linked-List-%EC%82%BD%EC%9E%85%EC%A4%91%EA%B0%84-%EB%85%B8%EB%93%9C-%EC%B2%AB%EB%B2%88%EC%A7%B8-%EB%85%B8%EB%93%9C%EB%A7%88%EC%A7%80%EB%A7%89-%EB%85%B8%EB%93%9C%EB%A1%9C-%EC%82%BD%EC%9E%85 [같이 보면 좋은 자료: linked lis..

Linked List에서 삭제는 다음과 같은 순서로 이루어진다. 1) 삭제할 노드의 앞 노드를 찾는다. 앞 노드를 찾는 이유는 크게 두가지인데, 연결관계를 해제하기 위해서이자 노드를 효율적으로 찾아 해제시키는 방법이기 때문이다. 2) 앞 노드의 링크필드에 삭제할 노드의 링크 필드값을 저장한다. 3) 삭제할 노드를 삭제하고, 메모리를 해제한다. 삭제 연산을 c로 구현하면 다음과 같다. #include #include // 단일 연결 리스트의 노드 정의 struct Node { int data; struct Node* next; }; // 연결 리스트의 헤드를 전역 변수로 선언 struct Node* head = NULL; // 연결 리스트에 노드 추가 void insertNode(int val) { str..