📁문제 풀이/🧩Baekjoon

[Python] 백준 1003 피보나치 함수 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 해결 포인트 - DP - 입력값(1~40) 에 따라 0과 1이 불린 횟수를 점화식을 이용하여 구할 수 있다 - 입력값 0은 0이 1회/1이 0회 불린다. 입력값 1은 0이 0회/1이 1회 불린다. - 입력값이 2라면 f(2) = f(1) + f(0) 이므로 1이 한 번, 0이 한 번 불린다. - 입력값이 3이라면 f(3) = f(2) + f(1) 이므로 f(2) 실행시 1한 번, 0 한 번 불린 것과 1이 한 번 불린 것을 더하면 1이 2번..

[Python] 백준 9095 1, 2, 3 더하기 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 해결 포인트 - DP(다이나믹 프로그래밍)의 전형적인 문제이다 - DP는 한번 진행한 계산에 대해서 저장 해두고 또 발생시 계산 값만 사용한다. - 해당 코드에서 numbers 배열은 계산 결과 값을 저장해두는 역할을 한다. - 1, 2, 3을 이용하여 1, 2, 3을 만드는 방법을 생각해보자 1 = 1 1을 만드는 방법은 1개(numbers[1] = 1) 2 = 1 + 1 2 = 2 2를 만드는 방법은 2개(numbers[2] = 2) 3 ..

[Python] 백준 1715 카드 정렬하기 | 그리디 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 해결 포인트 - 작은 카드 뭉치들 부터 순서대로 처리해야 하므로 그리디 알고리즘입니다! - 카드 뭉치가 1개라면 비교할 뭉치가 없으므로 0 반환 - 카드 뭉치가 3개 이상이라면 최소값 2개를 뽑아 순서대로 연산(우선순위 큐) - 큐 안에 뭉치가 2개 남았다면 더이상 최소 값 2개를 찾지 않고 연산 값을 더하여 출력 & 반복문 종료..

[Python] 백준 1774 우주신과의 교감 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1774 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 문제 해결 포인트 - 크루스칼 알고리즘 - dots : 각 점(정점, 노드) 별 x, y 좌표 저장 - edges : 간선의 비용 기준으로 오름차순 - parent : 정점 별 속한 집합 정보 - 각 정점 정보를 순서대로 dots..

[Python] 백준 21924 도시 건설 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 문제 해결 포인트 - 크루스칼 알고리즘 작성 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) parent = [i for i in range(N..

[Python] 백준 19368 행성 연결 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/19368 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 문제 해결 포인트 - 크루스칼 알고리즘 작성 코드 import sys input = sys.stdin.readline n = int(input()) edges = [] # 비용 오름차순을 위한 리스트 parent = [i for i in range(n+1)] # 서로소 집합 (본인을 부모로 갖도록 초기화) f..

[Python] 백준 14621 나만 안되는 연애 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 문제 해결 포인트 - 크루스칼 알고리즘 문제 - school : 정점 별 학교 성별 - parent : 정점 별 서로소 집합 정보 - edges : 간선의 비용 기준으로 오름차순 정보 저장 - 정렬된 edges를 순차적으로 접근하며 사이클이 발생하지 않으면 연결 - 서로소 집합이 정점 본인과 같은 정점의 개수..

[Python] 백준 6497 전력난 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제 해결 포인트 - 크루스칼 (최소 스패닝 트리) 알고리즘 - find 함수 : 부모 노드(어느 집합에 속하는지) 확인 - union 함수 : 정점 a, b를 같은 집합에 속하도록 parent 업데이트 - 여러 테스트케이스 있으므로 n, m이 0, 0 일때 종료 조건으로 무한 반복 - edges : 간선을 비용 기준 오름차순으로 저장 - parent : 각 ..

[Python] 백준 4386 별자리 만들기 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 해결 포인트 - 크루스칼 (최소 스패닝 트리) 알고리즘 - alist : 각 정점의 x, y 정보 저장 - edges : 정점 간 모든 간선 길이( sqrt((x1 - x2)**2 + (y1 - y2)**2) ) 를 오름차순으로 저장 - parent : 집합정보 ( 연결된 정점 정보) - find 함수 : 같은 집합에 속해있는지 확인 - unio..