정렬 알고리즘(Sorting Algorithm) 항상 정렬 헷갈리네요. 오름차순으로 정렬했을 때를 가정하고 정리해볼게요. Bubble Sort 인접한 두 개의 데이터를 비교해가면서 가장 큰 값을 배열 맨 끝에 두면서 정렬합니다. 한 턴마다 비교대상 중 가장 큰 값이 그 중 제일 뒤에 가도록 보장합니다. 시간 복잡도 : O(n^2) Selection Sort 앞에서부터 시작하여 해당 수보다 작은 수를 찾고, 만약 찾았으면 그 수랑 swap하고 없으면 (그 수가 가장 작은 수이기 때문에) 그대로 둡니다. 다음은 그 다음 인덱스부터 비교합니다. 한 턴마다 비교대상 중 가장 작은 값이 제일 앞에 가도록 보장합니다. 시간 복잡도 : O(n^2) Insertion Sort index 1부터 시작하여 해당 인덱스 아..
트리란? 부모-자식 관계로 정의하고, 부모에서 자식으로 간선이 이어져있는 유향 그래프를 의미합니다. 트리는 그래프에 속합니다. 용어 노드(node): 트리를 구성하는 기본 원소 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들 리프 노드(leaf node/leaf/terminal node): 자식이 없는 노드 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서 길이(length): 출발 노드에서 도착 노드까지 거치는 ..
n(log(n)) 정렬 불안정 정렬, 안정 정렬은 뭘까요? 정렬 후에 정렬 기준 값이 같은 원소의 상대적인 위치가 바뀌는 것의 유무를 말합니다. 출처 : 제타위키 불안정 정렬의 종류 : Selection, Heap, Quick 안정 정렬의 종류 : Bubble, Insert, Merge, Counting, Radix Quick sort 피봇을 기준으로 왼쪽은 작은값, 오른쪽은 큰값으로 한다는 왼쪽, 오른쪽에서 재귀적으로 다시 실행합니다. 불안정 정렬입니다. 가장 빠릅니다. 다른 n(log(n)) 정렬 중 quick sort가 왜 제일 빠를까요? 데이터의 locality(지역성)가 높기 때문에 그렇습니다. 그럼 locality는 뭘까요? 모든 데이터는 시간 지역성, 공간 지역성이 있습니다. 데이터는 자주 ..
'자료구조' 수업을 최근 계속 들어왔는데 오늘 처음으로 정리해보네요! 오늘은 수업시간에 정렬을 구현해보는 실습을 했는데요. 생각보다 쉽지 않더라구요. 주어진 미션은 다음과 같습니다. 배열 생성하기 그 배열 무작위로 섞기 본인이 구현하고 싶은 정렬방법으로 정렬하기 배열 생성하기 배열을 생성하는 방법은 어렵지 않죠. 보통은 for문의 인덱스를 이용하여 만드는데요. 이번엔 IntStream 을 이용하여 만들어보았습니다. public int[] genArray(int size) { return IntStream.range(0, size).toArray(); } 배열 무작위로 섞기 Collections.shuffle() 를 사용하지 않고 배열을 무작위로 섞는 방법을 생각해봤는데요. 생각보다 쉽지 않..
너비 우선 탐색(BFS) 오늘은 너비 우선 탐색(BFS, Breadth-First Search)에 대해 간략하게 정리해보려 합니다1. 우선 시작하기 앞서 그래프에 대해서 알아야 하는데요. 알고리즘에서 말하는 그래프는 중고등학교 때 수학시간에 배운 x축, y축과 전혀 관련이 없는 것이더라구요. 그래프 알고리즘에서 말하는 그래프는 정점(node)와 간선(edge)를 말합니다. 그래프에 대해 알아야할 것은 여기까지 입니다. 이제는 너비 우선 탐색에 대해 알아보겠습니다. 너비 우선 탐색은 다음과 같은 질문을 해결해줍니다. 정점A에서 정점B로 가는 경로가 존재하는가? 정점A에서 정점B로 가는 최단 경로는 무엇인가? 특히 두번째 질문 '정점A에서 정점B로 가는 최단 경로는 무엇인가' 를 해결해주는 알고리즘으로 유명..
순열(permutation) 어제 알고리즘 수업시간에 순열을 만드는 법을 배웠습니다. 평소 문제를 풀다가 여러 경우의 수를 고려하기 위해 순열 또는 조합이 필요한 경우를 느껴왔기 때문에 수업이 기대되었는데요. 물론 처음부터 순열 소스코드가 바로 이해되지는 않았지만 끝나고 혼자 고민하는 시간을 통해서 어떻게 구성되는지 대략적인 구조를 파악할 수 있었습니다. 오늘 배운 순열 구현 방법은 swap함수와 재귀를 이용하는 방법인데요. 우선 소스코드부터 보도록 하겠습니다. void myswap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void permutation(int[] arr, int d, int n, int..
