CodeAngie

문제 N개의 섬이 존재하고 이들이 n-1개의 다리로 어떤 두 섬이든 이동할 수 있도록 연결되어 있다. 이때 다리 하나가 파괴되었고 새로운 다리를 연결해야할 때, 어떤 두 섬 사이에 다리를 연결하면 어떤 두 섬이든 이동할 수 있게 되는지 알아내는 문제이다. 풀이 이 문제에서 기존에 어떤 두 섬이든 이동할 수 있었다는 것은 모든 섬들이 하나의 집합을 이루고 있다는 뜻이다. 즉 모두 같은 부모 노드를 갖고 있다는 의미이다. 여기서 다리 하나가 없어졌다는 것은 1개의 집합이 끊어져 2개의 집합이 되었다는 것이다. 따라서 두 개의 집합의 섬(노드) 하나씩을 연결해주면 다시 1개의 집합으로 만들 수 있다. 즉, 두 집합의 부모 노드 끼리 연결해주면 되는 것이다. Union-Find 알고리즘을 사용해 두 개의 분리된..

1. 분리집합 (Disjoint Set) 분리집합은 서로 겹치는 원소가 없는 상호 배타적인 집합들을 의미하며 서로소 집합이라고도 불린다. 전체 집합에 대하여 겹치지 않는 두 개 이상의 부분 집합이라 할 수 있다. 즉, 분리집합 알고리즘은 각 원소가 속하는 부분 집합을 찾아 분리를 하는 것이다. 예를 들어, 전체 집합 U에 대하여 짝수 집합 A와 홀수 집합 B는 서로 겹치는 원소가 없는 부분 집합들로 분리집합이라 할 수 있다. 2. Union-Find 알고리즘 시간복잡도: 평균적으로 O(logN)이며, 최악의 경우에는 O(n)이다. 트리구조를 사용한다. 하지만 이때, 자식노드가 부모노드 가리킨다는 것에 차이가 있다. 두 개 노드가 있을 때, 서로 같은 집합에 있는지 아닌지 판별하는 알고리즘이다. Find ..

문제 상근이와 선영이가 동시에 갖고 있는 cd의 개수를 구하면 되는 문제이다. 다만 주의할 점은 여러 개의 테스트 케이스로 이루어져 있다는 점이다. 예제는 한 개만 나와 있어 헷갈릴 수 있어 조심해야한다. 풀이 이 문제는 자료구조로 접근하면 쉽다. 중복되는 cd 번호가 없기 때문에 set 집합 자료구조를 사용하면 된다. 즉, 상근이의 cd 집합과 선영이의 cd 집합의 교집합 개수를 구하면 된다. 집합에 담을 땐 add 함수를 통해 넣고, 교집합(&)은 set(a) & set(b)와 같은 방법으로 구할 수 있다. 혹은 교집합을 구하는 대신 상근이의 cd 집합에 선영이가 가진 cd가 포함되는지 셈을 통해 구할 수도 있다. set 집합의 경우에는 탐색 시간이 O(1)이기 때문에 속도도 조금 더 빠르고, 선영이..

문제 초기 유성 위치 정보가 주어졌을 때, 한 덩어리의 유성이 땅위에 떨어졌을 때의 모습을 출력하는 문제이다. 유성은 "X", 땅은 "#", 공기는 "."으로 주어진다.. 유성은 가장 위에 존재하며, 맨 밑 줄은 모두 땅이다. 그리고 땅 위에 공기층이 적어도 1칸 존재한다. 유성은 수직으로 낙하하며, 유성과 땅의 원형은 변하지 않는다. 풀이 열 별로 유성과 땅 사이의 거리의 최솟값을 구하고 해당 거리만큼 유성만 이동시킨 모습을 출력해야한다. 열 별로 유성과 땅의 거리는 상단(0)에서부터 가장 먼 유성(meteor)과 가장 가까운 땅(i) 사이의 거리이다. 모든 열을 탐색하면서 유성(X)이 나타났을 땐 meteor 값을 업데이트하고, 최초로 땅을 만났을 때 meteor값과 i값 사이의 거리를 도출하여 (i..

문제 n*n 크기의 새 집이 있다. 집 수리를 위해 파이프를 옮겨야 하는데, 파이프는 무겁기 때문에 밀어서 이동시켜야 한다. 파이프는 2개의 연속된 칸을 차지하는 크기이며 3가지 방향으로 회전이 가능하다. 파이프를 밀 수 있는 방향은 →, ↘, ↓ 방향 총 3가지가 있으며, 회전은 45도만 가능하다. 따라서 다음 그림과 같이 가로일 때 2가지, 세로일 때 2가지, 대각선일 때 3가지가 있다. 또한 벽(1)으로는 파이프를 이동시킬 수 없다. 가장 처음에는 파이프가 가로 방향으로 왼쪽 상단에 위치해 있다. 파이프의 한쪽을 (n,n)으로 이동시키는 방법의 개수를 구하여라. 풀이 DP를 사용해 문제를 풀 수 있다. 마지막 위치(n,n)에 파이프가 도달할 수 있는 경우의 수 문제를 (i,j)에 파이프가 도달할 수..

문제 n가지 종류의 동전이 있다. 각 동전의 가치가 제시될 때, 그 가치의 합이 k원이 되도록 하는 경우의 수를 구하는 문제이다. 이때 순서가 달라도 구성이 같다면 같은 경우의 수이다. 풀이 이 문제는 dp를 사용해 풀 수 있다. 가치의 합이 k원(1 ≤ k ≤ 10,000)이 되도록 하는 경우의 수 문제를 나누어 가치의 합이 y(1 ≤ y ≤ k)가 되도록 하는 경우의 수를 구하는 부분 문제로 볼 수 있다. 동전 x1을 사용하여 y가 될 수 있는 경우가 성립하는지 확인하는 것이다. 다시 말해 y - x1을 만들 수 있는 조합이 있다면 해당 경우의 수만큼 x1을 가지고 y값을 만들 수 있다. 이를 통해 다음과 같은 식을 세울 수 있다. dp[y] = dp [y] + dp [y-x1] 알고리즘 dp 리스트..

문제 S의 문자들을 골라 T를 만들 수 있다. S에서의 순서대로 이어 붙여 새 문자열을 만드는 것을 반복하여 만들 수 있는 T의 최대 개수를 구하는 문제이다. 풀이 S에서의 순서가 유지돼야 함을 유의한다. S문자열에서 차례대로 문자를 살펴보며 T를 만들 수 있는 개수를 별도의 리스트에서 셀 수 있다. 예를 들어 S가 adabccb 이고 T가 abc일 때, 다음과 같이 셀 수 있다. T에 해당하는 알파벳이 순서대로 개수가 확보되어 있는지 확인할 수 있는 리스트를 생성한다. S의 1번째 a 문자는 T에 포함되며 이전 문자의 개수가 무한으로 현재 문자(a) 개수보다 많기 때문에 현재 문자에 1을 더한다. 2번째 문자인 d는 T에 포함되지 않으므로 넘어간다. 3번째 문자인 a는 첫번째와 마찬가지이기 때문에 a에..