CodeAngie

문제마을에는 N개의 집이 순서대로 원 형태로 서로 이웃해 있다. 각 집에는 돈이 보관되어 있으며, 이 돈의 양은 숫자로 표시된다. 도둑은 M개의 연속된 집에서 돈을 훔치기로 하였고, 만약 도둑이 훔친 돈의 총액이 K원 이상이 되면 방범장치가 작동하여 붙잡히게 된다. 따라서 도둑이 붙잡히지 않고 무사히 마을을 빠져나가기 위해 돈을 훔칠 M개의 연속된 집을 선택하는 방법의 수를 구해야 한다. 풀이이 문제에서 중요한 점은 집들이 원 형태로 이웃했다는 점이다.원의 형태이기 때문에 위 그림의 오른쪽 이미지들처럼 7번 집을 지나 0번 집까지 연속으로 돈을 훔치는 것이 가능하다.도둑질을 시작하는 집을 기준으로 0부터 n-1까지 m칸씩 합계를 구해, 방범 장치가 울리지 않는 크기가 총 몇 가지 있는지 구하면 된다.주의..

문제 n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다. 이 문제의 조건은 다음과 같다. 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. 예를 들어, n=17일 때까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 풀이 피보나치 수는 특정 숫자로 나누었을 때 나머지가 항상 주기를 갖는다는 특징이 있다. 이를 피사노 주기(Pisano Period)라고 한다. 예를 들어 피보나치 수를 4로 나누었을 때 나머지..

문제두 별 사이의 거리만큼 별자리를 만는 비용이 든다고 할 때,n개의 별들을 이어 별자리를 만드는 최소 비용을 구하는 문제이다.별자리의 조건두 별 사이의 거리는 서로 다른 두 별을 일직선으로 이은 선의 길이와 같다.모든 별은 직/간접적으로 연결되어 있다.풀이두 별 사이의 거리를 가중치로 두고, 크루스칼 알고리즘을 이용하여 최소 비용을 구한다.직각 삼각형의 대각선의 길이를 구하는 공식을 이용하여 가중치를 구한다.$c^2 = a^2 + b^2 $ $c = \sqrt{{a}^2 + {b}^2}$ $c = \sqrt{(x1-x2)^2 + (y1-y2)^2}$가중치와 두 별의 번호를 간선 list 에 저장한다.가중치를 기준으로 오름차순으로 간선 list를 정렬한다.작은 가중치부터 순서대로 별들을 연결한다. (부모..

문제그래프가 주어졌을 때 최소 스패닝 트리(최소 신장 트리)를 구하고 그의 가중치를 출력하는 문제이다.풀이크루스칼 알고리즘을 사용하여 가중치를 계산한다.간선(edge)을 가중치가 작은 순으로 정렬한다.부모 노드를 자기 자신으로 초기화한다.가장 작은 가중치부터 순서대로 노드를 서로 연결한다.노드를 서로 연결한다는 것은 두 노드가 같은 루트를 갖게 한다는 의미이다.즉 부모 노드가 다를 경우, 아직 서로 연결이 안 된 노드이기에union을 통해 부모 노드를 동일하게 만들어 줌으로써 서로 연결하는 것이다.Python 코드import syssys.setrecursionlimit(10**6)input = sys.stdin.readlinev,e = map(int,input().split())edges = [list(..

문제 5*3 개의 전구를 통해 0~9까지의 숫자를 표현할 수 있을 때, 전구가 망가졌을 수도 있음을 가정하고, 켜진 전구들을 살펴보아 만들 수 있는 숫자들의 평균을 구하는 문제이다. 층 안내판의 크기는 5*3 판을 여러 개 이어 붙인 형태이며 판 사이의 꺼진 전구가 존재한다. 풀이 먼저 문제에서 주어진 0~9까지의 표현을 가지고 5*3 판 위의 어떤 전구가 켜졌을 때 어떤 숫자를 만들 수 있는지 판별해야 한다. 예를 들어 5*3 판을 기준으로 (0,0) 위치의 전구가 켜지면 만들 수 있는 숫자들(0,2,3,4,5,6,7,8,9)을 저장한다. 같은 간격으로 숫자가 있기에 (i, j+k*4)를 통해 동일한 위치의 전구들을 확인할 수 있다. 각각의 판이 만들 수 있는 숫자들을 추출한다. 만약 (3,0) 위치의..

문제 0에서 n까지 숫자 한개로 이루어진 n+1개의 집합이 있다. 합집합 연산(0)과 두 원소가 같은 집합에 포함되는지 여부를 확인하는 연산(1)을 수행할 때, 같은 집합에 포함되면 yes, 아니면 no를 출력하는 문제이다. 연산은 연산종류(0,1), a원소, b원소 순서대로 입력된다. 풀이 이 문제는 각 원소가 포함된 집합의 대표 번호(부모 노드)를 저장함으로써 합집합 연산에서는 두 원소의 부모 노드를 더 작은 번호로 일치시켜주고 (union) 두 원소의 집합이 같은지 확인하는 연산에서는 부모 노드가 동일한지 확인하면 되기 때문에 (find) 분리집합 알고리즘으로 해결할 수 있다. 먼저 부모 노드들을 담을 parent(p) 리스트를 생성한다. 초기 부모 노드는 각 집합에 담겨있는 숫자의 번호로 초기화한..

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