출처 : https://www.acmicpc.net/problem/1146 1. 접근1. 키(숫자)는 궁금하지 않다, 즉 (1 2 3 4) 나 (1 5 7 9) 는 같은 상태이다.2. 모든 키가 다르므로 결국 인원 수가 중요하다3. 가장 키가 큰 N을 어디에 배치할지 정하고 나눠진 구간을 subproblem 으로 계산하자!  처음부터 위와 같이 접근한 이유는 다음과 같습니다.1. 상태의 독립성을 나타내기 위한 정보는? -> "인원수"2. subproblem 으로 쪼개고 싶다! -> (3)  2. 고찰N을 배치함에 따라 left, right 영역으로 나눠진다고 할 때 다음과 같은 궁금증이 떠올랐습니다.dt[N] : 지그재그 서는 가지수라고 하고 ( left ) N ( right ) 꼴로 나타날 때,Q. l..

출처 : https://www.acmicpc.net/problem/31063 해당 문제는 풀이가 굉장히 짧기에 포스팅이 짧지만, 교훈이 매우 중요할 것 같습니다. 1. 접근 과정 문제를 대충 보아하니 O(NM) 으로 TLE가 발생할 것 같다는 느낌이 든다. 따라서 어떤 알고리즘을 사용해서, 어떤 아이디어를 사용해서 최적화할 수 있을까? 를 관점으로 계속 생각하였다.  이전에 포스팅했던 SegmentTree 중 Lazy 하지 않더라도 연산 횟수가 제한된 경우의 문제를 떠올리며 입력의 최댓값을 보아하니 가망이 없겠구나... 싶었다. long long 타입까지 가능성이 있기에 고민하던 중 2^63 이라는 숫자 중 지수 부분을 활용하고자 생각하였고 문제 메커니즘을 다시 살펴보니 맨 앞의 소는 항상 먹을 수 밖에..

Mo's 알고리즘 이란?구간 질의하는 Query 문제에서 업데이트되지 않는 특수한 상황에서 사용할 수 있는 알고리즘으로 기존의 구간 쿼리는 O(NM)인 반면 Mo's 를 사용하면 O(M sqrt N) 으로 줄일 수 있습니다.  아이디어데이터가 추가적으로 업데이트되지 않는다면, 모든 쿼리에 대해서 항상 전체를 탐색해줄 필요는 없습니다. 이 전에 계산한 구간의 값을 참고하여 답을 구할 수 있습니다.   일단 데이터 길이를 N으로 했을 때 sqrt(N) 의 길이로 그룹을 나눕니다. 위 그림은 N = 10 일때의 그림이며 4개의 구간으로 나눌 수 있습니다. ( 왜 sqrt(N) 으로 나누는지는 아래에 설명하겠습니다 )  만약 위처럼 3가지 쿼리가 주어졌다고 할 때 어떻게 작동하는지 간략하게 그림으로 보고 자세히..

