자료구조48 [자료구조] Selection Sort 증명 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 선택정렬에 대하여 증명하였다. 알고리즘에 관한 증명들을 먼저 알려주시고 있는데, 이후에 연결리스트나, 스택 등을 설명해주신다 하셨다. Sorting의 증명 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 선택정렬을 증명하기에 앞서서, 우선 정렬 자체를 어떻게 증명할것인가? 에 대하여 답해보고 시작해보자. ▶ 입력으로는 a[0], a[1], ..., a[n-1] 의 집합이 들어온다. ▶ Sorting이 완료된 후 다음이 만족되어야 한다. sorting이 끝난후 배열에 저장된 값을 b[0], b[1], ..., b[n-1] 이라고 하자. - 조건.. CS/Data Structure (2021-1) 2022. 1. 22. [자료구조] Binary Search 증명 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 이번 글은 다들 아는 이진탐색에 대한 증명을 배웠다. 사실 이진 탐색 알고리즘 자체는 직관적이고, 이해하기가 쉽다. 문제는 이 당연한 것을 증명하려고 따지다 보니까 머리가 터지는 기분(살아있음에 감사함을)이 들었다. 이런거 증명해서 어디다 쓰지? 라고 생각할수도 있지만, 이런건 학생 신분일때 한번은 해봐야 향후 나의 발전에 큰 도움이 될거라 믿어의심치 않는다. Binary Search 의 증명 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 이진탐색의 코드를 확인해 보자. 아 그리고 이진탐색은 항상 sorting되어있어야만 한다. int.. CS/Data Structure (2021-1) 2022. 1. 22. [자료구조] 수학적 귀납법 증명 해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. 다들 아는 일반적인 수학적 귀납법 설명하려고 이글 쓰는것이 아닙니다. 사실 귀납법 자체는 고등학교만 정상적으로 나왔으면 다 아는내용이다. 문제는 다음 2가지 측면에서 교수님의 가르침에 큰 놀라움을 얻었기에 이를 공유하고자 글을 써본 것 이다. 1) P(n-1)을 왜 참이라고 가정하는가? 참인지는 어찌알지?? 2) 귀납법을 통해 재귀함수를 어떻게 인식해야 하는가? 수학적 귀납법 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 ● 수학적 귀납법의 기본형 (1) Base: P(1)이 참이고 (2) Step: P(n-1) -> p(n) 이 참이라면 .. CS/Data Structure (2021-1) 2022. 1. 22. [알고리즘] 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. [알고리즘] 최대공약수(GCD), 최소공배수(LCM), 유클리드 호제법 최대공약수 GCD(Greatest Common Divisor) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 최대공약수는 두 자연수가 공통으로 갖는 약수들 중에서 가장 큰 값을 의미한다. 예를들어 24와 18 있다고 해보자. 최대공약수는 6이 된다. 최소공배수 LCM(Least Common Multiple) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 최소공배수는 두 자연수들의 배수들 중에서 공통된 가장 작은수를 말한다. 참고로 최소공배수는 최대공약수를 통하여 바로구할 수 있다. 최소공배수 = 두 자연수의 곱 / 최대공약수 가 적용된다. 예를 들어 24와 18의 최소공배수는 72 이다. 유클리드 호제법 (Euclidean Algorit.. 카테고리 없음 2022. 1. 20. [알고리즘] 트리의 지름 : Diameter of Tree 트리의 지름 이란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 트리의 지름은 두개의 말단노드간의 최장거리를 의미한다. 각각의 정점을 u, v 라고 한다면 이들간의 거리는 d(u, v) 라고 함수로 나타낼 수 있으며, 최장거리(지름)는 이러한 d(u, v) 값들중 최대인 Max d(u, v)라고 할 수 있다. 트리의 지름을 찾는 알고리즘 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 BFS(node) 를 통하여 node로 부터 가장 멀리있는 node를 구한다고 해보자. 이 방식은 greedy 방식에 해당된다. 1. 임의의 시작 정점 s로부터 가장 멀리있는 정점인 u를 BFS(s)로 구한다. (DFS도 가능) 2. 이렇게.. Algorithm/PS 알고리즘 정리 2022. 1. 20. [알고리즘] Bipartite Graph : 이분 그래프 이분 그레프 (Bipartite Graph) 란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 학교에서 공부할때 필기한 내용을 먼저 보인후, 이를 내가 설명하여 보겠다. 이분 그레프란 정점의 집합을 2개의 독립적인 집합으로 나눌 수 있으며, 나눠진 집합에서는 서로다른 집합 사이에만 간선이 존재하는 그레프를 의미한다. 즉 같은 집합 내부의 정점간에는 간선이 있으면 안된다. 이를 그림으로 표현하면 다음과 같음 그레프를 의미한다. 집합이 오른쪽(V)과 왼쪽(U) 2개의 집합으로 나뉘어 졌다. 간선들의 양끝 정점(u와 v) 또한 서로다른 집합에 포함되어있다. 정점 u는 집합 U에, 정점 v는 집합 V에 포함되어야 하는 것! 추가적으로 그림에는 없지만, 한쪽 집합에 그냥 .. Algorithm/PS 알고리즘 정리 2022. 1. 20. 이전 1 2 3 4 다음
