본문 바로가기

CS ﹒ Algorithm/Algorithm

Minumum Spanning Tree(최소 신장 트리) 구하기, 관련 문제 풀이
CS ﹒ Algorithm/Algorithm 2023. 3. 3. Minumum Spanning Tree(최소 신장 트리) 구하기, 관련 문제 풀이 최소 신장 트리를 구하기 위해서는 기본적으로 UnionFind 알고리즘에 대한 이해가 필요하다. 몰라도 풀 수 있지만 UnionFind를 이용하는 게 더 효율적이다. 굉장히 쉬우니까 빠르게 학습하고 오자. https://7357.tistory.com/342 UnionFind 알고리즘과 경로 압축, 그리고 관련 문제 UnionFind 알고리즘은 서로소 집합을 표현하기 위한 알고리즘이다. 일반적으로 MST(Minumum Spanning Tree)를 구할 때 사용한다. 정말 별 거 없다. 어떤 노드 6개가 있다고 가정해보자. 이 때, 1-2, 2-3, 4-5, 5-6 7357.tistory.com MST도 쉽다. 다익스트라보다 더 쉽다. MST란 그래프 이론에서 사용되는 개념으로, 최소한의 비용으로 모든 노드..
스윙스만큼(?) 빠른 기수 정렬(Radix Sort)에 대해 친절하게 알려드림
CS ﹒ Algorithm/Algorithm 2022. 11. 7. 스윙스만큼(?) 빠른 기수 정렬(Radix Sort)에 대해 친절하게 알려드림 * 중요 : Big-O 표기법에서 상수 인자는 무시한다. 계수 정렬과 기수 정렬은O(N)의 시간 복잡도를 가지고 있으나 상수 인자 크기에 따라(자리수에 따라) 생각만큼 빠르지 않을 수 있으며, 리얼 월드에서는 Cache Hit까지 고려하면 계수 정렬을 사용할 수 있는 상황에서도 O(nlogn)의 시간 복잡도를 가진 Quick sort보다 빠르지 않을 수도 있다. 다만 기수 정렬은 Bucket sort와도 관련이 있으므로 구현에 대해서는 한 번 배워놓는 것을 추천한다. 간만에 새로운 정렬 알고리즘 하나 배워왔다. 마지막에 올렸던 Counting sort의 형뻘 정도 되는 Radix sort, 계수 정렬이다. Counting sort가 뭔지 궁금하다면 아래 글을 읽어보자. 사실 굉장히 쉬워서 굳이 읽지 않아..
계수 정렬(Counting sort)에 대해 알아보자
CS ﹒ Algorithm/Algorithm 2022. 8. 8. 계수 정렬(Counting sort)에 대해 알아보자 계수 정렬 ( == Counting sort, 카운팅 정렬, 카운팅 소트 ) 1. 계수 정렬은 비교 정렬이 아니며, 정렬할 배열의 최대값을 기준으로 새로운 배열을 만들어 값을 카운팅하여 정렬한다. 2. 계수 정렬의 시간 복잡도는 O(n)으로 일반적으로 가장 빠르다고 알려진 병합 정렬(Merge sort), 퀵 정렬(Quick sort)와 비교했을 때 우위에 있다. 3. 그러나 사실 O(n)의 시간 복잡도는 최적의 경우일 뿐이고 최대값을 기준으로 카운트할 배열을 생성하기 때문에 시간 복잡도는 최대값에 비례해서 끊임없이 높아진다. 게다가 그만한 배열을 사용하게되니 메모리 낭비는 덤이다. 4. 계수 정렬은 최대값의 제한이 없거나 너무 큰 경우에는 극도로 비효율적이고, 또한 배열 인덱스를 이용하여 카운트하는 특..
선형 탐색(Linear search)과 이진 탐색(Binary search)에 대해 알아보자 (Feat.JAVA)
CS ﹒ Algorithm/Algorithm 2022. 8. 4. 선형 탐색(Linear search)과 이진 탐색(Binary search)에 대해 알아보자 (Feat.JAVA) 고양이도 배울 수 있을 만큼 쉬운 선형 탐색과 이진 탐색에 대해 알아보자. 선형 검색 알고리즘 ( == Sequential search algorithme, Linear serach algorithm, 순차 검색, 선형 탐색) 가장 원시적인 형태의 데이터 탐색 알고리즘이다. 이것은 리스트에서 찾으려고 하는 값을 맨 앞부터 끝까지 차례대로 찾아 나가는 것이다. 검색할 리스트의 길이가 길면 길수록 비효율적이지만 단순하여 구현이 굉장히 쉽고, 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있다. 선형 검색은 데이터를 찾기 위해 데이터를 하나씩 모조리 검사하므로 시간 복잡도는 최악의 경우(worst) O(n)이다. 예시) 어렵게 생각할 게 전혀 없다. 그냥 임의의 배열에서 반복문으로 특정 값을 찾고자 한다..
퀵 정렬(Quick Sort)에 대해 알아보자 (feat. JAVA)
CS ﹒ Algorithm/Algorithm 2022. 8. 1. 퀵 정렬(Quick Sort)에 대해 알아보자 (feat. JAVA) 퀵 정렬(Quick Sort) ? 퀵 정렬은 다른 원소와의 비교만으로 정렬을 수행하기 때문에 비교 정렬에 속한다. 퀵 정렬은 평균적으로 O(n log n)번의 비교를 수행하지만 최악의 경우 O(n²)번의 비교를 수행한다. 원소들 중에 같은 값이 있는 경우 같은 값들은 정렬 이후 초기와 순서가 달라질 수 있기 때문에 불안정 정렬이다. ( 예 : 5₁, 5₂, 3, 2, 1를 정렬하면 1, 2, 3, 5₁, 5₂ 이 된다. ) 실제 임상 자료(real-world data) 정렬 시 가장 빠른 알고리즘이다. * 퀵 정렬은 일반적인 보편적으로 가장 빠른 정렬 속도를 보여주는 분할-정복 알고리즘 중 하나이지만 오름차순, 내림차순 등 이미 정렬되어 있는 배열의 재정열에 사용 시 최악의 성능을 보여주고 일반적으로 우..
거품 정렬(Bubble Sort)에 대해 알아보자 (feat. JAVA)
CS ﹒ Algorithm/Algorithm 2022. 7. 14. 거품 정렬(Bubble Sort)에 대해 알아보자 (feat. JAVA) 거품 정렬(Bubble Sort)? 1. 거품 정렬은 두 인접한 원소를 검사하여 반복, 순차적으로 정렬하는 방법이다. ( 비교 정렬 ) 2. 거품 정렬은 선택 정렬과 함께 정렬 알고리즘에서 최악의 성능을 보여준다. ( 시간 복잡도 O(N＾²) ) 3. 또한 거품 정렬은 제자리(in-place)정렬이기 때문에 추가적인 메모리 사용량을 필요로 하지 않는다. 값을 바꾸기 위한 임시 공간이 필요하지만 정렬 알고리즘에서 정렬 항목 외에 O(1)개의 메모리만 필요한 것은 제자리 정렬로 간주한다. 4. 단순한 원리로 작동하기 때문에 구현이 굉장히 쉽다. 종합적으로 구현하기 쉽고 단순하나 성능이 너무 좋지 않기 때문에 실무에서 사용하면 기다리다가 혼자 사무실을 지키게 될 수도 있는 알고리즘이다. 거품 정렬의 예시 사실..
피보나치 수열에서 n번째 수를 쉽게 구하는 세가지 방법. (Feat. Java)
CS ﹒ Algorithm/Algorithm 2022. 6. 25. 피보나치 수열에서 n번째 수를 쉽게 구하는 세가지 방법. (Feat. Java) 첫 달에는 새로 태어난 토끼 한 쌍만 존재한다. 두 달 이상이 된 토끼는 번식 가능하다. 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다. 토끼는 죽지 않는다. 10개월째에 총 몇 쌍의 토끼가 존재하는가? 사각형 채우기나 귓바퀴 예제보다는 토끼가 제일 와닿는 예시인 것 같다. 나는 사칙연산 이외의 수학을 사용해보지 않은지 10년이 넘은 사람이라 공식을 봐도 무슨 말인지 잘 이해되지 않아서 아래의 정의만 보고 코드를 작성했다. F[0] = 0; F[1] = 1; F[n] = F[n-1] + F[n-2]; 어? 익숙하다. 누가봐도 코드에 갖다 붙이기 좋은 형태다. // 배열 활용 예시 public static int fibonacci(int num) { int[] arr = new int[num]; i..
0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체
CS ﹒ Algorithm/Algorithm 2022. 6. 24. 0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체 고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 간편한 방법이다. 알고리즘 중에 그나마 쉬운 편에 속한다. (1) 우선 0과 1은 소수가 아니기때문에 제외한다. (2) 소수인 2를 제외한 2의 배수를 모두 제외한다. (3) 소수인 3을 제외한 3의 배수를 모두 제외한다. (4) 소수인 5를 제외한 5의 배수를 모두 제외한다. (5) 소수인 7을 제외한 7의 배수를 모두 제외한다. (6) 위의 과정을 반복하며 제외되지 않은 소수 n을 제외한 n의 배수를 제외.. 무한 반복 글로만 읽어도 그럭저럭 이해가 되겠지만 아래의 친절한 그림을 보고나면 더욱 와닿을 것이다. 이 알고리즘을 JAVA로 작성해보자. public static String test(int num) { // 인자로 제공되는 수와 인덱..

티스토리툴바