DataStructure & Algorithm

std::array, std::vector등과 같은 연속된 자료구조에서는중간 데이터 추가/삭제 하는 작업이 비효율적이다.그래서 연결리스트와같은 형태의 자료구조가 등장.단일 연결 리스트를 구현해놓은 wrapper이다.성능 유지를 위하여 전체리스트 크기 반환 X첫번째 원소

std::list는 std::forward_list의 단점을 보완하기 위해서 C++ 제공하는 Container이다.std::list는 양방향 연결된 리스트이다.즉, 이중 연결 리스트 double-linked list 구조로 되어있다.기본적으로 push_back(), e

vector는 가변 길이 배열이다.그래서 pop_front(), push_front()와 같은 동작이 느리다.선형 시간 복잡도를 가지게된다. ( O(n) )이러한 단점을 극복하기 위한 것이 std::deque이다.Double Ended Queuepush_front(),

std::array 는 Stack메모리에 올란간다.Stack memory에 올라간다는 것은 Compile Time에 이 array의 size를 정의를 해야한다는 것이다.그래서 std::array를 "static array"라고도 한다.Complie Time에 사이즈가

Static ArrayComplie Time에 size가 정해진다.Dynamic ArrayRun Time에 size가 정해진다.C-style식으로 dynamic array를 정의할 경우에 항상 delete\[] ap; 이런식으로 delete키워드를 꼭 넣어줄 것을 배웠

Array에 접근하는 방식에 따라 심하게는 100정도의 성능 차이를 보인다. 바로 예를 살펴보면은 결론부터 말하자면 1번과 2번중에 2번이 100배 정도 빠르다. 그 이유는 "Cache" 때문이다. 1번 방식이 잘못됬다라는 것은 Cache Line을 전혀 생각하

결론은 std::list를 사용하면 안된다 ❗❗❗reference를 참고해 보면은std::list는 doubly-linked list라고 정의되어있다.std::vector는 array이다.이렇게 된다. 이것은 ref를 참고를 해보아도 부정할 수 없는 사실이다.searc

컨테이너 어댑터(container adapter)란 기존 컨테이너의 인터페이스를 제한하여 만든 기능이 제한되거나 변형된 컨테이너를 의미합니다.이러한 컨테이너 어댑터는 각각의 기초가 되는 클래스의 인터페이스를 제한하여, 특정 형태의 동작만을 수행하도록 합니다.std::s

너비 우선 탐색이라고도 한다.그냥 출발점부터 가장 가까이 있는 녀석들 부터 탐색하려는 경향이 있다고 보면은 된다.하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법시작

계층적 구조를 갖는 데이터를 표현하기 위한 자료구조노드 : 데이터 표현간선 : 노드의 계층 구조를 표현하기 위해 사용깊이는 Root Node가 0이다.높이는 3이다.양파를 까면 양파가 나오듯이 트리도 분리를 하면 트리라서 재귀함수와 잘 맞다.기본셋팅은 이렇게 해주도록

priority_queue를 지탱하는 이론이다.힙 트리도 트리라서 일단 이진트리부터 보도록 하자각 노드가 최대 두개의 자식 노드를 가지는 트리없을 수도 있고 하나만 있을 수도 있음.그러면 이진트리 왜 사용하나?binary search(이진 검색)를 사용할려고 이진 검색

기본적인 queue아 사용 방법은 거의 똑같은데다른점은 내림차순으로 결과값이 나온다는 것이다.그런데 작은 값부터 나오게 하고싶다면은 애초에 push할때 음수값을 넣어도 되지만 (너무 야매이다)2번째, 3번째 인자에 container와 pr을 정해줄 수 있다.이렇게 g

Dijkstra, BFS는 시작점은 있지만 목적지가 뚜렷하게 없다.그냥 싹다 탐색을 하다가 목적지가 얻어 걸리는거임.다익스트라 잠깐 생각해보면은BFS의 가중치가 있을 경우의 한계를 보완하기 위해 다익스트라 썼는데다익스트라는 간선마다 가중치가 있어가지고 발견한 경로 중에

데이터가 정렬된 상태로 있어야지만 이진 탐색이 가능하다.정렬된 연결 리스트로는 이진탐색 불가능함 (Random Access X)이런식으로 절반식 줄여가면서 O(log n)으로 탐색을 한다.핵심은 v < vecmid 일경우 right = mid - 1 만 변경한다는

배열의 단점을 극복하기 위해서 이진 탐색 트리를 이용을 한다.배열의 단점이 뭐냐? => 삽입/삭제가 느리다.::SetConsoleCursorPosition 함수https://blockdmask.tistory.com/399>콘솔창의 커서 위치를 옮기는 함수이다.

균형 맞추는 알고리즘 많음.AVL, Trick, 레드 블랙 트리 => 싹다 균형맞추는 알고리즘임.NIL은 그냥 Dummy 노드임.4번 특성이 중요함.레드 -> 레드 안됨. 블랙 -> 블랙 -> 블랙 이런거는 되지만.아무튼 1~5번 특성 위반되면은 재구성이 발생함.레드

이거 3가지 다 성능 ㅎㅌㅊ임.Astar에서 OpenList를 관리를 할 때, PQ를 사용을 해서 관리를 했는데질문중 하나가 C이게 자알을 모르면 이런 질문을 한다.기본적으로 PQ는 O (log n)을 가진다.Astar에서 OpenList에 넣고 매번 std::sort

