1. 그래프의 특징과 종류방향이 있는 그래프 가중치가 있는 그래프 순환이 있는 그래프  2. 그래프 구현2 - 1. 인접 행렬을 이용한 그래프배열의 인덱스는 노드세로 방향 출발 노드가로 방향 도착 노드배열의 값은 노드의 가중치 2 - 2. 인접 리스트를 이용한 그래프  결론인접 행렬크기가 고정되어 있기 때문에 노드가 많고 연결이 적은 그래프에서 낭비가 심한 단점이 있다.간선의 정보를 O(1)에 얻을 수 있는 장점이 존재인접 리스트대부분의 경우 인접 행렬에 비해 메모리를 절약할 수 있다.평균적으로 간선의 정보를 얻는데 시간이 좀 더 걸림  3. 그래프 탐색3 - 1. BFS최단 경로를 보장하는 탐색 방식queue를 사용한다.방문 처리를 queue에 push할때 진행한다.#include #include #i..

1. 집합집합은 코딩테스트나 알고리즘에서 순서와 중복이 없는 원소들을 가지는 자료구조를 뜻한다.예를 들어, A = {1 ,6, 6, 6, 4, 3} 일때 A를 집합으로 생각하면 {6,3,4,1} 이런 식으로 정리 될 것이다.코딩테스트에서는 주로 상호 배타적 집합에 집중하게 된다.상호 배타적 집합이란 A와 B라는 집합이 있을 때서로간의 교집합이 없는 집합을 뜻한다.그 이유는, 그래프 문제에 사이클을 확인하는 경우가 많은데 이때 상호 배타적 집합 개념을 활용해서 문제를 풀기 때문이다.  2. 집합의 연산주로 집합은 트리로 표현하게 된다. 또한 상호 배타적 집합을 나타내기 때문에 배열을 사용해서 구현한다.이때 각 집합은 대표 원소가 있어야 한다.대표 원소는 집합을 트리로 나타낼 때 루트가 되는 노드가 대표 원..

업데이트) 병합 정렬과 이분탐색 알고리즘 추가자세한 예시는 해당 글에 있고, 전반적인 정리는 아래 링크의 글을 참고하면 된다.https://gbleem.tistory.com/128 정렬 및 탐색 알고리즘 정리1. 정렬 알고리즘1 - 1. 버블정렬배열에서 두개의 원소 선택하고 비교 후, 왼쪽 원소가 오른쪽 원소보다 큰 경우 swap 한다.시간 복잡도는 O(N^2), 공간 복잡도는 O(1)만약 아래 코드에서 swap이 발생하gbleem.tistory.com 1. 버블 정렬개념앞에서부터 시작해서 자기 자신과 하나 뒤에 값을 비교하는데, 자신보다 작은 값이 나온 순간 swap을 해주는 과정을 통해 정렬한다.한바퀴 순환을 하고나면, 맨 뒤의 값이 가장 큰 값이 된다.N개의 데이터가 있을 때, 이중 for문을 모두..

1. 트리 개념노드, 간선으로 이루어진 구조코딩테스트에서는 이진 트리만 알고 있으면 충분하다.  2. 이진 트리 표현하기2 - 1. 배열로 표현하기루트를 인덱스 1로 시작왼쪽 자식은 부모 노드의 인덱스 x2오른쪽 자식은 부모 노드의 인덱스 x2 + 1이 방식의 단점은 배열의 공간이 조금 낭비된다는 점이다.그러나 매우 간단하기 때문에, 많이 사용하는 방식이다. 2 - 2. 이진 트리 순회하기현재 노드를 부모 노드로 생각했을 때전위 순회 : 부모 -> 왼쪽자식 -> 오른쪽 자식 중위 순회 : 왼쪽 자식 -> 부모 노드 -> 오른쪽 자식후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 부모 노드위에서 그린 그림을 기반으로 예를 들어보자더이상 갈 곳이 없거나, 우선순위가 자기 노드인 경우 방문하는 식으로 동작한다..

