알고리즘/BOJ33 [BOJ] 9466. 텀 프로젝트 문제https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을www.acmicpc.net 주요 아이디어처음에는 BFS 방식으로 접근하고자 했다.1. BFS를 수행해 그래프가 완성되는지 판단2. 그래프가 완성될 경우 그래프에 속한 노드를 반환 / 아닐 경우 None을 반환3. 시작 노드 순차적으로 순회하며 BFS를 수행하고, 그래프가 만들어진 노드들의 개수를 제하면 그래프가 완성되지 않은 노드들의 개수만 남게 됨 코드 구현 (Python 3)더보기.. 2024. 4. 24. [BOJ] 12852. 1로 만들기 2 문제https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.www.acmicpc.net 주요 아이디어앞에서 풀었던 '1로 만들기' 문제의 로직을 그대로 가져다 쓰려고 했다. 코드 구현 (Python 3)더보기 n = int(input())dp = [0] * (n+1)# dp[i] = i를 만들기 위해 필요한 최소 연산횟수for i in range(2, n+1): # 1을 빼기 dp[i] = dp[i-1] + 1 # 2로 나눠진 것 전에서 더하기 1 if i % 2 == 0: dp[i] = mi.. 2024. 4. 24. [BOJ] 1463. 1로 만들기 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 주요 아이디어 1~n까지의 dp list를 만들고, 해당 숫자를 만들기 위해 필요한 최소 연산 횟수를 구하면 된다. 코드 구현 (Python 3) 더보기 n = int(input()) dp_list = [0] * (n+1) # 1로 만들기니까 2 이상부터 시작 for i in range(2, n+1): # 기본적으로 할 수 있는 연산 = 이전 연산횟수에서 빼기 한번이므로 +1 dp_list[i] = dp_list[i-1] + 1 if i%2 == 0: # 이전 연산 (i*2) 에서 나누기 한번이므로 +1 .. 2024. 4. 21. [BOJ] 12865. 평범한 배낭 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 개인적으로 좀 어려웠던 문제.. 주요 아이디어 처음 생각했던 방법은, 가치 기준 내림차순 & 같은 가치일 경우 무게 기준 오름차순 한 다음 for문을 돌면서 하나씩 더해주며 최대값을 찾는 방법이었다. 코드 구현 (Python 3) 더보기 n, k = map(int, input().split()) items = [] for _ .. 2024. 4. 21. [BOJ] 1026. 보물 문제 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 주요 아이디어 전체 합을 최소값으로 만들려면, (현재 A배열의 최대값) * (현재 B배열의 최소값) 을 하나씩 더해주면 된다. 코드 구현 (Python 3) 간단하게 풀려면, A를 오름차순 / B를 내림차순 해서 곱한 후 하나씩 더해주면 된다. 더보기 n = int(input()) a = list(map(int, input().split())) b = list(map(int, inpu.. 2024. 4. 21. [BOJ] 14501. 퇴사 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 돈미새 백준이.. 주요 아이디어 풀 때마다 항상 느끼지만 DP 문제는 정말 아이디어가 중요한 것 같다.. 앞에서 (i=1) 부터 접근하지 말고, 맨 끝 날짜부터 접근해보자 매 상담에 대해 현재 상담일자의 이윤 + 현재 상담을 마친 일자로부터의 최대 이윤 계산 즉 dp[i] = i번째 날 ~ n번째 날까지 낼 수 있는 최대 이익이다 예제 살펴보기 더보기 7일차에는 상담이 불가하다 상담 소요 일자 + 현재 일자 = 2 + 7 > n 이기 때문이다 dp[7] = 0, max_value = 0 6일차에도 상담이 불가능하다 상담 소요 일.. 2024. 4. 6. 이전 1 2 3 4 5 6 다음
