............ ............

#SCC(Strongly Connected Component): 강한 연결 요소 유향 그래프에서 임의의 두 정점 A, B에 대해 항상 A->B로 가는 경로가 존재하는 정점 그룹. + 즉 SCC안의 어떤 두 정점을 선택해도 서로 도달할 수 있는 경로가 존재한다. + SCC는 항상 최대로 정의된다. + 즉 SCC는 집합 내의 정점들이 서로 왕복 가능한 최대 크기의 집합이다. * 코사라주 알고리즘, 타잔 알고리즘은 모두 DFS(깊이 우선 탐색)를 기반으로 동작한다. #코사라주 알고리즘 주어진 그래프의 SCC(강한 연결 요소)를 찾기 위한 알고리즘 즉, 그래프 A가 주어질때, 1. 그래프 A에 대해 DFS를 수행하며, 방문하는 순서대로 스택 S에 삽입한다. 2. 그래프 A의 역방향 그래프 A'에 대해 스택 S에..

#위상정렬 어떠한 일을 하기 위한 순서를 탐색하는 알고리즘 즉, "순서가 정해져있는 작업"을 수행할때 그 순서를 결정하기위한 알고리즘 방향 그래프에 존재하는 각 정점의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는것 => 그래프를 정렬 ##조건 DAG(Directed Acyclic Graph): 방향성이 있고, 사이클이 없는 그래프 ##특징 하나의 그래프에는 여러개의 위상정렬이 존재한다. ##알고리즘 1. 진입차수가 0인 정점을 큐에 삽입. 2. 큐에서 원소를 꺼내고, 모든 간선을 제거 3. 간선을 제거한 이후에 진입차수가 0이 된 정점을 큐에 삽입 4. 큐가 빌때까지 2~3번 과정을 반복 모든원소를 방문: 위상정렬의 결과는 큐에서 꺼낸 순서 모든원소를 방문하기전에 큐가 비는경우: 사이클이 존재하는..

#비트마스킹(Bit Masking) 알고리즘보다는 bit단위 테크닉에 가까운 기법 + 정수를 이진수로 표현하는것을 활용 => bit단위로 값을 보존하며 진행 + 0=flase=off / 1=true=on => 비트로 상태를 나타낼수 있다. + 최적의 성능을 얻는데 필수적인 기법(컴퓨터 하드웨어) #비트의 활용 집합 A={0, 1, 2, 3, 4} A의 부분집합을 표현하는 방법 1. int형 인덱스 활용 int[] arr_1234 = {1, 1, 1, 1, 0} int[] arr_124 = {1, 0, 1, 1, 0} => 문제점: 메모리낭비, 오버헤드 증가 2. 비트마스킹 활용 => 1개의 정수로 표현가능 {1, 2, 3, 4} = 11110 => 30 {1, 2, 4} = 10110 => 22 #비트연..