문제 0에서 n까지 숫자 한개로 이루어진 n+1개의 집합이 있다. 합집합 연산(0)과 두 원소가 같은 집합에 포함되는지 여부를 확인하는 연산(1)을 수행할 때, 같은 집합에 포함되면 yes, 아니면 no를 출력하는 문제이다. 연산은 연산종류(0,1), a원소, b원소 순서대로 입력된다. 풀이 이 문제는 각 원소가 포함된 집합의 대표 번호(부모 노드)를 저장함으로써 합집합 연산에서는 두 원소의 부모 노드를 더 작은 번호로 일치시켜주고 (union) 두 원소의 집합이 같은지 확인하는 연산에서는 부모 노드가 동일한지 확인하면 되기 때문에 (find) 분리집합 알고리즘으로 해결할 수 있다. 먼저 부모 노드들을 담을 parent(p) 리스트를 생성한다. 초기 부모 노드는 각 집합에 담겨있는 숫자의 번호로 초기화한..
문제 상근이와 선영이가 동시에 갖고 있는 cd의 개수를 구하면 되는 문제이다. 다만 주의할 점은 여러 개의 테스트 케이스로 이루어져 있다는 점이다. 예제는 한 개만 나와 있어 헷갈릴 수 있어 조심해야한다. 풀이 이 문제는 자료구조로 접근하면 쉽다. 중복되는 cd 번호가 없기 때문에 set 집합 자료구조를 사용하면 된다. 즉, 상근이의 cd 집합과 선영이의 cd 집합의 교집합 개수를 구하면 된다. 집합에 담을 땐 add 함수를 통해 넣고, 교집합(&)은 set(a) & set(b)와 같은 방법으로 구할 수 있다. 혹은 교집합을 구하는 대신 상근이의 cd 집합에 선영이가 가진 cd가 포함되는지 셈을 통해 구할 수도 있다. set 집합의 경우에는 탐색 시간이 O(1)이기 때문에 속도도 조금 더 빠르고, 선영이..
[백준 BOJ / Python] 25194번 결전의 금요일 DP
문제 각각의 일을 끝내는 데 걸리는 시간(일)이 담겨 있는 A 배열이 주어졌을 때, 일의 순서를 바꾸어 헬스장에 갈 수 있는 경우는 YES, 갈 수 없다면 NO를 출력하는 문제이다. 문제 조건 오늘은 월요일이다. 금요일에 일을 끝내야 헬스장에 간다. 풀이 일주일은 7일이기 때문에 월요일부터 일요일을 0에서 6으로 둔다. 월요일에 일을 시작해서 금요일에 끝나려면 7로 나누었을 때 나머지가 4인 날이 있는지 확인하면 된다. 따라서 숫자의 조합에 따라 합계를 7로 나눈 나머지가 4가 되는 경우가 있는지 살핀다. 시간에 대한 연산과 나머지에 대한 연산의 결과가 같다는 것을 활용한다. ex) (15+ 9) % 7 = (1 + 2) % 7 = 3 A 배열의 요소(a)들을 모두 순회하면서 먼저 계산된 나머지와 연산을..
[백준 BOJ / Python] 1965번 상자넣기 DP
문제 상자의 크기가 입력된 배열이 주어졌을 때, 앞에서부터 작은 상자를 뒤의 큰 상자에 넣는다면 최대 몇 개의 상자를 겹칠 수 있는지 개수를 묻는 문제이다. 풀이 왼쪽의 작은 상자를 오른쪽의 큰 상자에 넣는다는 것은 오른쪽으로 이동하면서 오름차순으로 증가하는 상자를 골라야 한다고 말할 수 있다. 즉, 상자배열 내에서 가장 긴 증가하는 부분 수열 (LIS) 을 구한다면, 겹칠 수 있는 최대 상자의 개수를 알 수 있다. 알고리즘 겹치는 상자의 개수를 담는 dp 를 1로 초기화한다. 상자의 크기가 담긴 box 배열을 순회한다. 해당 상자의 이전에 있는 상자들과 비교하면서 담을 수 있는 상자라면, 이전 상자에 담기는 상자의 개수(dp[j])에 1을 더한 값과 현재 dp[i]에 담긴 값을 비교하여 더 큰 값을 d..
[백준 BOJ / Python] 25338번 바지 구매 math
문제 주어진 하체 둘레 공식을 참고하여 새로 산 바지를 입었을 때, 둘레가 커서 흘러내리지 않으면서 바닥에 끌리지 않는 바지의 개수를 구하는 문제이다. 문제 조건 하체 둘레 공식 : $f(x) = max(a(x-b)^2 + c, d)$ 바지는 하체 둘레가 가장 큰 위치보다 높거나 같은 곳에서만 걸린다. 풀이 바지의 하체 둘레가 가장 큰 위치는 $f(x) = max(a(x-b)^2 + c, d)$ 공식에 따라 바닥으로부터 $b$의 위치를 의미한다. 바지는 하체 둘레가 가장 큰 위치보다 높거나 같은 곳에서만 걸리기 때문에, 바닥으로부터 길이가 $b$보다 작은 경우는 바지가 짧은 것임을 알 수 있다. 즉, 바지의 길이는 $b$ 길이보다 같거나 커야 한다. 바지의 길이가 $v$일 경우, 바지의 ..
[백준 BOJ / Python] 2565번 전깃줄 DP
문제 두 전봇대 A와 B 사이에 몇 개의 전깃줄을 제거해야 교차하는 전깃줄이 없는지 구하는 문제이다. 즉, 최소한의 제거할 수 있는 전깃줄의 개수를 도출해야 한다. 풀이 서로 전깃줄이 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구해야 한다. 예를 들어, A-1번과 B-8번이 연결된 전깃줄보다 A-3번과 B-9번이 연결된 전깃줄이 더 아래 있는 것을 알 수 있다. 이를 통해 A의 번호가 순차적으로 커질 때, 각각의 A와 연결된 B의 번호도 더 커진다면 교차하지 않는 전깃줄의 개수를 구할 수 있음을 알 수 있다. A의 정렬된 번호를 리스트의 인덱스로 두고, B의 번호를 가지고 가장 긴 증가하는 수열(LIS)을 구함으로써 교차하지 않는 전깃줄의 최대 개수(c)를 구할 수 있다...