c++ 자료구조/알고리즘 개념 복습

알고리즘 문제만 무작정 푸는 것 같아 이번에 주요 개념들을 다시 정리하는 시간을 가지려한다바킹독님의 강의를 바탕으로 복습을 진행해볼 예정!\-- int --int 형 1개는 4bytefloat - 유효숫자 6자리double - 유효숫자 15자리long long - 유효

시간복잡도 O(1)에 k번째 원소를 확인 및 변경 가능임의의 위치 원소 추가 = O(n) <- 한 칸씩 뒤로 밀어야 한다임의의 위치 원소 제거 = O(n) <- 한 칸씩 당겨온다 원소를 끝에 추가 = O(1)마지막 원소 제거 = O(1)추가적으로 소모되는 메

원소들을 저장할 때 그 다음 원소가 있는 위치를 포함하는 방식의 자료구조 k번째 원소를 확인/변경하기 위해 O(k)가 필요하다 배열과 다르게 O(1) 접근이 불가 임의의 위치에 원소를 추가/삭제 = O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit r

마지막에 들어간 원소가 가장 먼저 나오는 자료구조 = LIFOLast In First Out원소의 추가 = O(1)원소의 제거 = O(1)스택 최상단의 원소 확인 = O(1)최상단이 아닌 원소들의 확인/변경이 원칙적으로 불가능

한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조먼저 들어간 원소가 먼저 나온다 = FIFO(First In First Out)원소의 추가 = O(1)원소의 제거 = O(1)맨 앞/뒤 원소 확인 = O(1)맨 앞/뒤가 아닌 나머지 원소들의 확인, 변경

양쪽 끝에서 삽입/삭제 가능한 자료구조원소의 추가 = O(1)원소의 제거 = O(1)제일 앞/뒤의 원소 확인이 O(1)제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능!! STL deque 에서는 인덱스로 원소의 접근이 가능 !!STL stack, qu

erase 사용 streamstring 사용

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법보통

다차원 배열에서 각 칸을 방문하는 경우 깊이를 우선으로!스택을 주로 사용한다재귀로도 가능

https://kimcoder.tistory.com/122존재하지 않는 key 값을 인덱스로 하여 Map에 접근하면 기본타입의 value 값이 나온다ex> value가 int -> 0, string -> ""위 코드는 -1 이 출력된다!value 타입이 in

sort(배열 변수 이름, 배열 변수 이름 + 배열길이)compare 함수를 명시적으로 정의하여 원하는 기준으로 정렬 가능 \- int 타입인 경우 위와 같이 int 타입 인자를 2개 받으면 된다greater = 내림차순 정렬true로 조건 성립하면 우선순위가 높다고

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘재귀를 사용한다는 것은 곧, 귀납적인 방식으로 풀이를 하는 것!특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다(Base Condition)모든 입력은 Base Condition으로 수렴해야

배열에서 기존에 이중 for문을 통해 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘투 포인터에서는 i=0일 때 계산하면서 얻은 정보가 그 다음인 i=1일때 사용한다이분탐색으로 투 포인터 문제를 풀 수 있는 경우도 많으며, 반대로 이

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘모든 경우의 수를 확인해야 할 때 사용\-> for 로는 확인 불가한 경우(깊이가 달라질때)더 이상 볼 필요 없는 부분은 쳐내는게 핵심https://www.acmicpc.net/problem/1

pop을 하는 경우, 가장 먼저 들어온 원소가 나오는 대신, 우선순위가 가장 높은 원소가 나오는 큐!힙 구조 활용!!!원소의 추가 = O(logN)우선순위가 가장 높은 원소의 확인 = O(1)우선순위가 가장 높은 원소의 제거 = O(logN)이진 트리 기반최대값, 최소

Greedy 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 관찰을 통해 탐색 범위를 줄이는 알고리즘 바킹독님 그리디 문제 추천 전략 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다 -> 짜서 제출해보고 틀리면 빠르게 손절

여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.즉, DP는 부분 문제의 결과

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법 O(logN) 시간복잡도 이분탐색을 활용해 문제를 푸는 경우 탐색 종료 조건을 상황에 맞게 잘 설정하는 것이 중요하다!! -> w

해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행된다. 데이터를 검색할 때 사용할 Key와 실제 데이터의 값(Value)이 한 쌍으로 존재하고, Key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게

왼쪽 시프트 연산자 << 는 수를 왼쪽으로 이동하는 것1 << n 형태 = 2의 n승1 << 2 = 이진수 형태 0001 에서 0100 이 되는 것 &연산 활용!boolean 배열의 역할을 하는 '하나의 숫자' 를 만들어서 '비트 연산자

각 노드는 특정 구간을 대표하다 이진 트리 구조 (완전) 부모 노드가 대표하는 구간은 자식 노드 두 개가 대표하는 구간의 합집합이다 부모 노드가 담당하는 구간을 반씩 나누어 왼쪽 자식, 오른쪽 자식 탐색 구간의 길이가 1이라면 리프노드! (구간 시작 번호와 마지막 번호

모든 정점 쌍 사이의 최단거리를 구하는 알고리즘 각 정점을 거쳐서 가능 경우를 생각한다 i->j 로 가는 과정에서 정점A를 거쳐가는게 더 빠르다면 최단 거리를 업데이트 해준다 각 정점 별로 모든 정점의 쌍을 검사하므로 O(n^3) 시간 복잡도 ( n(정점 수) *

하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘 플로이드 워셜의 경우 음수의 간선은 괜찮고, 음수의 사이클이 존재하는 경우 문제가 발생 but 다익스트라는 음수의 가중치를 가진 간선있으면 사용할 수 없다 바킹독님 강의링크 (https://www.