극꼼이 이야기 (GG_Tales)

1. 퀵정렬이란? 데이터들 중 한 숫자를 기준점(pivot)으로 정하고, 기준점보다 작은 데이터는 왼쪽으로, 큰 데이터는 오른쪽으로 분류하여 정렬합니다. 재귀용법을 이용해 작은 단위까지 쪼개어 정렬한 후 합치는 방식입니다. 2. 퀵정렬의 구현 병합정렬을 배우고 나니 퀵정렬은 조금 더 쉬웠습니다. public List quickSort(List list) { if (list.Count = list[i]) left_List.Add(list[i]); else right_List.Add(list[i]); } left_List = quickSort(left_List); right_List = quickSort(right_List); left_List.Add(pivot); left_List.AddRange(righ..

이전 포스팅에서 분할 정복에는 병합 정렬과 퀵 정렬이 있다 언급했었는데요, 오늘은 병합 정렬에 대해 공부해봅니다. https://geukggom.tistory.com/169 1. 병합 정렬이란? : 분할 정복 방식의 알고리즘이며, 재귀용법을 이용한 정렬 알고리즘입니다. 병합정렬의 방식을 단계별로 설명하면 다음과 같습니다. 1) 배열을 반으로 쪼갭니다. 2) 1) 과정을 재귀용법을 이용해 반복합니다. 3) 쪼개진 두 배열들을 합병 정렬을 이용해 합치며 정렬합니다. 움짤로 보시면 더 이해가 쉽습니다. 2. 병합 정렬 구현 위에서 설명한 단계별로 구현해보겠습니다. 1) 배열을 반으로 쪼갭니다. int cutNum = list.Count / 2; List leftList = list.ToList(); List ..

1. 동적 계획법(Dynamic Programming(DP))이란? : 처음 계산된 값을 저장(Memoization)하고, 이 값으로 상위 문제를 풀어 나가는 방식(상향식 접근법)입니다. * Memoization(메모이제이션) : 프로그램 실행 시 이전에 계산한 값을 저장하고, 이를 이용해 중복 계산을 하지 않고 전체 실행 속도를 빠르게 하는 기술. * 상향식 접근법 : 가장 최하위의 해답을 구한 후, 이를 저장해 해당 결과값으로 상위 문제를 푸는 방식 2. 분할 정복(Divide and Conquer)이란? : 문제를 가장 작은 사례로 나누고, 각각을 푼 다음(하향식 접근법) 합병하여 문제의 답을 얻는 알고리즘입니다. 일반적으로 재귀함수로 주로 구현(재귀함수를 사용하지 않고, 스택이나 큐를 사용하기도 ..

1. 삽입 정렬이란? : 두번째 인덱스부터 시작해서, 앞으로 이동하면서 다른 인덱스들과 값을 비교해서 자신의 위치에 맞는 곳에 삽입하는 방식의 정렬 알고리즘. 2. 삽입 정렬 구현 GitHub for문을 2번 사용했으므로 시간복잡도는 O(𝑛2)입니다. 최악의 경우에는 𝑛∗(𝑛−1)/2 번 반복해서 코드를 읽습니다. * 버블정렬, 선택정렬, 삽입 정렬 모두 동일한 시간복잡도를 가집니다.

1. 선택 정렬이란? : 데이터에서 최소값을 찾아 맨 앞으로 가져오고, 옮겨둔 데이터를 제외한 나머지 리스트를 같은 방법으로 교체하는 방식의 정렬 알고리즘. 2. 선택 정렬 구현 GitHub for문을 2번 사용했으므로 시간복잡도는 O(𝑛2)입니다. 최악의 경우에는 𝑛∗(𝑛−1)/2 번 반복해서 코드를 읽습니다.

버블 정렬에 들어가기에 앞서, 정렬이 무엇인지 알아보겠습니다. * 정렬(sorting) : 데이터를 정해진 순서대로 나열하는 것. 1. 버블 정렬(Bubble sort) : 인접한 두개의 데이터를 비교해서 앞의 데이터가 더 작게 두 데이터의 자리를 바꾸는 정렬 알고리즘. 2. 버블 정렬 코드 구현 GitHub for문을 2번 사용했으므로 시간복잡도는 O(𝑛2)입니다. 최악의 경우에는 𝑛∗(𝑛−1)/2 번 반복해서 코드를 읽습니다.

* 시간 복잡도 : 알고리즘이 실행되는 상대적인 시간 https://geukggom.tistory.com/159 [알고리즘] 점근 표기법(Asymptotic Notation)과 빅 오의 사용 방법 1. 점근 표기법(Asymptotic Notation) : 시간복잡도를 근사치로 표현한 것입니다. 아래에서 빅 오를 예시로 들어 어떤 식으로 시간복잡도를 계산하는지에 대해 알아볼건데, 컴퓨터의 성능과는 관계없 geukggom.tistory.com 1. 공간 복잡도란? : 알고리즘이 실행될 때 필요한 저장 공간. 효율적인 알고리즘은 시작부터 결과가 나올 때까지 실행에 걸리는 시간이 짧고(작은 시간복잡도), 연산하는 컴퓨터 내의 메모리 자원을 덜 사용하는 것(작은 공간 복잡도)입니다. 시간복잡도와 공간복잡도는 반비..

1. 점근 표기법(Asymptotic Notation) : 시간복잡도를 근사치로 표현한 것입니다. 아래에서 빅 오를 예시로 들어 어떤 식으로 시간복잡도를 계산하는지에 대해 알아볼건데, 컴퓨터의 성능과는 관계없이 두 알고리즘을 비교해서 어떤 알고리즘이 더 나은 알고리즘인지, 더 빠른 알고리즘인지를 가늠할 때 사용합니다. 2. 점근 표기법의 종류 1) 빅 오 (Big O : Ο) : 알고리즘이 최악으로 실행될 경우(아무리 늦더라도 이 정도의 성능을 보장한다는 것을 의미)의 성능을 표현할 때 사용. 알고리즘의 성능을 표현하는데 가장 많이 사용. = 최악의 경우의 수에 어떤 성능을 내는지 궁금해하기 때문. 2) 빅 오메가 (Big Omega : Ω) : 알고리즘이 가장 최선으로 실행될 경우의 성능을 표시. 3)..

1. 그래프(Graph)란? 그래프란 정점과 선으로 이루어진 자료구조입니다. 더 자세한 내용은 아래 링크를 클릭해주세요. https://geukggom.tistory.com/8 [자료구조] Graph란? 1. Graph란? 정점(vertex(V))과 그 정점을 연결하는 간선(edge(E)을 하나로 모아 놓은 자료구조. 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조입니다. G = (V, E) (ex) 지도, 지하철 노선도, 전기 geukggom.tistory.com - 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 2. BFS, DFS란? BFS : Breadth-First Search = 너비 우선 탐색. 인접한 노드를 먼저 탐색하는 방법. DFS :..