CCW(Counter-Clockwise) 알고리즘 CCW는 벡터의 외적을 이용하여 한 선분에 대하여 한 점의 위치 관계를 파악하는 알고리즘을 말합니다.직선 AB에 대하여 점 C의 위치 관계 서술한다면 AB벡터와 AC벡터의 외적 값의 부호를 통해 알 수 있습니다. 그리고 이러한 위치 관계를 통해 기하에서 다양한 것들을 할 수 있습니다. ※ 벡터의 외적과 방향성오른손의 법칙을 통해 AB벡터로 손을 가르킨 후 점 C의 방향으로 손을 감을 때 엄지손가락이 위로 가면 반시계 ( 외적값이 + ) 반대로 아래로 가면 시계방향 ( 외적값이 - ) 로 나타납니다.  int ccw(pii v1, pii v2, pii v3){ ll val = (v2.first-v1.first) * (v3.second-v1.second..

SCC 알고리즘 목적 해당 알고리즘의 목적은 사이클을 한 개의 노드로 묶는 것을 목적으로 하며 이 알고리즘은 위상 정렬에서 많이 사용됩니다. 위상 정렬은 사이클이 없는 그래프, 즉 dag라는 조건이 있어야 했는데요. 하지만 실제 복잡한 그래프는 사이클이 존재하는 그래프가 매~우 많습니다. 이런 상황을 다루기 위한 테크닉이 바로 SCC 알고리즘이 되겠습니다!강한 연결 요소 Strong Connected Component의 Group에 속하는 노드는 u, v 에 대하여 u->v로 항상 이동이 가능한 집단을 말합니다. SCC알고리즘은 이런 조건을 만족하는 노드를 grouping하는 것입니다!일반적인 그래프(트리 포함) -> Dag(트리 포함x) 변환!  작동 메커니즘문제 출처 : https://www.acmi..

출처 : https://www.acmicpc.net/problem/2316 1. 아이디어 접근기존의 네트워크 플로우 문제와 달리 추가된 조건이 한 가지 더 존재한다. 그것은 바로 "지난 노드는 더 지날 수 없다" 해당 조건을 구현하기 위해서 기존의 네트워크 플로우와 달리 이상한 방향으로 계획을 세우곤 했는데 해당 문제는 어떤 예제 상황에서 힌트를 얻을 수 있었다.  모든 간선의 최대 용량이 1일 때 1->2 로 가는 최대 유량은 2일 것이다. 하지만 우리가 구하고 싶은 답은 1이다. 여기서 우리가 관찰할 수 있는 것은 3으로 가나 4으로 가나 결국 5라는 공통된 지점이 존재하며 공통된 지점을 지날 때 연산 결과가 답을 도출한다는 결론을 내릴 수 있다.  해당 예시에서 5번은 검문소 혹은 공항과도 같다. ..

사실 이 문제는 1주일 전에 푼거긴 한데 dynamic programming에서 bottom-up, top-down 기법의 차이를 분석하고 넘어가고자 포스팅하고자 한다. 13250번: 주사위 게임 효빈이는 1부터 6까지 수가 적혀있는 6면 주사위를 가지고 있다. 매번 주사위를 던질 때마다 주사위의 윗 면에 적힌 수 만큼 사탕을 받게 된다. 효빈이가 적어도 N개의 사탕을 받기 위해 주사위를 www.acmicpc.net 1. 문제 분석 dt[i] = i이상의 사탕을 가져올 때 주사위를 던진 횟수의 기댓값으로 지정했다. 또한 주사위는 1~6 자연수 이기에 해당 범위의 dt값에만 영향을 받는다. 2. Bottom-Up Bottom-Up은 문제를 작은 단위로 쪼갠 상태에서 부터 큰 단위로 범위를 확장해 나가는 방..

1521번: 랜덤 소트 첫째 줄에 순열의 크기 N이 주어진다. 둘째 줄에 순열에 들어있는 수 N개가 주어진다. 이 수는 모두 1보다 크거나 같고, N보나 작거나 같으며, 같은 수는 2번 이상 주어지지 않는다. 또, N은 8보다 www.acmicpc.net 1. 문제 분석 N = 8이하 자연수라서 check배열을 이용해 최대 8!의 경우의 수를 구하여 답을 얻을 수 있다. 그리고 bfs와 memoization을 이용해 기댓값을 구하면 된다. 2. 실패 과정 살짝 확률을 경우의 수로 정의하는 것과 햇갈려서 횟수의 합과 경우의 수를 나눴다. 솔직히 이래도 괜찮지 않을까? 하고 무심코 넘어갔는데.. 1시간 고민 끝에 틀린 이유를 알 수 있었다. (아래 참고) 3. 성공 과정 위의 그림에서 쓴 글처럼 사실 어느 ..

최근에 이 문제를 풀고 큰 교훈을 얻어서 올려야지~ 하고 못했던 문제 중 하나입니다.. 복습할 문제들 보다가 이 문제가 눈에 띄어서 다시 올려봅니다. 27730번: 견우와 직녀 견우는 정점의 개수가 $N$인 무향 가중치 트리 $E$에 살고 있고, 직녀는 정점의 개수가 $M$인 무향 가중치 트리 $W$에 살고 있다. 두 사람은 각자 다른 트리에 살고 있으므로 만날 수 없다... 슬픔에 www.acmicpc.net 1. 문제 분석 A트리와 B트리가 존재할 때 A트리의 임의 노드 a, B트리의 임의 노드 b에 대하여 A의 모든 노드와 B의 모든 노드를 이동하는 비용의 합은 B.size * ( i -> a ) + A.size * (j -> b) + A.size * B.size 입니다. 그리고 i -> a 와 j..

16468번: 크리스마스 트리 꾸미기 이진트리란 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료구조로, 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드가 있다. 제일 위에 노드가 1개, 그 다음 2개… 와 같은 식으로 위에 www.acmicpc.net 1. 문제 분석 및 풀이 이전 포스팅에서 트리 dp에 대해 다뤘는데 대부분의 아이디어가 해당 노드를 루트로 하는 부분 트리에 대한 dt를 설정하여 진행하는 방법이었다. 이 문제도 너무 뻔히 tree dp임을 보이고 그냥 쉽게 만들면 된다고 생각했지만 단 한 가지 간과한 사실이 있었다. dt[n][h] : 높이 h인 트리를 n개의 공을 이용해 만드는 가지 수 이렇게 정의하면 되는 것인가? 나는 처음에 된다고 생각했는데... 문제를 쫌 더 보니깐 트리..