해시 구조는 데이터 값(키)이 들어오면,  "해시 함수"를 통해 변환된 값을 기반으로 버킷에 넣어주는 구조를 가진다.이때, 해시 함수가 변환한 값이 최대한 중복되지 않도록 (해시 충돌이 적게 발생하도록) 하는 것이 중요하다. 1. 해시 함수1 - 1. 나눗셈법 해시 함수공식 : h(x) = x mod k가장 기본적인 해시 함수로 나눗셈법을 이용한 함수가 있다."키"를 소수로 나눈 나머지를 활용하는 방식이다.이때, 소수를 사용하는 이유는 충돌을 줄일 수 있기 때문이다.예시) x = 3, 6, 9, 12, 15, 18, ... (3의 배수)15라는 수로 나눈 경우3 ~ 15 까지의 수는 각각 3, 6, 9, 12, 0 에 해당하는 버킷에 들어가게 된다.그러나, 이후의 값(18 ~)에 있어서 3, 6, 9, ..

1. 최대값 & 최소값 탐색주어진 컨테이너(주로 벡터나 string)에서 최대 혹은 최소를 구해주는 함수algorithm 헤더 include 필요min_element와 max_element 모두 리턴값은 해당 위치를 가리키는 iterator이다.string에서도 사용할 수 있다!숫자가 문자보다 우선순위가 빠르고, 대문자가 소문자보다 우선순위가 빠르다. (숫자 -> 대문자 -> 소문자)#include #include #include using namespace std;int main(){ vector vec = { 5,4,1,2,10 }; vector::iterator min_it = min_element(vec.begin(), vec.end()); cout ::iterator max_it = max_el..

1. STL 기본 구조STL이란C++ 내장 템플릿 기반 라이브러리컨테이너, iterator, 알고리즘으로 구성되어 있다.주요 컨테이너vector동적 배열로 구현된 컨테이너원소 삽입/삭제를 마지막 원소에 할때는 O(1)랜덤 접근이 O(1)중간 삽입/삭제는 비효율적list이중 링크드 리스트 구조의 컨테이너중간 삽입/삭제가 효율적deque양뱡향으로 동적으로 동작하는 컨테이너반복자컨테이너를 순환하면서 정리하거나 가져다주는 역할종류iteratorreverse_iteratorconst_iteratorinserter알고리즘정렬 관련 : sort, partial_sort, stable_sort, nth_element ...탐색 관련 : find, binary_search, lower_bound, upper_bound ..

1. partial_sum연속된 구간의 합을 구해주는 함수numeric 헤더를 include 해주어야 사용 가능하다.[] 연산자를 통해 특정 구간까지의 합을 구할 수 있다.#include #include #include using namespace std;int main(){ vector vec = { 1,2,3,4,5 }; vector vec_sum(vec.size()); partial_sum(vec.begin(), vec.end(), vec_sum.begin()); for (const int& v : vec_sum) { cout   2. unique중복된 원소를 제거한 후 끝 위치를 반환하는 함수unique 결과값이 중복을 제거하고 정렬된 맨 값들을 제외하고 맨 처음 원소를 가리킨다.아래 예시의 경..

1. find찾으려고 하는 문자 혹은 문자열의 시작 위치 index를 size_t 타입으로 리턴찾는 문자가 없는 경우 string::npos 값을 리턴 (18446744073709551615 가 출력된다)find에 두번째 매개변수를 넣으면, 해당 위치부터 시작해서 find 함수를 수행할 수도 있다.#include #include using namespace std;int main(){ string str = "Hello,World\n"; //특정 문자의 위치 찾기 size_t pos1 = str.find(','); size_t pos2 = str.find("ZZ"); size_t pos3 = str.find("H", 1); cout   2. replace파라메터첫번째 : 시작..

1. 우선순위 큐1 - 1. 기본 개념우선순위를 가지고 정렬 되어 있는 큐내부적으로 Heap 자료구조를 사용한다.삽입 삭제는 "항상" O(logN), 우선순위 높은 원소 검색은 O(1) 1 - 2. 사용하기기본적으로 가장 큰 원소가 먼저 나오는 최대 힙으로 구현 되어 있다.최소힙을 위해서는 아래와 같이 구현하면 된다.첫번째 인자는 자료형두번째 인자는 구현체세번째 인자는 비교연산자(비교 함수)priority_queue, greater> minPQ;새롭게 만든 타입을 사용하는 경우의 예시#include #include #include using namespace std;class Student{public: string name; int age;};struct cmp{ bool operator()(Stude..