mei 기술 블로그

1. 집합(Set)특정 조건에 맞는 원소들의 모임2. 교집합두 집합이 공통으로 포함하는 원소로 이루어진 집합A ∩ B = {x | x ∈ A and x ∈ B}3. 합집합어느 하나에라도 속하는 원소들을 모두 모은 집합A∪B = {x | x ∈ A or x ∈ B}4. 차집합A or B에만 속하는 원소들의 집합A - B = {x | x ∈ A and x !∈ B}5. 여집합전체 집합(U) 중 A의 원소가 아닌 것들의 집합A^c = {x | x ∈ U and x !∈ A}6. 코드HashSet set = new HashSet();set.add(1);set.add(1); // set은 중복 허용하지 않기 때문에 1은 한번만 삽입set.add(2);set.add(3);set.remove(1); // 1이라는 데..

1. 서로소 집합 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합 2. 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 두 종료의 연산을 지원한다. 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리기도 한다. 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정은 다음과 같다. 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. A와 B의 루트 노드 A’, B’를 찾는다. A’를 B’의 부모 노드..

비용이 음수인 간선이 있을 때 최단 경로를 구하는 알고리즘 1. 음수 간선이 포함된 상황에서의 최단 거리 문제 백준 ‘타임머신’ 문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 2. 벨만 포드 최단 경로 알고리즘 음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류할 수 있다. 모든 간선이 양수인 경우 음수 간선이 있는 경우 음수 간선 순환이 없는 경우 음수 간선 순환이 있는 ..

모든 출발지에서 다른 모든 출발지까지 최단 경로 계산 1. 플로이드 워셜(Floyd-Warshall) 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다. 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다. 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다. 점화식에 맞게 3중 반복문을 이용하여 2차원 테이블을 갱신한다. 다익스트라 알고리즘과 비교했을 때 구현 난이도는 쉬운 편인데 시간 복잡도는 O(N^3)이다. 노드의 개수가 적은..

하나의 출발지에서 다른 모든 출발지까지 최단 경로 계산 1. 최단 경로 문제 가장 짧은 경로를 찾는 알고리즘 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 2. 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다. 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다. 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 ..

1. DFS (Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. 동작 예시 [Step 0] 그래프를 준비한다. (방문 기준: 번호가 낮은 인접 노드부터) 시작 노드: 1 [Step 1] 시작 노드인 ‘1’을 스택에 삽입하고 방문 처리한다. [Step 2] 스택의 ..

1. 정렬 알고리즘 비교 대부분의 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장 단, 퀵 정렬은 최악의 상황의 시간 복잡도 = O(N^2) 정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 O(N^2) O(N) 아이디어가 매우 간단 삽입 정렬 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때 가장 빠름 퀵 정렬 O(NlogN) O(N) 대부분의 경우 가장 적합하고 빠름 계수 정렬 O(N+K) O(N+K) 데이터의 크기가 한정되어 있는 경우에만 사용 가능하지만 매우 빠름

빠른 정렬 알고리즘 1. 퀵 정렬 일반적으로 데이터 특성과 관련 없이 표준적으로 사용할 수 있는 정렬 알고리즘 중 하나 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정 동작 예시 [Step 0] 현재 피벗의 값은 ‘5’이다. 왼쪽에서부터 ‘5’보다 큰 데이터를 선택하므로 ‘7’이 선택되고 오른쪽에서부터 ‘5’보다 작은 데이터를 선택하므로 ‘4’가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다. [Step 1] 현재 피벗의 값은 ‘5’이다. 왼쪽에..

1. 정렬 알고리즘 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용 2. 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 동작 예시 [Step 0] 처리되지 않은 데이터 중 가장 작은 ‘0’을 선택해 가장 앞의 7과 위치 변경 [Step 1] 처리되지 않은 데이터 중 가장 작은 ‘1’을 선택해 가장 앞의 5와 위치 변경 [Step 2] 처리되지 않은 데이터 중 가장 작은 ‘2’을 선택해 가장 앞의 9와 위치 변경 [Step 3] 처리되지 않은 데이터 중 가장 작은 ‘3’을 선택해 가장 앞의 7와 위치 변경 이러한 과정 반복 매번 가장 작은 데이터를 찾기..

1. 바이너리 인덱스 트리 (Binary Indexed Tree) 2진법 인덱스 구조를 활용하여 구간 합 문제를 효과적으로 해결해줄 수 있는 자료구조 펜윅 트리(fenwick tree) 라고도 함 정수에 따른 2진수 표기 정수 2진수 표기 7 00000000 00000000 00000000 00000111 -7 11111111 11111111 11111111 11111001 0이 아닌 마지막 비트를 찾는 방법 특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서 K & -K 계산 K & -K 계산 결과 예시 정수 K 2진수 표기 K & -K 0 00000000 00000000 00000000 00000000 0 1 00000000 00000000 00000000 00000001 1 2 00000000 ..