Algorithm/PS 알고리즘 정리21 [알고리즘] 불확실한 상황을 현명하게 사용하는 코드 이번글은 학교 알고리즘 수업 시간에 Randomized algorithm을 배우면서 느낀 점을 남기는 글입니다. 어떤 알고리즘을 설명한다기보다는, 제가 느낀 점을 남겨보는 글입니다. 1. 불확실한 상황을 이용해 볼 수 없을까? 우리가 코드를 작성할 때 모든 상황이 확실하게 결정된 상황에서만 진행하는 경우는 거의 없다, 어쩌면 이는 코드뿐만 아니라 대부분의 사람들이 하루를 살아가는 자연스러운 방법(?) 중 하나일지도 모른다. 물론 우리는 계획이라는 것을 만든다. 해당 계획을 통하여 시간이 얼마나 걸릴지 예측할 수도 있고, 얼마나 많은 리소스가 필요한지 또한 측정할 수 있다. 하지만 이는 어느 정도의 사전 정보가 있다는 가정 하에 가능할 것이며, 당장 첫 시도를 해야 하거나, 상황 자체가 너무나 불확실하다면.. Algorithm/PS 알고리즘 정리 2023. 12. 14. [알고리즘] 최소 공통 조상 LCA(Lowest Common Ancestor) 1. LCA란? LCA(Lowest Common Ancestor)는 주어진 두 노드 a와 b의 최소 공통 조상을 찾는 알고리즘입니다. 예를 들어 다음 그림과 같은 트리가 있다고 했을 때, 12번과 15번 노드의 최소 공통 조상 LCA는 5번 노드가 됩니다. 우선 두 노드의 LCA를 찾는 가장 간단한 O(N)이 걸리 방법으로 2가지 정도가 있다. 2가지에 대하여 간단하게 알아본 후, 이글의 Main 목표인 O(LogN) 안에 해결하는 알고리즘에 대하여 알아보자. 2. O(N) 알고리즘 2-1) 두 Node의 Level을 통일시키는 방식 A와 B의 깊이가 다를 경우 더 깊은 정점의 부모를 따라 하나씩 올라가면서 A와 B의 깊이를 맞춘다. 위의 결과 A와 B가 같다면 A(or B)가 최소 공통조상이다. A !.. Algorithm/PS 알고리즘 정리 2023. 12. 8. [알고리즘] HeapSort보다 QuickSort가 더 빠른 이유 1. 왜 HeapSort보다 QuickSort가 현실적으로 더 빠를까? HeapSort와 QuickSort는 대표적으로 O(NlogN)안에 동작하는 정렬알고리즘이다. 하지면 현실성면에서 QuickSort가 더 빠르다는것은 익히 들어 알고있을 것 이다. 왜 그런것 일까? 이에 대하여 알아보자 1-1) 알고리즘의 성능 요인 크게 정렬 알고리즘에서 성능을 미치는 원인은 크게 3가지로 볼 수 있다. 비교 및 스왑을 수행하기 위한 반복자(loop) = 반복자가 어떻게 구현되어있는가의 문제 유효 접근 시간 (지역성) 메모리 소비량 1번의 경우 대부분 시간복잡도를 측정할때 고려하는 요소라, O(NlogN)이라는 표기안에 포함되어있는 개념이다. 따라서 HeapSort와 QuickSort의 차이는 2번인 유효 접근 시간.. Algorithm/PS 알고리즘 정리 2023. 10. 13. [알고리즘] 빅오(Big-O)표기법 수학적 이해 1. Big-O를 수학으로 이해하기 이번 코드스쿼드 멘토를 진행하면서, Big-O 표현식에 대한 과제가 있었다. 물론 이에 대한 직관적인 이해까지는 대부분 하게 된다. 하지만, 성장을 원하는 개발자라면 한 번쯤 수학의 관점에서 이해할 수 있어야 된다 생각한다! 그만큼 Bio-O는 중요한 내용이다! 따라서 학생들에게 이를 설명하기 위한 12분 정도의 영상을 하나 만들었는데, 좀 부족하지만... 나름 잘? 설명했다 생각하여 유튜브 영상으로 남겨두었다! https://youtu.be/OF-BsdcFJ8U (3:49, 5:59, 7:52초 에 N제곱 이라 말한 부분 N제로 입니다 ㅎㅎ) Algorithm/PS 알고리즘 정리 2022. 11. 10. [알고리즘] L-트로미노 1. 트로미노란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 트로미노는 크기가 같은 정사각형 3개를 변끼리 붙여 만든 다각형 이다. 따라서 다음과 같은 모양이 가능하다. 2. 트로미노로 구성된 불완전 보드 증명 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 트로미노중에서 L 모양의 트로미노를 한 변의 길이가 2^n인 정사각형에 배치하는 것이 목표이다. 결론부터 말하자면, L-트로미노는 1x1 한 칸을 제외하고, 한 변의 길이가 2^n인 정사각형을 항상 채울 수 있다. 위 가정의 증명은 다음과 같이 수학적 귀납법으로 가능하다. 1) Base 단계 (n = 1일때) 만약 n = 1 이면 2x2의 불완전 보드는 트로미노 자신이며, 하나의 .. Algorithm/PS 알고리즘 정리 2022. 2. 10. [알고리즘] 비트마스크 조합, 부분수열 예전부터 비트마스크 활용하는거 정리 한번 해야지... 해야지 하다 안해서... 이번에 정리해본다. 먼저 부분수열부터 문제를 통하여 알아봅시다. 1. 비트마스크를 활용하여 부분 수열 구하기 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 위 백준 문제를 통하여 설명해보겠습니다. 문제의 예시처럼 5개의 원소가 있다고 해봅시다. -7 -3 -2 5 8 각 원소 하나마다 (포함 or 미포함) 둘중 하나.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] next_permutation : 다음 순열 next_permutation (다음 순열 구하기) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 ▶ 우선 순열의 특징을 먼저 살펴봅시다! A라는 집합의 원소가 [1, 2, 3, 4] 라고 해보자. A의 순열은 다음과 같다. 1 2 3 4 (오름차순) : 첫 순열 1 2 4 3 1 3 2 4 1 3 4 2 ... 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 ... 4 3 2 1 (내림차순) :마지막 순열 오름차순으로 시작했던 순열이, 최종적으로 내림차순으로 배열되어 끝나게 된다. 총 N! 개의 서로 다른 순열이 있다. 1 2 로 시작하는 순열인 1 2 ? ? 의 마지막 순열의(내림차순) 다음 순열을 어떻게 구할까? 1 2 ? ? 의 마지막 순열은 1 2 4 .. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] Two Pointers Algorithm : 투포인터 알고리즘 Two Pointers Algorithm " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 투 포인터 알고리즘은 기본적으로 1차원 배열상에서 배열을 가리키는 포인터 2개를 이용하는 방법 입니다! (포인터 라고 해서 C의 그 포인터를 사용한다는 것 이 아닌, 배열의 어느 한칸을 가리키는 용도로 사용하는 것을 의미합니다) 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 대표적인 문제로 백준의 2003번이 있습니다. 이 설명을 보기전 문제를 먼.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] Sweeping Algorithm : 라인 스위핑 알고리즘 Sweeping Algorithm " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 라인 스위핑 알고리즘은 무엇일까? 사실 개념 자체는 매우 단순하다. 공간이나 직선 상에서 한쪽 시작점을 기준으로 반대편 종료지점 까지 scan하면서 지나가는데, 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단기준이 되는 기준 을 적용해 주면 정답이 구해지는 형태입니다. 이처럼 알고리즘의 구조 자체는 간단합니다. 즉, 스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 해야한다. 대표적인 문제로 백준의 선 긋기 문제가 있습니다. 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] Counting inversions Counting inversions " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 예를들어 배열A에 1, 2, 3, ... n 의 수가 무작위 순서로 들어있다고 해보자. 이 수들에서 2개의 무작위 수를 생각했을 때, 그 순서 대비 크기가 역전되어 있는 두 수의 쌍이 몇개가 되는지를 구해보자. 예를 들어 A {2, 3, 6, 4, 1, 7}이 있을때, 크기가 역전된 쌍은 (2, 1), (3, 1), (6, 4), (6, 1), (4, 1) 이 있다. 따라서 Inversion 된 쌍의 수는 5개 이다. 이런 Inversion된 쌍의 수를 어떻게 구해야 할까? 직관적으로 떠오르는 직접다 for문 돌면서 확인하는 방식은 O(n^2)이 걸릴것이 눈에 훤하다... 이럴때 Merge.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] lower_bound, upper_bound : C++ ⭐ 조건 : 탐색을 진행할 array, vector는 오름차순으로 정렬되어 있어야 한다. lower_bound " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 lower_bound(3)을 진행하고 싶다. 배열 arr의 첫 시작지점 부터 탐색하면서 처음으로 3이 나오는 배열의 위치(Iterator)를 반환한다. 즉, 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위한 용도이다. 위치를 반환한다고 한 이유는 lower_bound의 반환형은 Iterator 이기 때문이다. 실제로 몇 번째 인덱스인지 알고 싶다면, 아래 코드와 같이 lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 된다. #include #incl.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] 에라토스테네스의 체 : 소수 판별법 에라토스테네스의 체 (Sieve of Eratosthenes) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이 방식은 지정됨 범위네에서 대량의 소수를 한번에 구할때 유용하다. 예를 들어 121 이하의 소수를 모두 구해야 한다고 해보자. 어떻게 해결해야 할까? 결론부터 말하면 121의 제곱근, 즉 11 이하의 소수 n에 대하여 n의 배수들은 전부 제외시키면 된다. n의 배수라는 말 자체가 소수가 아니다. 아직 이해가 잘 안갈 수 있다. 다시 설명해 보자. 121의 제곱근인 11이하의 수 들을 생각해보자. 일단 2는 소수니 제거하지 않는다. 2를 제외한 모든 2의 배수 4, 6, 8, 10, ..., 120 에 해당되는 수들은 전부 제거하면 된다. 이들은 소수가 아니다. .. Algorithm/PS 알고리즘 정리 2022. 1. 21. 이전 1 2 다음
