RECORD STUDY

https://www.toptal.com/developers/sorting-algorithms 정렬 알고리즘 퍼포먼스 선택 정렬(Selection Sort) 가장 작은 값을 찾아서 0번 인덱스에, 두번째로 작은 값을 찾아 1번 인덱스에 · · · =>일일히 하나씩 비교하여 가장 작은 값을 선택해서 앞으로 보냄 시간 복잡도 : O(N^2) #include using namespace std; int main(void) { int i, j, min, index, temp; int array[6] = { 4,2,7,9,3,1 }; for (i = 0; i array[j]) { ..

시간복잡도 - 보통 반복문이 결정, Big-O 표기법 사용 컴퓨터는 1초에 약 1억번(10^8) 연산 가능 tip!) 입력이 커질 때 사용 => ios_base::sync_with_stdio(false); cin.tie(NULL); c++에서는 개행문자로 endl사용 but 너무 느림 ∴ 대신 '\n' 사용 STL(Standard Template Library) PS에서 C++을 쓰는 이유 PS에서 자주 쓰이는 여러 자료구조, 알고리즘등이 구현되어 있음 -vector, stack, queue, set, map, string등의 자료구조 -최댓값, 최솟값, 이분탐색, 엄청 빠른 정렬등의 알고리즘 Sort 기본적으로 오름차순 정렬, 퀵 정렬을 기반으로 함, 최악의 경우에도 O(NlogN)보장 #include..

※ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 1. 스택(Stack) LIFO(Last in First out) : 나중에 들어간게 먼저 나옴 : push(), pop(), top(), size(), empty() #include //pop,top의 경우 empty여부 확인하기 stack s; if(s.empty()) cout

그래프 : 정점(vertex)과 간선(edge)의 집합으로 정의된 자료구조 G=(V,E) ( ) : 무방향 , : ->방향 degree(차수) : 정점에 연결된 간선의 수(방향그래프에서는 indegree,outdegree) cycle weight(가중치) : 간선에 할당되는 무게 인접행렬(adjcent matrix) : 두 정점간의 간선 연결관계를 |v| * |v|크기의 행렬(배열)로 표현 +)구현간단 -)공간복잡도 v^2 인접리스트(adjcent list) : O(E) DFS(스택 , 재귀함수사용) : 끝까지 가는 방식 BFS(큐, ※ 부분 그래프, 연결 요소, 강력 연결 요소, 트리, 신장 트리, 단절점, 이중 결합 그래프, 이중 결합 요소 ...

DP: 복잡한 문제를 여러문제로 나누고 문제를 해결한 값은 기억했다가 다시 써야할일이 있으면 재사용 => 문제쪼개기 + 메모이제이션 DP의 구현 방법 2가지, 차이점 DP가 사용하는 핵심 기법의 이름은 무엇이고 그것이 어떤 기법인지 설명 더보기 1. 탑다운, 바텀업 / 탑다운: 코드 이해, 작성 쉬움 -) 함수 호출 비용 大, 바텀업보다 느리고 메모리 大 바텀업: 빠르고 메모리 小 -) 코드 작성이 조금 어려움 2. 메모이제이션 / 계산한 소문제의 값을 기록했다가, 똑같은 소문제를 계산해야되는 경우 다시 계산하지 않고 기록한 값을 그대로 활용 ex) 피보나치 수열에서 recurcive함수로 구현했을 때 계산 중복이 多 1)전에 계산한 값 기록했다가 필요하면 다시 계산안하고 그 값 사용(memoizatio..