💻

문제이해 선분들이 주어질 때, 그 선분들이 교차하거나 닿는 부분이 있다면 같은 그룹으로 묶고, 아니라면 다른 그룹으로 취급하여, 그룹의 개수와 그룹들 중 선분이 가장 많은 그룹의 선분 개수를 출력하는 문제이다. 계획 이 문제는 두가지 부분으로 나눠진다. 1. 먼저 선분 두 개가 주어졌을 때 교차하는지 확인하는 함수가 필요하다. 2. 만약 교차할때, 같은 그룹으로 묶어주는 함수가 필요하다. 1번 같은 경우는 ccw를 이용하여요 선분이 교차하거나 맞닿는지 확인하면 되고, 2번 같은 경우는 union-find를 이용해서 같은 그룹으로 묶어주면 된다. 마지막으로, 그룹의 크기를 출력해야하므로 union 할 때마다 각 그룹의 root에 해당하는 원소에 그룹의 위치를 계속해서 저장해 주면 나중에 쉽게 출력할 수 있..

문제이해 문제가 호흡이 긴데 요약하자면 1로 된 섬과 0으로 된 바다로 이루어진 매트릭스가 주어질 때 최소 비용으로 그 섬을 모두 연결하는 문제이다. 다만, 다리는 직선이어야 하고 길이가 2 이상 이어야 한다. 계획 일단 이문제의 핵심은 모든 섬을 최소비용으로 연결해야 한다는 점이다. 이 점만 본다면 일반 최소신장트리(MST) 문제와 다르지 않다. 크루스칼을 쓰면서 섬을 추가하면 된다. 다만 그러기 위해서는 각 섬과의 다리 개수와 길이, 섬의 개수가 필요하다. 따라서, 첫 번째로 주어지는 매트릭스에서 그러한 정보를 추출해야 한다. 이 문제의 대략적인 순서는 아래와 같아야 한다. 1. 매트릭스에서 섬위치와 개수 파악 2. 매트릭스에서 다리 개수와 길이 추출 3. 크루스칼 먼저 매트릭스에서 섬이 같은 섬인지..

1 2 3 4 5 6 1 2 (2, 3) 3 (3, 5) 4 5 (5, 5) 6 문제이해 (1, 1)과 (n, n)에 있는 경찰차 두대가 최소거리로 사건들을 해결하는 방법과 거리를 출력하는 문제이다. 계획 이 문제가 어렵게 느껴지는 이유는 경찰이 현재 있는 위치에 따라 추가되는 거리가 계속해서 달라지기 때문이다. 따라서, 기존의 dp문제처럼 dist[n+1] = dist[n] + min(police1[n], police2[n])와 같은 점화식은 사용할 수 없다. 각 경우에 따라 거리가 달라지기 때문에 모든경우의 수를 탐색하는 방법을 생각할 수 있지만. 사건이 n개일 때의 경우의 수는 2^n개다. 사건이 3개일때의 경우의 수 111 112 121 122 211 212 221 222 사건의 개수가 1000개..

문제이해 정수로 이루어진 수열 num과 s가 주어지면, num안의 원소중 더한 값이 s가 되도록 하는 경우의 수를 구하는 문제이다. 계획 먼저 브루스포트로 푸는 경우의 시간복잡도는 2^40으로 1초이내 푸는 것이 불가능하다. 따라서, 시간복잡도를 O(2^N)인 알고리즘을 O(2^(N/2))로 줄일 수 있는 Meet In The Middle 알고리즘을 활용하면 해결할 수 있다. MITM(Meet In The Middle) MITM은 N이 그렇게 크지 않지만 완전 탐색을 진행하기엔 무리가 있다고 판단할 때 주로 사용하는 알고리즘이다. 배열을 완전탐색 한다면 O(2^N)시간복잡도가 나올 걸, 배열을 반으로 나눈 뒤 각각의 조합을 구해 O(2^(N/2)+2^(N/2))=O(2^(N/2)) 경우의 수가 나오게 하..

문제이해 음의 간선이 있을 때 최단거리를 구하는 문제다. 계획 가중치가 있는 간선의 최단거리를 구하는 문제이므로 다익스트라를 생각할 수 있으나, 음의 간선이 있으므로 다음과 같은 경우가 생겨 다익스트라는 사용할 수 없다. 음의 간선이 있을 때 다음과 같은 경우가 있을 수 있다. 모든 간선이 양수인 경우 음수 간선이 있는 경우 음수 간선 순환이 있는 경우 음수 간선 순환이 없는 경우 만약 음수 간선 순환이 있는 경우, 그 사이클을 지나는 모든 노드들의 최단거리가 무한히 음수로 갱신된다. 따라서, 벨만-포드 알고리즘을 이용하면, 이런 경우들을 고려하여 최단거리를 구할 수 있다. 벨만-포드 알고리즘 벨만-포드 알고리즘은 다익스트라와 유사하다. 다른 점은 다익스트라는 조건에 맞는 몇몇 간선만 탐색한다면, 벨만-..

문제이해 0~9까지의 숫자를 적어도 한 번씩은 거치면서 계단 수를 만들 수 있는 경우의 수를 구하는 문제다. 단, 0으로 시작할 수는 없다. 예를 들어, 10자리의 계단 수를 만들 수 있는 경우는 9876543210 밖에 없으므로 한 가지밖에 없다. 계획 0~9까지의 숫자를 적어도 한번씩 거친다는 조건이 없다고 생각하자. 행이 n, 열이 10인 2차원 배열 t가 있다고 하면, t[0]부터 t[n-1]까지 t[i][ii] (0