알고리즘(Python)

다리를 지나는 트럭(프로그래머스)

문제링크

#다리를 지나는 트럭
def solution(length, weight, before_lst):
    ing_lst = [] # 다리를 지나고 있는 트럭
    ing_time = [] # 다리를 지나고 있는 트럭의 다리에 있었던 시간
    end_lst = [] # 다리를 지난 트럭
    n = len(before_lst)
    time = 0 # 시간
    while True:
        time += 1
        if ing_time:
            ing_time = [i+1 for i in ing_time] # 다리를 지나고 있는 트럭의 체류시간 +1
        if len(ing_lst) < length: # length 만큼 트럭이 머물 수 있다.
            if before_lst:
                i = before_lst[0]
                if sum(ing_lst)+ i <= weight: # 다리위트럭의 무게가 기준치를 안넘는다면 append
                    ing_lst.append(before_lst.pop(0))
                    ing_time.append(1)

        if ing_time[0] == length: # 다리위에 있는 트럭중 체류시간이 length 만큼 됐다면 pop
            ing_time.pop(0)
            end_lst.append(ing_lst.pop(0))
        if len(end_lst) == n:
            break
    return time+1

큐를 사용하면 더 빨라졌을 듯
if 문이 너무 많다 줄일 수 있을 듯
end_lst 안만들어도 된다.

#다리를 지나는 트럭
def solution(length, weight, before_lst):
    ing_lst = []
    ing_time = []
    n = len(before_lst)
    time = 0
    cnt = 0
    while True:
        time += 1
        if ing_time:
            ing_time = [i+1 for i in ing_time]
        if len(ing_lst) < length:
            if before_lst:
                i = before_lst[0]
                if sum(ing_lst)+ i <= weight:
                    ing_lst.append(before_lst.pop(0))
                    ing_time.append(1)

        if ing_time[0] == length:
            ing_time.pop(0)
            ing_lst.pop(0)
            cnt += 1
        if cnt == n:
            break
    return time+1

요렇게!!

연속합

문제링크

1. 첫번째 접근

연속되는 양수 묶음을 파악하고 각 묶음의 합의 최댓값을 출력
-> 음수가 포한되는 연속합이더라도 최대합이 될 수 있기 때문에 접근이 틀렸다.

n = int(input())
queue = list(map(int, input().split()))
s = sum(queue)
cnt = 0
for i in queue:
    if i < 0:
        cnt += 1
if cnt == n: # 모든수가 음수일 때
    print(max(queue))

else:
    packet = []
    tmp = []
    v = queue.pop(0)
    vp = v>0
    tmp.append(v)
    while queue:
        vv = queue.pop(0)
        vvp = vv>0

        if vp == vvp:
            tmp.append(vv)
            v = vv
        else:
            packet.append(tmp)
            tmp = []
            # tmp.append(vv)
            v = vv
    packet.append(tmp)
    packet.append(queue)
    p = [sum(i) for i in packet]
    p.append(s)
    print(max(p))

2. 완전 탐색 O(N^2)

n = int(input())
queue = list(map(int, input().split()))
result = []
for i in range(n):
    tmp = []
    tmp.append(queue[i])
    result.append(queue[i])
    for ii in range(i+1, n):
        tmp.append(queue[ii])
        result.append(sum(tmp))
print(max(result)) 

답은 맞는데 시간초과 뜬다,,,,,,,,

3. 동적 계획법

어떻게든 더할수록 커져야 한다. 계속 더해온 값보다 현재 인덱스의 값이 더 크다면 그 값으로 바꿔야 한다.
그래서 더해온 값을 저장하고, 저장한 값 중에서 가장 큰 값을 찾는다.

n = int(input())
nums = list(map(int, input().split())) # 입력 숫자
history = nums.copy() # 입력 숫자들을 더하는 기록 저장
max_val = -1000

for i in range(n):
    if i==0:
        continue
    if nums[i] < history[i-1] + nums[i]:
        history[i] = history[i-1] + nums[i]
    if history[i] > max_val:
        max_val = history[i]
print(max_val)

이렇게 썼다가 틀렸는데 이유는
맨 첫번째 원소에서는 continue를 해버리면서 최댓값을 찾는 코드가 안먹었기 때문이다.
초기값을 첫번째 원소로 지정하면 된다.

n = int(input())
nums = list(map(int, input().split())) # 입력 숫자
history = nums.copy() # 입력 숫자들을 더하는 기록 저장
max_val = nums[0]

for i in range(n):
    if i==0:
        continue
    if nums[i] < history[i-1] + nums[i]:
        history[i] = history[i-1] + nums[i]
    if history[i] > max_val:
        max_val = history[i]
print(max_val)

1. max함수가 복잡도가 높아서 위와같이 max함수를 안쓰는 방향으로 쓰는 것이 좋다.
2. 초기값 잘 생각하고 설정하자