알고리즘/코테 스터디 (2024)37 1495 기타리스트 💡문제 분석 요약마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 찾는다.볼륨은 0 이상 M 이하의 값만 가능하다.각 곡을 연주할 때, 주어진 볼륨 변화(V[i])로만 조절할 수 있다.💡알고리즘 설계2차원 배열 dp[i][j]를 정의하여, i번째 곡을 연주할 때 볼륨이 j인 상태를 기록.💡코드n, s, m = map(int, input().split())v = list(map(int, input().split()))def max_volume(n, s, m): # dp[i][j]는 i번째 곡을 연주할 때 볼륨이 j인 상태를 나타낸다. dp = [[0] * (m + 1) for _ in range(n + 1)] # 시작 볼륨 설정 : dp[0][S] = True dp[0][s] = T.. 2024. 8. 2. 12026 BOJ 거리 💡문제 분석 요약시작지점에서, 끝까지 가는데에 드는 최소비용을 계산한다.이동은 반드시 B -> O -> J 순서로만 이동할 수 있고, 해당 알파벳이 인접해있지 않으면 점프도 가능하다.점프할 때 드는 비용은 거리의 제곱만큼 든다.💡알고리즘 설계DP를 이용해서 점프를 할 때 어디 알파벳으로 점프해야 최소비용일지 계산한다.이중 for문으로 모든 원소에 대해서 비교한다.💡코드n = int(input())boj = input()# 여기서 dp[i]의 값은 해당 인덱스까지 가는데에 드는 에너지를 의미함.# 문제 조건에서 적힌 N의 최대값이 1000이라서, 첫번째에서 마지막으로 바로 점프하더라도 1000000을 넘지 않음dp = [1000000]*ndp[0] = 0for i in range(n): for .. 2024. 8. 1. 1654 랜선 자르기 💡문제 분석 요약이미 가지고 있는 랜선들은 길이가 제각각이다. 이것들을 이용해서 n개의 랜선이 더 필요하다.갖고 있는 랜선들을 n개로 만들 때, 최대길이가 되어야한다.💡알고리즘 설계지난번 풀었던 절단기 문제와 매우 유사해서 쉽게 풀 수 있었다. 이분탐색을 이용한다.💡코드k, n, = map(int, input().split()) # k : 이미 가진 랜선개수 / n : 필요한 랜선개수lans = []for i in range(k): lans.append(int(input()))left = 1right = max(lans)while left = n: left = mid + 1 else: right = mid - 1print(right)💡시간복잡도O(log N)💡.. 2024. 7. 31. 2805 나무 자르기 💡문제 분석 요약나무개수, 원하는 나무 길이, 각 나무들의 길이가 주어졌을 때 바닥에서부터 몇m가 되는 지점을 베어야 나무의 윗부분들을 잘라내어서 정확히 내가 원하는 나무의 길이만큼 베어갈 수 있는지를 구해야한다.중요한 것은 절단기가 아래서부터 시작한다는 것이다. 즉, 맨 아래를 자르는 것이 가장 많은 나무를 가져가는 경우이다.💡알고리즘 설계나무가 아닌 절단기를 대상으로 이분탐색을 진행한다.💡코드처음에 틀린 풀이이다. (아래 설명)n, m = map(int, input().split())tree = sorted(list(map(int, input().split())))# 절단기의 높이를 이분탐색으로 찾기# 절단기 높이는 짧을수록 나무를 더 많이 자르는 것임. (중요)def checkSum(mid):.. 2024. 7. 30. Programmers 입국심사 💡문제 분석 요약N명의 사람들이 심사관들에게 심사를 받는 최소 시간을 구해야한다.심사관마다 심사를 보는 시간은 제각기 다르다.이때 주의할 점은, 당장 내가 심사를 받을 수 있는 상황이더라도 잠시 기다렸다가 심사를 더 짧게 보는 사람에게 가는 것이 이득일 수 있다는 것이다. ex) 당장 가서 100분 심사받기 vs 1분 기다렸다가 20분 심사받기💡알고리즘 설계잠시 기다리는 대기시간을 고려한다는 점에서 DP로 풀 수 있다고 생각했지만, 입력 값이 10억인 것을 보고 안되는 것으로 판단했다...이분탐색을 이용해본다.💡코드def solution(n, times): # left = 최소시간 , right = 최대시간 left = 1 # 최소시간은 1분이상이라고 문제에 명시 ri.. 2024. 7. 29. 2661 좋은수열 💡문제 분석 요약숫자 1, 2, 3으로만 이뤄지는 수열 중에서 좋은 수열을 찾는다.임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이다.좋은 수열 중에서 가장 작은 값을 출력한다.💡알고리즘 설계모든 수열을 나열하고, 인덱스 0부터 끝까지 반복되는 구간이 있는지 확인해보려 했는데, 모든 수열의 경우의 수는 3^80이므로 불가능하다.모든 수열 중, 좋은 수열을 찾고 그 중에서 min을 찾기보다, 처음부터 min에서 시작해서 좋은 수열이라면 출력하는 쪽이 나아보인다.💡코드n = int(input())nums = []def check(idx): for i in range(1, (idx // 2) + 1): if nums[-i:] == nums[-2 * .. 2024. 7. 27. 1759 암호 만들기 💡문제 분석 요약조건에 맞는 암호 후보들을 출력한다.암호는 다음과 같은 조건이 있다. (1)오름차순 (2) 모음1개 자음2개 포함 (3) 암호 길이는 L💡알고리즘 설계combination으로도 풀 수 있다. 최대 15개의 알파벳이 들어오므로 15CL개를 뽑는다.백트래킹으로도 풀 수 있으므로 DFS를 활용한 백트래킹으로 풀어보았다.💡코드일단 결과적으로 아래 코드는 시간 초과로 틀렸다. 분석해보니 불필요한 조건검사가 많았다.# 처음 시도했다가 틀린 풀이 (시간초과)import sysinput = sys.stdin.readlinesys.setrecursionlimit(5000)# L : 암호 후보의 길이l, c = map(int, input().split())lst = sorted(list(input().. 2024. 7. 26. 1182 부분수열의 합 💡문제 분석 요약n개의 정수와, 목표합 s를 받아서 부분 수열의 합이 s가 되는 경우의 수를 구한다.💡알고리즘 설계DFS를 쓰지 않아도 풀 수 있어보인다. N의 개수도 20으로 그리 크지 않아서 for문으로 모든 경우를 다 구해도 되지 않을까 생각이 들었다.combination을 이용하여 1개, 2개, 3개 ..... n개를 뽑는 경우를 모두 구한 후, sum이 s와 같은지 비교하여 개수를 구한다.💡코드import sysfrom itertools import combinations as cbinput = sys.stdin.readlinen, s = map(int, input().split())lst = list(map(int, input().split()))# 부분 수열의 합이 s가 되는 개수를 구.. 2024. 7. 25. 6987 월드컵 💡문제 분석 요약월드컵 조의 경기 결과를 보고, 해당 결과가 나올 수 있는 결과인지 아닌지 판단한다.경기 결과는 4개 조에 대해서 주어진다.한 조에 6팀이 속한다.💡알고리즘 설계백트래킹으로 모든 경우의 수를 다 구할까 생각했었다.이는 3^15 경우의 수인데 이론상 가능하다고 생각했다.💡코드import sysfrom itertools import combinationsinput = sys.stdin.readlineanswer = []# 가능한 모든 게임 조합 - 총 15개 게임 (0,1), (0,2), ... , (4,5)game = list(combinations(range(6), 2))def backTracking(round): global ans if round == 15: # 모든 .. 2024. 7. 24. 이전 1 2 3 4 5 다음 반응형
