에라토스테네스의 체 에라토스테네스의 체는 소수를 구하는 대표적인 알고리즘이며, 자주 쓰지만 쓸 때마다 헷갈려서 정리했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #include #include using namespace std; #define N 3000 int prime[N + 1]; void che() { prime[0] = -1; prime[1] = -1; for (int i = 2; i <algorithm>을 활용한 정렬 CP를 하면서 헷갈리는 것을 정리했다. 배열 정렬과 벡터 정렬 1 2 3 4 5 6 7 8 9 // 벡터(n은 정렬할 원소의 개수) sort(vec.begin(), vec.end()); // 오름차순 sort(vec.begin(), vec.begin() + n); // 오름차순 sort(vec.begin(), vec.end(), greater()); // 내림차순 // 배열 sort(arr, arr + n); // 오름차순 sort(&arr[0], &arr[n]); // sort(arr, arr + n, greater()); // 내림차순 char 및 string의 정렬도 똑같이 작동한다. 비교 함수인 greater()에 자료형을 정해주지 않고 비워놓은 것을 확인할 수 있다. 이렇게 자료형을 쓰지 않아도.. 마스터 정리(Master Theorem) 마스터 정리는 재귀를 활용한 점화식을 푸는 방법을 알려준다. 다른 것과 다르게 재귀를 사용한 알고리즘은 시간 복잡도를 구하는 것이 어려운데 마스터 정리를 사용하면 아주 간단하게 해결할 수 있다. 재귀 알고리즘의 점화식은 다음과 같은 형태를 띄고 있다. $$T(n) = aT(n / b) + f(n) (단, a ≥ 1, a > 1, f(n)은 점근적으로 양)$$ f(n)이 점근적으로 양이라는 말은 충분히 큰 n에 대하여 f(n)이 양이라는 뜻이다. 점화식에서 a, b, f(n)을 가지고 시간 복잡도를 계산한다. 다음과 같이 세 가지 경우가 있다. 1. $f(n) n^{log_ba}$ 3. $f(n) = n^{log_ba}$ 1의 시간 복잡도 T(n) = θ($n^.. 이진 검색 트리(Binary Search Tree) 자료 출처 1. [알고리즘] 제11-1강 이진검색트리(Binary Search Tree) 2. [알고리즘] 제11-2강 이진검색트리(계속) 3. [알고리즘] 제11-3강 이진검색트리 4. Introduction to Algorithms 12장 트리라는 자료구조는 보통 데이터 자체가 계층적인 구조를 가지고 있을 때 주로 사용한다. 이를테면 조직도, 가계도가 있다. 하지만 검색 트리는 조금 다르다. 검색 트리에 저장되는 데이터들은 반드시 계층적인 구조를 가지고 있을 필요는 없으며, 검색 트리는 데이터를 저장하는 컨테이너로서 역할을 한다. 다른 컨테이너 역할을 하는 자료구조들과 다른 점은 검색 트리는 삽입(Insert), 탐색(Search), 삭제(Delete)와 같은 동적 집합(dynamic set) 연산을.. [이산수학] 관계 충북대학교 이충세 교수가 2015년 1학기에 강의한 이산수학 과목 중 관계(1)을 듣고 정리한 것이다. 그래프를 배울 때 2, 3도 듣고 정리할 예정이다. 사람 사이에는 여러 관계가 있다. 선생-학생, 부모-자식 등이 그 예다. 이와 마찬가지로 집합에도 관계가 있다. 예를 들어, 학생 정보(이름, 학번)과 과목 정보(과목명, 과목 코드)를 카티션 곱을 하면 학생 정보와 과목 정보가 합쳐진 수강 정보가 나오는데, 이는 '어떤 학생이 특정 과목을 수강한다'는 관계를 만들어 낸다. $A*B$로 표현할 수 있다. 여기서 A를 정의역(Domain), B를 공역(Co-domain)이라고 한다. 또한 A에서 B로 가는 관계 중 A와 실제로 관계를 맺고 있는 것을 치역(Range)라고 한다. 그렇기 때문에 치역은 B의.. 해시 테이블(Hash Table) 개요 해시 테이블(Hash Table)은 많은 양의 데이터의 인덱싱(indexing)을 빠르게 해 줌으로써 탐색(Search), 삽입(Insert), 삭제(Delete)의 속도를 높여주는 자료구조다. 그렇기 때문에 해시 테이블은 Database indexing, Caching, Error checking, Password authentication 등 많은 곳에서 쓰이고, dynamic set을 구현하는 데 사용되기도 한다. 자료 출처 1. Hash Tables and Hash Functions 2. [알고리즘] 제13-1강 hashing01 3. Introduction to Algorithms third edition 11장 해시 테이블 위의 배열에서 'Ada'를 찾는 프로그램을 만든다고 하자. 보통 .. 나는 아마존에서 미래를 다녔다 아마존에서 12년 동안 근무한 한국인인 박정준씨가 아마존에 대해 말해주는 책이다. 아마존의 창업자인 제프 베조스에 대해서, 아마존의 사업 영역에 대해서는 대충 알고 있었지만, 아마존의 기업 문화에 대해서는 아는게 없어서 이번에 책을 읽으면서 조금이라도 알아보고자 했다. 아마존에서 12년이나 일한 저자의 말이라면 충분히 신뢰가 갈것 같았다. 읽으면서 흥미로웠던 부분들을 주제로 짧게 다루겠다. 비싼 회사 식당 아마존이 절약을 한다는 것은 위 사진에 있는 '도어 데스크'를 통해 충분히 알수 있었는데 직원들에게 제공하는 식사조차 무료로 제공하지 않고 돈을 아낀다고 한다. 실제로 저자의 지인이 한국에서 방문하면 가격이 비싸 놀란다고 한다. 이는 직원 복지 차원에서 무료로 식사를 제공하는 구글이나 페이스북과 같은 .. 힙정렬(Heap Sort) 개요 힙정렬을 하기 위해서는 '최대힙', '최소힙'의 개념을 알아야 한다. 최대힙은 '두 노드값은 그 부모의 값보다 클 수 없다'는 정의를 만족하는 힙이며, 최소힙은 그와 반대로 '두 노드값은 그 부모의 값보다 작을 수 없다'는 정의를 만족하는 힙이다. 즉, 최대힙에서는 최대값이 루트에 있으며, 최소힙에서는 최소값이 루트에 있다. 최대힙의 성질을 이용해 오름차순 정렬을 할 수 있으며, 최소힙의 성질을 이용해 내림차순 정렬을 할 수 있다. 둘 중 하나만 확실하게 알아놓으면 다른 하나는 반대되는 성질로 인해 쉽게 추론할 수 있으므로 '최대힙을 이용한 오름차순 정렬'만 공부하겠다. 최대힙을 이용한 오름차순 정렬 우선 오름차순으로 정렬해야할 배열이 주어지면 그 배열을 최대힙으로 만든다(buildMaxHeap)... 이전 1 2 3 4 5 6 7 다음
