알고리즘46 [알고리즘] 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++ 코드 작성 팁 해당 본문의 원문의 출처는 Geeks for Geeks 입니다. 이과생이 공부겸 번역한 딱딱한 어투의 글 입니다. 문제가 될시 삭제하겠습니다. Writing C/C++ code efficiently in Competitive programming - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org 가끔 해외 유튜버들.. Algorithm/PS 알고리즘 정리 2022. 1. 19. 뇌를 자극하는 C++ STL : 12장. string 컨테이너 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 12장. string 컨테이너 string은 표준 라이브러리 이지만 STL에는 포함시키지 않는다. string은 문자만을 원소로 저장하고 문자열을 조작할 목적으로 만들어진 컨테이너 입니다. string " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 다음 코드는 string의 생성자를 이용한 문자열 초기화 코드이다. #include #include using namespace std; int main() { string st("zbqmgldjfh"); string s1; string s2("Hello!"); string s3("Hello!", 3); string s4(3.. CS/C++ 2022. 1. 18. 뇌를 자극하는 C++ STL : 11장. 컨테이너 어댑터 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 11장. 컨테이너 어댑터 컨테이너 어댑터는 다른 컨테이너의 인터페이스를 변경한 컨테이너 이다. STL에는 stack, queue, priority_queue 3가지 컨테이너 어댑터가 있다. stack " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 stack 어댑터를 적용시킬 컨테이너는 empty(), push_back(), pop_back(), back(), size() 인터페이스를 지원해야한다. 따라서 이러한 인터페이스를 제공하는 vector, deque, list는 어댑터를 적용시켜 stack으로 사용할 수 있다. 다음 코드를 통하여 확인해 보자, #include .. CS/C++ 2022. 1. 18. 뇌를 자극하는 C++ STL : 9장. 함수 객체 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 9장. 함수 객체 STL에서는 다양한 함수 객체를 제공한다고 한다. STL의 함수 객체는 클라이언트 코드 에서 만든 함수를 callback형식으로 다른 구성 요소에 반영하기 위해 사용된다. 많은 알고리즘이 STL함수 객체를 알고리즘의 인자로 받아 작동한다. 함수 객체는 헤더에 정의되어 있다. 나같은경우 함수 객체보다는 Functor라는 단어가 입에 붙었기에 Functor라는 말을 주로 사용하겠다. STL의 함수 객체의 분류 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 ▶ 일반 함수 객체: 특정 기능을 수행하는 함수 객체 - 산술 연산 함수 객체 - 비교 연산 함수 객.. CS/C++ 2022. 1. 18. C++ 공부 섹션16 STL : 홍정모의 따배씨쁠쁠 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 상세히 기록하고 얕은부분들은 가겹게 포스팅 하겠습니다. 1) 섹션16 이번시간에는 STL에 대하여 배우는 시간이였다. 간략히 맛보기 시간이였던 것 같다. STL은 책을 따로 사서 공부할 예정이다. 16-1 표준 템플릿 라이브러리, 컨테이너 소개 항상 모든것을 직접 구현하여 사용한는 것 이 아니라, 자주 사용하는 것들을 표준으로 만들어논 라이브러리를 STL(Standard Template Libraries)라고 한다. STL은 4가지 위주로 구현이 되있다. 1) Algorithms, 2) Containers, 3) Functions, 4) Literators 이중 컨테이너 에 대하여 간단하게 배웠다. - Sequence_contain.. CS/C++ 2022. 1. 17. [자료구조] 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++로 쉽게 풀어쓴 자료구조 : 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. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 4장, Queue 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 4장. queue. deque Queue의 ADT " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 데이터: 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모음 연산: - enqueue(e): 주어진 요소 e를 큐의 맨 뒤에 추가한다. - dequeue(): 큐가 비어 있지 않으면 맨 앞 요소를 삭제하고 반환한다. - isEmpty(): queue가 비어있는지의 유무를 bool값으로 반환 - isFull(): queue가 가득 차있는지의 유무를 bool값으로 반환 - peek(): queue가 비어있지 않으면 맨 앞의 요소를 확인해본다. - size(): queue의.. CS/Data Structure (2021-1) 2022. 1. 14. 이전 1 2 3 4 다음
