개발왕 양선규

그리디 문제이다. 살짝 어려웠다. 난 2가지 방식으로 풀었는데, 의문점이 있다. import sysinput = sys.stdin.readline"""1. 큰 값 순서대로 정렬2. 현재 가장 큰 값 기준으로, 원본 리스트 역순 순회하며 가장 큰 값 찾기3. 찾았다면, 가장 큰 값 포함한 좌측 값 전부 사서 큰값에 팔기4. 원본리스트에서 방금 사용된 값을 전부 없애기5. 반복현재 가장 큰 값 idx가 while문당 1씩 증가하는데, 이거 좀 비효율이다. 이후에 올 큰값들이 지워지면 쓸모없어지기 때문따라서 가장 큰 값 리스트에서도 값들을 지워주고, 항상 0으로 인덱싱 하면 될 것 같은데 귀찮다.[1, 3, 1, 10, 2, 9, 3, 10, 5][10, 9, 5, 3, 2, 1]"""for _ in rang..

그리디 문제이다. 실버 3보다는 좀 더 쉬운 것 같다. 시간복잡도도 고려할 필요 없다. 난 고려하긴 했지만. import sysinput = sys.stdin.readline"""0이 앞에 최대한 많아야 한다1은 앞부터 지우고0은 뒤부터 지우면 되지않나1. 리스트로 받아서 , 지우지 말고 -1로 교체 (지우는 연산 오버헤드 방지)2. 앞부터 -1이 아닐 경우 출력"""S = list(map(int, input().strip()))"""0, 1 개수 세기"""count = [0] * 2 # 0의 개수, 1의 개수 저장할 리스트for num in S: if num == 0: count[0] += 1 else: count[1] += 1"""앞부터 1 지우기"""delete..

전통적인 그리디 문제이다. 부분 최적해가 전체 최적해가 된다.can_eat 함수의 슬라이싱 부분은, 투포인터나 슬라이딩 윈도우 성질도 띈다. import sysinput = sys.stdin.readline"""N: 식탁의 길이K: K 이하 거리 햄버거 먹기 가능table: 사람과 햄버거의 위치사람 기준 순서대로 왼쪽이든 오른쪽이든 가장 가까운거 먹으면 될거같은데..? 그리디?K가 최대 10이니 가능할거같다. K 햄버거와 사람을 따로 보지 않고, 매핑되는 관계로 간주한다.왼쪽부터 K범위를 순차 탐색하며, 매핑될 경우 두 요소를 방문처리한다."""def can_eat(idx, K): # 기준 (사람 또는 햄버거) point = table[idx] # idx 뒤로 K거리만큼 잘라낸다 (슬라이..

그리디, 우선순위 큐 문제이다. # 골드5 -> 그리디, 자료구조, 정렬, 우선순위 큐import heapqimport sysinput = sys.stdin.readlineN = int(input())data = [list(map(int, input().split())) for _ in range(N)]data.sort()# 첫번째 시작하는 수업의 종료시간을 저장# 종료시간은 우선순위가 됨pq = []heapq.heappush(pq, data[0][1])for i in range(1, N):    # 다음 수업과 진행중인 수업이 중복되지 않을 경우 진행중 수업 빼기    if data[i][0] >= pq[0]:        heapq.heappop(pq)    heapq.heappush(pq, data..

그리디 문제이다. 문제는 간단한데 해결 방법이 도저히 떠오르질 않았다. 한번에 3개의 전구가 바뀌니까 엄청나게 많은 경우의 수가 있을 것이라 생각했고, 아무리 생각해도 답을 도출할 방법이 떠오르질 않아서 다른 코드를 참고했다. 근데 참고해도 이해가 잘 안된다. 이 코드가 어째서 정답을 도출하는지. 이론적으론 이해했지만 와닿지가 않는다.# 그리디import sysinput = sys.stdin.readlineN = int(input())origin = list(map(int, input().strip()))target = list(map(int, input().strip()))# 1번 인덱스 전구부터 하나씩 누를지 말지 결정하는 함수def solve(A, B):    press = 0    for i in..

import sysinput = sys.stdin.readline# N개의 웅덩이, L길이의 널빤지N, L = map(int, input().split())water = []# 겹치는 웅덩이는 들어오지 않는다# 웅덩이 좌표 : [1, 6] -> 1 2 3 4 5for _ in range(N):    water.append(list(map(int, input().split())))sortedWater = sorted(water, key=lambda x: (x[0])) # 시작 위치 기준으로 정렬def fix(size, L):    if size % L >= 1:        return size // L + 1    else:        return size // Ldef solve():    resul..

N은 과제의 개수D는 과제 소요일, T는 과제 마감일이며 D, T 형태로 주어진다. 최대한 과제를 미루고 미루다가 마지막에 한번에 몰아서 하는데, 이 때 첫 과제를 시작하기 전 최대 며칠을 놀 수 있는지를 구하는 문제이다. 먼저 과제 마감일 기준으로 내림차순 정렬을 해줘야 한다. 그리고 day 변수에 가장 긴 마감일을 설정해 둔다. day는 놀 수 있는 날을 저장해둘 변수이며, 반복문이 진행되며 계속해서 갱신된다. 그리고 N번 반복문을 돌리되, day와 e(현재 과제의 마감일)중 더 작은 값에서 s(현재 과제의 소요일)을 뺀다.그 뺀 값을 다시 day에 할당한다. day가 길어도 과제의 마감일이 더 이르다면 마감일에서 s를 빼고,마감일이 길어도 현재 남은 day가 더 짧다면 day에서 s를 뺀다.이걸 반..

DP(Dynamic Programming, 동적 계획법) - 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 이용해, 다시 큰 문제를 해결할 때 사용한다. - DP는 특정 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰인다. - “큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고, 재활용” - DP라는 이름은 그냥 멋있어 보여서 지은 이름이다. DP를 쓰는 이유 - 일반적인 재귀방식도 DP와 유사하지만, 일반적인 재귀를 단순히 사용 시 “동일한 작은 문제가 반복”되어, 비효율적인 계산이 될 수 있다. ex) 피보나치 수열. 한번 한 계산을 또 하고 또 하고 반복한다. --->>> DP 방식으로 작은 문제의 결과를 저장해두고 “재사용”하면 매우 효율적으로 해결할 수 있다. --->>..