0850

최소 신장 트리(Minimum Spanning Tree, MST) 구현에 사용되는 알고리즘이다. 최소 신장 트리란 그래프에서 모든 정점을 최소 비용으로 연결하는 트리이다. 프림 알고리즘 다음 과정을 따른다. 1. 시작 정점을 하나 정함.2. 연결 가능한 간선들 중 가장 비용이 낮은 간선을 선택3. 해당 간선이 연결하는 정점이 아직 MST에 포함되지 않았다면 추가4. 1~3을 모든 정점이 연결될 때까지 반복 프림은 O(ElogV)의 시간 복잡도를 가지며, priority_queue를 사용하여 구현할 수 있다.(MST 구현에 사용되는 다른 알고리즘인 크루스칼은 O(ElogE)이다. 따라서 간선이 많은 경우는 프림이 유리하다.) int mst() { priority_queue, vector>, greater>..

문제: https://www.acmicpc.net/problem/2166난이도: G5 ccw를 사용하는 문제이다. 점 3개로는 삼각형이 만들어지는데, 점 하나를 잡고 다른 두 점들을 모두 연결하여 삼각형을 만들면 모든 점으로 이루어진 도형을 삼각형들로 나눌 수 있다. 이 삼각형의 넓이는 ccw로 구할 수 있다, 세 점의 ccw결과는 평행사변형의 넓이이다. 이 값을 2로 나누어주면 삼각형의 넓이가 된다. 점들로 이루어진 도형이 볼록하다는 보장이 없지만, 오목한 부분을 ccw를 하면 음수가 나온다.(아래 그림) 따라서한 점을 잡고 모든 두 점에 대해 ccw를 한 결과를 절댓값을 해주면 정답이다.점 a, b, c, d로 이루어진 도형을 보면 abc의 ccw 결과는 파란색, acd의 ccw 결과는 빨간색이다...

문제: https://www.acmicpc.net/problem/16946난이도: G2 격자에서 bfs를 활용하는 문제였다. 모든 벽에서 bfs를 돌리면 시간초과가 난다. 따라서 시간을 줄일 수 있는 구현 방법이 필요하다. 주요 아이디어는 이동할 수 있는 곳이 이어진 부분을 미리 계산하여 묶어두는 것이다. 간단하게 000100 이라는 예시가 있다고 하자. 000부분은 미리 3이라고 계산할 수 있고, 00 부분은 2라고 계산을 해둘 수 있다. 단순한 구현처럼 1에서 bfs를 돌리면 주변 0을 모두 방문하여 시간이 많이 필요하지만, 미리 계산해두면 상하좌우(위 예시는 좌우만 있다) 한 칸만 보고도 이동할 수 있는 칸 수를 알 수 있다. 구현에서는 0이 이어진 부분의 수를 bfs로 계산하였고, 같은 번호로..

문제: https://www.acmicpc.net/problem/1412난이도: P4 최근에 위상정렬에 대해 공부하고 관련 응용 문제를 풀어보았다. 모든 도로는 양방통행 or 일방통행 도로로 연결되어있다. 이 문제의 목표는 양방통행을 일방통행으로 바꾸어 x도시에서 출발하여 다시 x도시로 도착하는 경우가 없도록 하는 것이다. 출력으로 목표가 가능하면 'YES' 불가능하면 'NO'를 출력한다. 결론부터 말하면 단방향으로만 이루어진 사이클이 만들어지는 경우에 'NO'를 출력하면 된다. 양방향은 단방향으로 바꿀 수 있다. 따라서 양방향이 포함된 사이클은 무조건 사이클이 안 되도록 할 수 있다. 구현에서는 양방향인 도로는 연결이 안 되어있는 것으로 취급하였다. 이제 사이클이 있는지 판단만 하면 된다. 위상정..

위상 정렬이란 어떤 일들을 순서대로 해야 할 때, 선행 조건이 있는 작업들의 실행 순서를 정하는 방법이다. 방향 비순환 그래프(DAG, Directed Acyclic Graph)에서 적용가능하다. DFS기반과 BFS기반으로 구현할 수 있다. 이 글에서는 BFS기반으로 작성했다. 위상 정렬 알고리즘의 작동 과정은 아래와 같다. 1. 진입 차수가 0인 node를 queue에 넣는다.2. queue에 넣은 노드의 다음 node의 진입차수를 1 줄인다.3. q가 비어있을 때까지 2를 반복한다. 코드로 작성하면 아래와 같다. int st[32001]; // 노드들의 진입차수vector graph[32001]; // 노드 연결int N; // 노드의 수queue q;vector ans;void ts() { for..

문제: https://www.acmicpc.net/problem/28082난이도: G12023 인하대학교 프로그래밍 경진대회(IUPC) I번 문제 조건을 대충보면 N, K의 범위가 500으로 완전탐색을 하면 될 것 같아 보인다. 하지만 완전탐색의 경우 배터리 N개 중 1개 이상 K개 이하를 선택하는 모든 조합의 수이다. 따라서 시간복잡도를 줄여야한다. $O(_{N}C_1 + _{N}C_2 + ... + _{N}C_K )$ 배낭 문제를 응용하면 1차원 dp로 풀 수 있다. dp[i]: 전력량 i를 만들 수 있는 최소 배터리 수이다. 여기까서 생각해서 dp[0]부터 dp[50000]까지 가면서 min으로 최소 배터리 수 넣어주면 되겠다고 생각하면 안 된다. 문제 조건에서 각 배터리는 중복사용이 안 된다...

문제: https://www.acmicpc.net/problem/31858난이도: G32024 인하대학교 프로그래밍 경진대회(IUPC) L번 문제 조건을 식으로 보면 뭔가 싶지만 히스토그램으로 보면 쉽다.예제 입력 1을 보면 4 2 3 1 5이다. 막대기 2개(a, b)를 골라서 그 사이에 a와 b보다 작은 값만 있으면 된다. 예를 들어 index (0, 4)를 선택하면 그 사이 값들은 (0, 4)보다 작으므로 문제 조건에 만족한다. 물론 붙어있는 두 수( 0 1이나 1 2, 2 3 같은 조합)는 무조건 조건에 만족한다. N이 200,000이므로 완전 탐색으로는 O(N^2)이므로 시간초과가 난다. 자료구조나 알고리즘 수업에서 한 번쯤 stock span 문제을 들어봤을 것이다. 히스토그램을 그려보면 st..

문제: https://www.acmicpc.net/problem/31851난이도: G42024 인하대학교 프로그래밍 경진대회(IUPC) F번 문제를 요약하면 "N개의 점에서 4개를 선택하는 모든 경우에서 볼록한 사각형이 몇 개 만들어지나?" 이다. 문제 오래 째려보고 든 생각은 점 3개로 삼각형을 만들고 남은 점이 삼각형 밖에 있으면 볼록 사각형을 만들 수 있겠다는 것이었다. 거기서 더 나아가서 점 4개로 선분 2개를 만들고 선분이 교차하면 볼록 사각형이 된다는 사실을 깨달았다. 그래서 관련 알고리즘을 찾던중 ccw로 선분이 교차하는 것을 판단할 수 있다는 것을 알아서 적용시켰다. ccw로 선분 교차 판단하는 알고리즘은 구글에 많으니 생략하겠다. 간단히 말하면 네 점으로 ccw를 수행한 결과가 둘 다..

문제: https://www.acmicpc.net/problem/31849난이도: G42024 인하대학교 프로그래밍 경진대회(IUPC) E번 문제를 보면 bfs를 사용해야 한다는 것을 바로 알 수 있다. 모든 집에서 가장 가까운 편의점을 찾아가는 방식으로 작성하면 bfs를 여러번 돌려야 하므로 시간초과가 난다. 역으로 편의점에서 가장 가까운 집을 찾으면 된다. 이 방식도 편의점 마다 bfs를 따로 돌리면 시간초과가 난다. (최악의 경우를 생각하면 O(N^2M^2) 정도 나올 것 같다.) 따라서 초기에 편의점 위치를 queue에 넣어두고 bfs를 한 번만 돌리면 된다. 편의점끼리 길이 겹치면 안 되지 않나? 라는 생각이 들 수 있는데, 잘 생각해보면 이미 지나간 길은 최소 거리이다. 그래서 편의점 위치를..

문제: https://www.acmicpc.net/problem/31848난이도: S22024 인하대학교 프로그래밍 경진대회(IUPC) D번 입력 범위를 보면 100000으로 O(N^2)은 시간 초과일 것으로 예상할 수 있다. 문제를 읽어보면 이분탐색을 사용하는 문제라는 것을 쉽게 알 수 있다. 하지만 입력 그대로 이분탐색을 적용하려고 하면 문제가 발생한다. 배열이 정렬이 되어있지 않다. 문제를 살짝 바꿔서 이해하면 정렬이 된 배열을 만들 수 있다. 도토리가 굴러 떨어지면서 크기가 1씩 감소하는 것을 구멍의 크기가 1씩 커지는 것으로 생각해보자. 구멍의 크기를 입력 받을 때 1씩 키워가면서 (+0, +1, +2, ...) 저장하면 된다. 그래도 배열이 정렬이 되어있지 않다. 앞에 구멍이 뒤에 구멍보다..