개발일지

개념 Floyd Warshall (플로이드 와샬) 알고리즘은 정점과 정점 사이의 최단 거리를 구하는 알고리즘이다. 플로이드 와샬 알고리즘의 특징은 모든 정점 사이의 거리를 구할 수 있다. 최단 경로를 찾을 때 중간에 한번 거쳐서 가는 경로 중 가장 가까운 경로로 업데이트 하면서 모든 정검들의 최단 거리를 구하는 알고리즘이다. 시간 복잡도가 O(V^3)이라는 꽤 오래 걸리는 알고리즘 이지만 모든 정점 사이의 최단 거리를 구할 수 있다. 작동원리 1. 중간 정점 K, 시작 정점 I, 도착 정점 J로 삼중 반복문을 순회한다. 2. distance[i][j]가 distance[i][k] + distance[k][j]보다 크면 경로를 업데이트 한다. -> distance[i][k], distance[k][j]가 ..

개념 LIS(Longest Increasing Subsequence)는 배열이 있을 때 일부 원소를 고른 부분 순열 중, 각 원소가 이전 원소보다 크고 그 순열의 길이가 가장 큰 순열을 LIS라 하고 최장 증가 부분 순열이라고 한다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 변형 문제로 LDS, 최장 감소 부분 순열이 있다. 작동원리 1. LIS라는 List를 만든다. 2. List가 EMPTY거나 제일 마지막 원소가 검사하는 원소보다 작은 경우 List뒤에 추가한다. 3. 검사하는 원소가 List 마지막 원소보다 작은 경우 lower_bound를 사용하여 찾은..

https://www.acmicpc.net/problem/3648 3648번: 아이돌 각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다. www.acmicpc.net 접근 Tarjan 알고리즘으로 SCC를 구현하면 특성상 하위의 SCC가 먼저 결정된다. 그렇기 때문에 x < ¬x 를 만족하면 x가 참이된다. 상근이가 합격하려면 ¬x가 False면 합격이기 때문에 그래프를 구현할 때 역방향으로 그래프를 구현하여 ¬x가 False가 될 수 있는지 확인한다. (명제의 대우는 동치이기 때문에 가능하다.) 코드 #include using namespace std; constexpr int NONE = -1; int..

https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 접근 1. SCC를 만들고 각 Component를 새로운 하나의 노드로 생각하고 Component의 구성 요소로 SCC Component간 연결할 수 있는 간선을 구하여 새로운 Graph를 구한다. 2. DP를 사용하여 최대로 인출할 수 있는 금액을 구한다. 코드 #include #include #include #include using namespace std; constexpr ..

개념 충족 가능성 문제 중 하나로써 아래와 같은 형태를 2-SAT 문제라 한다. * 충족 가능성 문제 : Boolean으로 이루어진 식이 있을 때 해당 식이 True인 경우를 찾는 문제 f=(¬x1∨x2)∧(¬x2∨x3)∧(x1∨x3)∧(x3∨x2) 인 경우에 f를 true로 만드는 경우 ¬ : NOT ∨ : OR ∧ : AND 괄호 안의 OR 연산으로 이루어진 것을 절(Clause)이라고 표현하고 AND와 절로 이루어진 식을 CNF(Conjunctive Normal Form)라고 한다. 각 절의 변수의 개수가 2개면 2-SAT이라 하고 N개면 N-SAT이라고 한다. 2개 같은 경우 SCC 알고리즘을 사용하여 쉽게 해결할 수 있지만, 3개 이상의 SAT 문제에서는 NP-Hard 문제이다. 작동원리 1. ..

www.acmicpc.net/problem/2449 2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 접근 1) dp[left][right][color] 재귀함수로 구간에 특정 color로 색칠하는 방법을 고민했다. => 실패 이유는 모르겠다. 2) dp[left][right] 하지만 구간을 나누고 특정 color로 색칠할 필요가 없었다. => left의 색이나 right의 색으로 칠하는 것이 자명하기 때문이다. dp[left][right] = min(dp[left][i] + dp[i + 1][righ..

www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 접근 처음에 Disjoint-Set과 LCA를 고민했다. Disjoint-Set을 고민한 이유는 간선을 추가할(샘플을 측정) 때 Disjoint-Set의 Union연산을 통해 하나의 Set으로 만들고, Find연산으로 쉽게 UNKNOWN인지 알 수 있기 때문이다. LCA를 고민한 이유는 무게차이를 구할 때 공통 조상 노드를 찾아서 거리를 구하면 logN만에 쉽게 거리를 찾을 수 있기..

개념 탐색 범위를 반으로 줄이면서 값을 찾는 방법이다. 작동원리 1. 탐색 범위를 정렬한다. 2. l -> 탐색 범위 최소값, r -> 탐색 범위 최대값, m -> 탐색 범위 중간값 3. m에 찾으려는 위치가 있는지 확인한다. 4. m에 찾는 값보다 큰 값이 존재하면 r을 m - 1로 바꾼다. ( 정렬되어있기 때문에 m보다 큰 인덱스에 저장된 값은 m에 저장된 값보다 크기 때문에 확인할 필요가 없다.) 5. m에 찾는 값보다 작은 값이 존재하면 l을 m + 1로 바꾼다. (정렬되어있기 때문에 l보다 작은 인덱스에 저장된 값은 m에 저장된 값보다 작기 때문에 확인할 필요가 없다.) 6. l > n >> k; vector ve(n); for (auto &i : ve) { cin >> i; } long lon..