#include #include #include #include #define F first #define S second using namespace std; typedef pair PII; int V, E, X; int d1[1001], d2[1001]; vector go[1001], back[1001], temp[1001]; priority_queue pq; const int INF = 1e9 + 10; void dijkstra(vector* g, int* d, int start){ d[start] = 0; pq.push({d[start], start}); while(!pq.empty()){ auto cur = pq.top(); pq.pop(); if(d[cur.S] != cur.F) continu..

1. 가중치가 1인 무방향 그래프인 경우: BFS로 풀면 최초 방문 위치가 최단 경로가 보장된다.2. 가중치가 있는 방향이 있는 그래프인 경우: 데이크 스트라 알고리즘3. 플로리드 알고리즘(음수 간선도 가능)4. 벨만 포드 알고리즘

이번 포스팅에서는 비트마스킹에 대해 다루겠습니다. 비트마스킹을 이해하려면 비트에 대한 기본적인 이해가 필요합니다. 따라서 비트연산, 이진수의 표현과 변환 방법, 부분집합에 대해 이해가 선행되어야 합니다. 일반적으로 C++의 헤더에는 비트마스킹의 여러 기능을 지원합니다. 하지만 비트연산을 통해 직접 구현할 줄 알아야 합니다. 따라서 이번 포스팅에서는 직접 구현하고 원리를 알아보는 것을 위주로 다룹니다. 1. 개념 비트마스킹이란? 컴퓨터로 처리하는 모든 정보는 0과 1의 이진수로 이루어져 있습니다. 비트마스킹은 이진수의 비트 표현을 이용하여 자료구조(주로 집합)를 표현하는 기법입니다. 0은 해당 비트에 원소가 없음을, 1은 해당 비트에 원소가 있음을 나타냅니다. 예를 들어 10진수 14를 이진수로 변환하고 ..

[목차] 1. 다익스트라 알고리즘이란? 알고리즘 알고리즘 원리 구현 O(n²) O(ElogE) 알고리즘 분석 의의 다익스트라는 일종의 그리디 이다. 왜? 매 순간 다음 정점을 선택할 때 가중치가 최소인 정점을 선택하기 때문이다. 하지만 그리디의 특성상 부분 최적해가 전체의 최적해를 보장해야 위의 선택이 합리적이라고 할 수 있다. 그렇다면 매 순간 최소 가중치를 가진 정점을 선택하면 항상 최소가 보장될까? 직관 이를 귀류법으로 증명해보자. 반례 [원시적인 다익스트라 알고리즘] #include #include #include #define F first #define S second using namespace std; typedef pair PII; int V, E, st, en; int d[10001];..

[목차] Deque이란? Deque 기능 주요 기능 소개 구현해보기 주요 기능들의 성능 분석 예제 코드 Deque의 특징 예제 문제 1. Deque이란? 선형 자료구조에는 Stack, Queue, Deque, Linked List가 있다. Duque는 선형 자료구조의 한 종류이다. Double Ended Queue의 줄임말로 양쪽에서 삽입과 삭제가 가능한 Queue를 말한다. 주로 배열을 뒤집어서 원소를 추가/삭제하는 경우에 Deque를 쓰면 효율적으로 구현할 수 있다. C++과 java 모두 Deque을 지원한다. 따라서 그냥 가져다 쓰면 된다. 여기서는 C++에서 Deque의 주요 기능들을 간단히 소개하고 구현해본다. 예제는 [백준 5430번]을 이용한다. 2. Deque의 기능 1) 주요 기능 문제..

1. 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 풀이 아이디어 알고리즘 코드 #include #include #include #define F first #define S second #define IN(Y, X) Y >= 0 && Y = 0 && X < N using namespace std; queue q; int dy[4] = {0, 1, 0, -1}; int dx[4] = {1, 0, -1, 0}..

[목차] 완전 탐색과 DP로 푼 LIS LIS 알고리즘 아이디어 알고리즘 알고리즘 분석 예제 정리 1. 완전 탐색과 DP로 구현한 LIS 이 전의 글에서는 LIS를 구하는 알고리즘을 완전 탐색과 동적 계획법으로 구현했었다. 동적 계획법 풀이는 O(N²)의 시간 복잡도를 가졌었다. 하지만 이분 탐색을 이용하면 O(N logN)의 시간 복잡도로 더 빠르게 해결할 수 있다. 이번 글에서는 이분 탐색을 이용하여 O(N log N)의 시간 복잡도로 구현해보려고 한다. 이분 탐색의 LIS를 이해하려면 이분 탐색의 lower_bound() 함수와 upper_bound()함수에 대해 알고 있어야 한다. 또한 DP로 푼 LIS알고리즘도 이해하고 오면 도움이 된다. 따라서 앞의 부분에 대한 이해가 안되어있다면 최소한 이분..

1. 두 포인터란? 포인터 두 개를 사용하여 배열이나 문자열을 탐색하는 알고리즘이다. 흔히 배열을 탐색하다 보면 완전탐색을 진행할 경우 O(N²)의 시간복잡도를 가진다. 하지만 투 포인터를 이용하면 동시에 포인터 두 개로 탐색하므로 O(N)의 시간 복잡도로 한 번에 탐색할 수 있다. 예시 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net #include #include using namespace std; int N, M, a..