문제 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로 나누었을 때 나머지..
[백준 BOJ / Python] 4386번 별자리 만들기
문제두 별 사이의 거리만큼 별자리를 만는 비용이 든다고 할 때,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(..
[백준 BOJ / Python] 1089번 스타트링크 타워
문제 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) 리스트를 생성한다. 초기 부모 노드는 각 집합에 담겨있는 숫자의 번호로 초기화한..
[백준 BOJ / Python] 17352번 여러분의 다리가 되어 드리겠습니다!
문제 N개의 섬이 존재하고 이들이 n-1개의 다리로 어떤 두 섬이든 이동할 수 있도록 연결되어 있다. 이때 다리 하나가 파괴되었고 새로운 다리를 연결해야할 때, 어떤 두 섬 사이에 다리를 연결하면 어떤 두 섬이든 이동할 수 있게 되는지 알아내는 문제이다. 풀이 이 문제에서 기존에 어떤 두 섬이든 이동할 수 있었다는 것은 모든 섬들이 하나의 집합을 이루고 있다는 뜻이다. 즉 모두 같은 부모 노드를 갖고 있다는 의미이다. 여기서 다리 하나가 없어졌다는 것은 1개의 집합이 끊어져 2개의 집합이 되었다는 것이다. 따라서 두 개의 집합의 섬(노드) 하나씩을 연결해주면 다시 1개의 집합으로 만들 수 있다. 즉, 두 집합의 부모 노드 끼리 연결해주면 되는 것이다. Union-Find 알고리즘을 사용해 두 개의 분리된..
문제 상근이와 선영이가 동시에 갖고 있는 cd의 개수를 구하면 되는 문제이다. 다만 주의할 점은 여러 개의 테스트 케이스로 이루어져 있다는 점이다. 예제는 한 개만 나와 있어 헷갈릴 수 있어 조심해야한다. 풀이 이 문제는 자료구조로 접근하면 쉽다. 중복되는 cd 번호가 없기 때문에 set 집합 자료구조를 사용하면 된다. 즉, 상근이의 cd 집합과 선영이의 cd 집합의 교집합 개수를 구하면 된다. 집합에 담을 땐 add 함수를 통해 넣고, 교집합(&)은 set(a) & set(b)와 같은 방법으로 구할 수 있다. 혹은 교집합을 구하는 대신 상근이의 cd 집합에 선영이가 가진 cd가 포함되는지 셈을 통해 구할 수도 있다. set 집합의 경우에는 탐색 시간이 O(1)이기 때문에 속도도 조금 더 빠르고, 선영이..