NineTwo meet you

비트 마스크란? 정수의 이진표현을 자료구조로 쓰는 기법을 의미한다. 비트 연산자 & AND 두 비트가 모두 0이면 1 | OF 두 비트가 모두 1이면 1 ^ XOR 두 비트가 서로 반전되면 1 ~ NOT 비트의 반전 > y x의 각 비트를 y만큼 오른쪽으로 이동하고 왼쪽 빈자리는 최상위 부호 비트와 같은 값으로 채움 >>> x >>> y x의 각 비트를 y만큼 오른쪽으로 이동하고 왼쪽 빈자리는 0으로 채움 부분 집합 비트 마스크를 이용하여 공집합부터 꽉찬 집합까지 표현이 가능하다. 배열의 개수가 n인경우 (1 2 {2,1} -> 011 -> 3 {3} -> 100 -> 4 {3,1} -> 101 -> 5 {3,2} -> 110 -> 6 {3,2,1} -> 111 -> 7 원소 포함 여부 확인 k라는 수의..

// 최대 공약수 static int GCD(int a, int b) { while(b > 0) { int temp = a; a = b; b = temp%b; } return a; } // 최소 공배수 // a*b할때 int 범위 초과할 수 있으니 유의해야 한다. static int LCM(int a, int b) { return (a*b)/GCD(a, b); }

프림 (Prim) 가중치의 합이 가장 작은 트리를 찾는 최소 스패닝 트리를 푸는 알고리즘 중 하나 하나의 시작점으로 구성된 트리에 간선을 하나씩 추가하는 방식 동작 과정 1. 그래프를 확인하고 출발 노드를 우선순위 큐에 저장한다. (start, 0) 이때 저장되는 가중치는 자기 자신이므로 0이다. 우선순위 큐 : (0, 0) 2. 우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다. 이때 한번 지나갔던 정점은 추가하지 않는다. 우선순위 큐 : (2, 1), (1, 5) 3. 우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다. 이때 한번 지나갔던 정점은 추가하지 않는다. 우선순위 큐 ..

크루스칼 (Kruskal) 가중치의 합이 가장 작은 트리를 찾는 최소 스패닝 트리를 푸는 알고리즘 중 하나 간선이 하나도 없는 상태에서 시작해 하나씩 트리에 간선을 추가해 가는 탐욕적 알고리즘 간선을 오름차순으로 정렬하고 이미 트리에 추가된 간선과 사이클을 이루지 않을 때 간선을 추가 간선이 사이클이 되지 않는지 확인하기 위해 유니온 파인드를 사용 동작 과정 1. 가중치가 오름차순으로 정렬된 우선순위 큐에 모든 간선을 추가한다. 우선순위 큐 (노드 1, 노드 2, 두 노드 사이의 가중치) : (0,1,1), (1,3,1), (2,3,2), (5,6,2), (1,5,3), (1,6,3), (3,6,3), (0,1,5), (3,4,5) 2. poll 한 값의 두 노드의 부모가 같은지 판단(사이클 여부 확인)..

플로이드 와샬(Floyd Warshall) 모든 쌍의 최단 거리 알고리즘 두 정점 사이에 간선이 없는 경우 어떤 경로의 길이보다도 큰 값으로 처리 3중 for문 사용 자기 자신으로 가는 간선은 항상 0으로 초기화 int n; // 정점의 수 int m; // 간선의 수 int adj[][] = new int[n+1][n+1]; // 그래프의 인접행렬 // 간선이 없는 경우 어떤 경로의 길이보다 큰 값으로 초기화 // 자기 자신으로 가는 간선 0으로 초기화 for(int i = 0; i v 로 향하는 가중치 w를 가지는 간선 for(int i = 0; i < m; i++) { Str..

벨만 포드 (Bellman-Ford) 단일 시작점 최단 경로 알고리즘 음수 간선 포함 가능 동작 과정 그래프에서 최단 경로가 한 정점을 두 번 지나는 일은 없다. 최단 경로는 최대 V개의 정점을 갖기 때문에 잘해야 V-1개의 간선을 가질 수 있다. 따라서 모든 간선에 대한 완화 과정은 V-1번이면 충분하다. 음수 사이클 판정 완화를 V번 시도하면 된다. 음수 사이클이 존재하지 않다면 V-1번이면 최단 거리를 찾아낼 수 있다. 만일 V번째 완화 과정에서 한번더 완화가 성공한다면 이는 음수 사이클이 존재한다고 생각할 수 있게 된다. static int n; // 정점의 개수 static int m; // 간선의 개수 static ArrayList[] al = new ArrayList[n+1]; // 그래프의..

다익스트라(Dijsktra) 단일 시작점 최단거리 알고리즘 너비 우선 탐색(BFS)과 유사한 형태를 가진 알고리즘 큐 대신 우선순위 큐(PriorityQueue)를 사용해 최단 거리를 기준으로 정점을 배열해 문제를 해결 음수 간선을 포함할 수 없음 동작 과정 출발 노드 방문 및 출발 노트 최소 비용 0으로 초기화 출발 노드 기준 각 노드별 최소 비용 저장 방문하지 않은 노드 중 가장 최소 비용 노드 선택 해당 노드를 거쳐 특정 노드로 가는 경우 고려해 최소 비용 갱신 3,4 반복 1. 기본 그래프 확인 2. 출발 노드 방문 및 출발 노트 최소 비용 0으로 초기화한다. 출발 노드 0의 최소 비용을 0으로 초기화한다. 3. 출발 노드 기준 각 노드별 최소 비용 저장한다. 출발 노드 0을 기준으로 연결된 노드..

DFS(depth-first search)란? 그래프 이론에서 많이 사용되는 탐색 알고리즘 중 하나다. 현재 정점에서 인접한 간선들을 하나씩 점검하다 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 탐색 알고리즘이다. 이전까지 거쳐온 정점을 기억하기 위해서 재귀를 사용한다. 또한 그래프의 모든 정점이 간선을 통해 연결되어 있다는 보장이 없기 때문에 그래프의 전체 구조를 파악하기 위해서 DFS로 풀 수 있는 유명한 문제를 살펴보겠습니다. 위상 정렬(topological sort) 그래프의 순서를 정렬하기 위한 방법이다. 각 정점의 의존 관계를 간선으로 표현한 의존성 그래프(dependency graph)의 순서를 나타내기 위해 사용된다. 이 그래프의 가장 큰 특징은 사이클이 없..