자료구조론47 [알고리즘] 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. [서평] 윤성우의 열혈 자료구조 저의 돈으로 직접사서 직접 완독해본후 써보는 후기입니다. 따라서 장점은 장점대로 칭찬할것이며, 단점은 단점대로 언급할 것 입니다. 윤성우의 열혈 자료구조 저자 : 윤성우 출판 : 오렌지미디어 발매 : 2012.01.18. 2020/8/1 ~ 2020/12/7 (학교 수업과 병행하여 전반적인 자료구조론에 이 책으로 대해 독학하였습니다.) 1) 책의 표지 2) 단원별 구성 3) 읽은소감 우선 저의 글의 앞부분만 보는 분들을 위해 먼저 간단히 3가지에 대해 답해보겠습니다. Q 자료구조를 공부하기 전에 필요한 C언어 수준/ 지식은? => 최소한 C언어 문법은 다 알고있으셔야 합니다. C를 모른다면 코드를 전혀 이해하실수 없을 것 입니다. C언어 기초책이 아닌 C언어 라는 도구를 사용한 자료구조에 관한 책 입니다.. Life/Book Record 2022. 1. 20. [알고리즘] Union Find 알고리즘 : 경로 압축 기존에도 Union Find 알고리즘을 사용하기는 했지만, 경로 압축을 하고있지 않아 시간이 조금더 걸리는 문제가 있었다. 간단하게 경로압축을 할 수 있는 방법을 배워 글을 써본다. Union & Find " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 기본적인 Union Find 알고리즘의 구성은 다음과 같다. int Find(int num){ if(parent[num] == num) return num; return Find(parent[num]); } void Union(int a, int b){ a = Find(a); b = Find(b); if(a != b) parent[a] = b; } 맨 처음 parent 배열에서 각각은 자기 자신의 번호를 갖고 시작한다. 1.. Algorithm/PS 알고리즘 정리 2022. 1. 20. [알고리즘] Red-Black Tree : 레드 블랙 트리 스스로 공부해 본 후, 다시 정리하는 내용의 글 입니다. 틀린부분과 실수가 있다면 지적해주시면 감사하겠습니다. 레드 블랙 트리 또한 binary-search tree(이진탐색트리) 의 일종이다. 기존의 이진탐색트리 같은경우 input이 이미 정렬되있다면 높이가 n이 되버리고, 따라서 시간복잡도 또한 O(n)에 도달하게 된다. 하지만 레드 블랙 트리의 경우 특정 조건을 지키면서 균형잡힌 이진트리가 되기때문에 Search, Insert, Delete 연산을 최악의 경우에도 O(logN) 시간안에 가능하도록 해준다. 이번 포스트의 순서는 다음과 같다. 1) NIL node 의 설명 2) Red-Black tree의 정의 3) Red-Black tree의 높이 4) Left and Right rotation 5.. Algorithm/PS 알고리즘 정리 2022. 1. 19. [백준][C++] 17135번: 캐슬 디펜스 <176> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 구현 문제는 생각의 순서를 정하는것이 중요하다. 어떤 순서로 진행되어야 할까? 1. 3명의 궁수를 N+1 번지에 배치한다. 2. 원본 map을 복사한 copyMap 만들기(궁수 배치의 case 마다 한번씩 복사해주어야 한다) 3. 왼쪽 궁수부터 BFS 탐색을 진행하면서, 가장 가까운 적을 공격표.. Algorithm/백준 2022. 1. 19. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 14장, 탐색 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 14장 탐색 탐색은 하나 이상의 field로 구성된 record의 집합에서 원하는 레코드를 찾아내는 작업이다. 보통 이런 레코드의 집합을 table이라고 부른다. 레코드들은 각각 고유한 키값을 갖는데, 이를 탐색키(search key) 라고 부른다. 자료 검색은 테이블에서 해당 탐색키를 찾는 것 이다. C++로 쉽게 풀어쓴 자료구조 (14장, 탐색) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 데이터: 키와 값을 가진 요소 (key, value)의 집합 연산: - create(key, value): 주어진 key와 value를 각각 키와 값으로 갖는 레코드를 생성. .. CS/Data Structure (2021-1) 2022. 1. 15. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 13장, 정렬 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 13장 정렬 정렬이란 물건을 크기순으로 오름차순이나, 내림차순으로 나열하는 것 을 의미한다. 일반적으로 정렬시켜야할 대상을 레코드(record)라고 불린다. 레코드는 다시 field라고 하는 보다 작은 단위로 나누어 진다. 여러 필드중 레코드들을 구분해주는 역할을 key가 한다. 선택 정렬 (selection sort) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 정렬되지 않은 숫자가 모여 있는 리스트 B 와 정렬이 완료된 숫자들이 들어가는 리스트 A 가 있다고 하자. A{ } : B{5, 3, 8, 1, 2, 7} 선택 정렬은 B의 리스트에서 가장 작은 숫자를 선택.. CS/Data Structure (2021-1) 2022. 1. 15. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 12장, 가중치 그래프 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 이번 12장 책 코드에 중간중간 오류코드들이 보인다... 이해를 조금 방해하는 수준이다. 1) 12장. 가중치 그래프(Weighted Graph) 가중치 그래프는 이전에 만들었던 AdjMatGraph class를 상속하여 사용한다. 이전에 사용했던 인접행렬에서는 간선이 있으면 1 없으면 0을 행렬에 저장했지만, 이번에는 가중치값을 행렬에 저장하였다. 일정 범위를 두고 그 범위 안의 값이면 간선이 있고, 이를 벗어나는경우는 간선이 없다고 여긴다. WGraph.h #pragma once #include "AdjMatGraph.h" const int inf = 100; class WGraph : public Ad.. CS/Data Structure (2021-1) 2022. 1. 15. 이전 1 2 3 4 다음