기존의 PQ를 직접 구현을 해서 사용을 할 수도 있지만 일단 std::pq를 사용해서 구현을 하면 이렇게 된다.그리고 우선순위큐의 push의 시간 복잡도는 O(lon n)인데 데이터가 n개니까 O(n log n)이된다.버블, 선택, 삽입 보다는 훨씬 낫고 사용할 만한

정렬되지 않은 Array에서 N번째로 큰 || 작은 element를 찾는 방법이다.에서 2번째로 큰 수를 찾을 경우.Heap정렬을 한 뒤, 뒤에서 두번째 원소 뽑아내면된다.Heap정렬은 https://velog.io/@starkshn/Heap-sort-%EB%

먼저 "기준점"을 잡는다. 여기서는 5를 기준으로 잡아줌.(pivot설정은 지 마음대로임. 8을 해도되고 상관없음..)low ->, <- high 화살표 방향대로 이동을 할 것이다.먼저 low부터 보면은 pivot보다 작을 경우 ++low를 진행시켜준다.그러다가

C++11기준 map, hash map차이점 설명해봐라.map은 이진 트리 말하는거고hash map은 unordered map말하는 거임?기본적으로 다 Red-Black Tree이다.(균형 이진 트리)추가/탐색/삭제 => O(Log N)을 가진다.C>C라고 생각하는 사

고오급 알고리즘을 공부하는 이유?선구자들의 지혜를 배우고, 내가 보는 시야를 넓힌다.최소 스패닝 트리 (Minimum Spanning Tree)를 공부를 할 것인데,Minimum Spanning Tree => 그래프/트리의 활용정도가 된다.이것을 알기전에 알고가야할 부

최소 스패닝 트리트리는 일단 노드와 간선으로 이루어져 있다.최소 스패닝 트리란? 간선을 최소화 해서 모든 노드들을 연결하는 것을 말한다.길을 연결하는 과정부터 생각을 해볼 것이다.이렇게 빨간 간선으로 만 연결할 때 간선이 최소화가 된다.간선을 최소화 한다는 말은 "사이

최초의 상태는 이런 상태임.

Dijkstra랑 비슷하다.다익스트라는 BFS + "가중치"개념인데BFS가 출발점으로 부터 무조건 가까운 vertex부터 방문을 한다.여기서 "가중치"라는 개념이 들어가서 다익스트라는 출발점으로부터 무조건 가까운 vertex부터 방문을 하는데 가중치를 따져서 방문을 한

옛날에 했던거.. 5C2이런거이것도 말이 됨.3을 포함하지 않는 경우의 수 4C2 + 4 == 5C2지금 PPT오타있다.

1 9 2 5 7 부분 수열 : 일부 숫자를 지우고 남은 수열 ex) 1 2 5 ex) 1 9 5 7 1 2 9 이딴식으로 순서 바꾸는거 안됨. 순 증가 부분 수열 1 2 5 이런거 LIS > 제일 긴 순 증가 부분 수열의 길이 1 2 5 7 => 길이 4

문제는 되게 간단함.그냥 밑으로가나 오른쪽 밑으로가나 해서가장 큰 수의 합을 찾는 부분임.그냥 딱 최대의 합만 구하는 부분은경로까지 출력하는 부분은이렇게 되겠다.

아래 부분도 Permutation "순열" 코드이다.아래의 경우에는 algorithm 헤더파일에 있는 next_permutation을 사용한 순열 구현이다.재귀 함수를 통해서 "순열"을 구해볼 것이다.아래의 코드처럼 구해주면 되는데 "도식화"를 한두번쯤은 해보길 바란다

Algorithm CS

Big O 표기법은 알고있었는데예전부터 상수시간 복잡도? 이부분에서 뭐가 상수시간이라는 건지 햇갈렸음..엄밀히 말하면 상수시간이 아니겠지만Big O 표기법으로 아래와 같은 애들을 상수시간 복잡도 O(1)을 가진다고한다.그냥 간단한 연산이나 비교같은 부분들? 정도상수 시

공간복잡도가 뭐임?"입력 크기"에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 "양"을 의미한다.정적변수 뿐만아니라 동적으로 재귀적인 함수로인해 공간을 계속해서 필요로할 경우도 포함됨.배열이든 뭐든 공간 필요하면 다 포함됨.ㅇㅎㅇㅎ.문제의 최대 범위를 기반으

어떠한 앞에서부터 요소까지 계속 더한거 말하는거임.뒤에서 부터 더하는것은 suffix sum이다.범위가 1~4, 1~5, 3~5까지의 누적합들을 구해라라는 문제임그래서 코드를 이렇게 짜면 틀림.10만 \* 10만은 100억임. int범위를 벗어난다.그러면 long lo

abcde를 앞에서부터 3개를 출력하라해당 문자열을 거꾸로 출력하라해당 문자열 끝에 "abcde"추가하라이럴때1, 2번을이딴식으로 하면 안됨.최소한 이렇게는 해야함.맞는 말임.단순 구현이라면 구현바로하고무식하게 풀 수 있다면 무식하게 풀자.무식하게 푸는게 brute f

ㅇㅇ. 보통 그래프같은데서 u ,v 로 표현을 많이 하는데 이거 u는 from, v는 To이다.u에서 나가는 단방향 간선이 4개임. 이것을 outdegree가 4개라고 하는 것이다.u라는 vertex의 관점에서는 Indegree가 2개 Outdegree가 4개이다.v라