개발 일지

서로소 집합 (union find) 서로소 집합이란, 공통되는 부분집합이 존재하지 않는 두 집합을 의미한다. 이 개념을 통해 다루게 될 문제는, 바로 어떤 두 그래프가 서로소 집합 관계인지 확인하는 것이다. 이를 확인하는 알고리즘을 union find 알고리즘이라고 하는데, 각 노드가 같은 부모를 가리키는지 확인하는식의 접근이라고 보면된다. 필자는 이런 상황을 이전에 마주한적이 있다. 전력망을 둘로 나누기 (lv2) (tistory.com) 전력망을 둘로 나누기 (lv2) 문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖 forteqook.tistory.com 바로 ..

A가 어떤 공을 고르면, B는 반드시 A가 고른 공과는 다른 무게를 가진 공을 골라야 한다. 그리고 이 문제에서 중요한 것은 두 사람중 어떤 사람이 공을 집었는지는 사실 상관 없다는 것이다. 다시말해 A가 1번 공을 집고 B가 2번 공을 집는 경우와 A가 2번 공을 집고 B가 1번 공을 집는 경우는 완전히 같은 경우라는 말이다. 따라서 단순히 조합문제로 다음과 같이 풀 수 있다. from itertools import combinations from collections import Counter n,m = map(int, input().split()) data = list(map(int, input().split())) result = 0 for c in combinations(Counter(data)..

지니고 있는 동전들로 만들 수 없는 target 값을 찾아야 하는데, 바꿔말하면 지니고 있는 동전들로 target-1까지의 모든 금액을 만드는 방법을 찾아야 한다. 따라서 금액이 최소인 동전부터 하나씩 조합해보면서 만들 수 있는 target-1값을 갱신하겠다는 아이디어가 핵심이 되겠다. 위 예시와 같이 현재 동전이 1,1,2,3,9원이 있다고 하자. 1원 하나로 만들 수 있는 금액은 다음과 같을 것이다. 1 = 1 1원까지는 1원 하나로 전부 만들 수 있으니, 또 1원을 추가하여 [1,1]원으로 만들 수 있는 금액은 다음과 같을 것이다. 1 = 1 1 + 1 = 2 2원 까지는 [1,1]원으로 전부 만들어 볼 수 있으니, 2원을 추가하면 경우의 수는 다음과 같을 것이다. 1 = 1 2 = 2 1 + 2 ..

각 그룹을 최소한의 인원으로 짜면 최대의 그룹 수를 얻을 수 있다는 아이디어가 핵심이다. 조건에서 공포도가 X인 모험가는 반드시 X명 이상으로 구성된 그룹에 들어가야 하고, 이러한 그룹을 최대한 많이 만들기 위해서는 공포도가 X인 사람은 딱 X명으로 구성된 그룹으로 묶어주는것이 좋겠다. 예시로 주어진 2, 3, 1, 2, 2 의 경우, 1 단 한명으로 구성된 그룹, 2 두명으로 이루어진 그룹으로 짜서 총 두개의 그룹을 만드는게 정답이 되는데, 모든 모험가가 그룹을 맺을 필요가 없으며 공포도가 큰 모험가 일수록 많은 인원을 필요로 하며, 결과적으로 비용이크므로 선호도가 떨어진다는 이야기가 된다는 사실에 기반하여 정답으로 판단 가능하다. 위 가정을 구현하기 위해 주어진 배열을 오름차순으로 정렬한 뒤 공포도에..

본 문제는 반복적으로 문자 삽입, 삭제, 교체 중 최적의 선택을 시행한다는 점에서 DP로 접근한다는 아이디어는 타당하다. 소개할 방법에서는 기본적으로 문자열 A를 순회하며 문자열 B와 비교해 현재 인덱스에 해당하는 문자에 와야할 문자를 삽입할지, 삭제할지, 교체할지 결정한다. 아래 표는 A에 sunday, B에 saturday가 입력된 경우 편집 거리 DP 테이블 이다. 여기서 편집 거리란 특정 행상태의 A가 특정 열상태의 B까지 도달하기 위한 최소 비용이다. 맨 처음 테이블을 초기화 할 때는, 문자열 A가 아무것도 입력되지 않았을 때 B의 saturday까지 입력되려면 총 8의 편집 거리가 소요되므로 dp[0][8] = 8 이 되고, 마찬가지로 문자열 B가 비어있을 때 A의 sunday가 되려면 총 6..

이해하는데 꽤 애먹은 문제였다. 풀이 자체는 굉장히 간단하다. 못생긴 수에 2,3,5 중 하나를 곱해준 결과는 항상 못생긴 수라는 것이다. 바꿔 말하면, 1부터 시작해서 2,3,5를 각각 곱해가며 못생긴 수를 만들고, 오름차순으로 나열해야 하니 후보 숫자들 중 최소값을 못생긴 수 배열 끝에 담아주는 것이다. next가 의미하는 것은, 모든 못생긴 수에 대해 2,3,5를 각각 곱해본다는 의미이다. 코드 n = int(input()) ugly = [0]*n ugly[0] = 1 i2 = i3 = i5 = 0 next2,next3,next5 = 2,3,5 for l in range(1,n): ugly[l] = min(next2,next3,next5) if ugly[l] == next2: i2 += 1 next..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.