알고리즘

기본base casegeneral case

경우를 정확하게 나누는 것이 중요!

개념makes the choice that looks best at the momentam: Si,j에서 가장 첫 종료시간 가지는 활동Ai,j: maximum size subset in Si,jak: Ai,j의 첫 종료 활동DP VS 그리디 비교

개념데이터를 효율적으로 압축조건prefix code 존재x코드큐에 결과값 넣으며 가장 작은 두개의 값 추출0과 1 할당왼쪽 0, 오른쪽 1시간 복잡도

도둑이 배낭에 넣을 수 있는 최대 보석 무게brute force모든 경우를 계산하여 가장 큰 경우time complexity: O(n)그리디해당 문제 해결 불가DP

행렬 곲을 최소로 만드는 알고리즘pXq, qXr 행렬총 연산 횟수: pxqxrbrute forceP(n): n개의 행렬을 괄호로 묶는 서로 다른 방법의 수ex) P(4) = p(1)p(3) + p(2)p(2) + p(3)p(1)

Longest Common Subsequence여러개 lcs 존재 가능

spanning tree: 그래프 내에 모든 정점을 포함하는 트리

discover: vertex is first encounteredexplore: edge is first examinedO(V+E)탐색 시작 노드 정보를 큐에 삽입하고 \*방문처리 함큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리2번

kind of edgeTree edge: dfs의 결과로 완성된 트리의 모든 간선들Back edge: from descendent to ancestor(checked)Forward edge: 트리에서 조상이 자식을 연결하는 tree edge가 아닌 간선들Cross ed

자기 균형 이진 탐색 트리(Self-Balancing BST)이진 탐색 트리: 자신의 왼쪽 서브 트리에는 현재 노드보다 값이 작은 것, 오른쪽 서브 트리에는 값이 큰 것들만 들어감평균 O(logn)이지만 균형이 무너질 경우 O(N)까지 시간 증가 할 수 있음rb tre

그래프에서 정점간에 가장 짧은 경로 찾는 알고리즘유형Single Source: 하나의 노드로부터 출발해서 다른 모든 노드의 최단 경로를 찾는 문제Single Destination: 모든 노드로부터 하나의 목적지 까지의 최단 경로를 찾는 문제Single Pair: 주어진