본문 바로가기
  • 시 쓰는 개발자

분류 전체보기336

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.
필독!!) DP (Dynamic Programming) DP처음 보면 dynamic programming이 무슨 뜻인지 감이 잘 안오는데, 쉽게 말하면 중복되는 과정은 재사용하겠다는 것이다. 큰 문제를 해결하는데 작은 문제들이 사용된다면, 이를 어디다가 저장해놓고 큰 문제를 해결하는데에 이용한다.이 맥락에서 알 수 있듯이, 작은 문제의 결과를 저장해야 하므로 메모리를 추가적으로 사용한다.그러나 생각해보자. 100이라는 문제를 푸는데 단계별로 1, 2, 3, ... , 98, 99가 필요하다고 한다면, 99까지의 결과를 어디다가 저장해두고, 99 → 100 이렇게 한단계만 푸는 게 효과적이지 않겠는가?? 그래서 메모리는 추가적으로 들지만 앞단계를 다 스킵할 수가 있으므로 시간을 많이 단축할 수 있다.Memoization위에서 설명했던, 메모리를 추가로 사용해서.. 2024. 7. 29.
이진탐색 요약 이진탐색이진탐색의 제일 큰 특징은 "정렬된 데이터"에서 탐색하는 것이다(오름차순). 이유는 이진탐색이 search하는 방식에서 드러난다.ex) 1 2 3 4 5에서 4를 찾는다고 할 때, 제일 먼저 리스트의 가운데를 탐색한다. 목표인 4를 가운데값 3과 비교해서 크면 오른쪽, 작으면 왼쪽으로 탐색을 이어간다. 이처럼 값의 크기에 따라 "왼쪽", "오른쪽"과 같이 방향을 가져야하므로 반드시 정렬이 된 상태로 탐색이 진행되어야한다.가운데값을 보고 계속 탐색 범위를 반씩 줄여가므로 시간 복잡도는 O(log N)이 된다.구현재귀, 반복문 2가지 방법으로 구현이 가능하다. 공통점은 무조건 정렬하고 시작해야한다는 것 !!반복문으로 구현data = [4,2,3,7,1,9,6]data.sort()def binary_s.. 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.
반응형

티스토리툴바