태야

배열이나 리스트에서 각 원소에 대해 오른쪽에 있는 원소들 중 자신보다 크거나 같은(또는 보통은 '큰' 경우가 많지만, 변형으로 '크거나 같은' 조건을 쓰기도 한다) 첫 번째 원소를 찾는 문제다.

예시 문제 설명

예를 들어, 배열 A가 주어졌을 때A = [3, 5, 2, 7, 5]각 원소에 대해 오른쪽으로 이동하며, 처음 만나는 자신보다 크거나 같은 원소를 찾습니다.

- 3의 오른쪽에는 5, 2, 7, 5가 있는데, 처음으로 3보다 크거나 같은 수는 5입니다.
- 5의 오른쪽에는 2, 7, 5가 있는데, 2는 작으므로 건너뛰고, 다음 7은 5보다 크므로 7이 됩니다.
- 2의 오른쪽에는 7, 5가 있으므로 7이 첫 번째 큰(또는 같은) 수입니다.
- 7의 오른쪽에는 5만 있으나 5는 7보다 작으므로, 7은 오른쪽에 조건을 만족하는 원소가 없는 것으로 처리합니다.
- 마지막 원소인 5는 오른쪽에 아무 원소도 없으므로 조건을 만족하는 원소가 없습니다.

보통 조건을 만족하는 원소가 없을 경우 -1 또는 0 등 특정 값을 반환합니다.

단순하게 이중 반복문을 사용하면, 각 원소마다 오른쪽의 모든 원소를 확인해야 하므로 시간복잡도가 O(n^2)가 된다. 하지만 스택(stack)을 이용하면, 한 번의 순회로 각 원소를 효율적으로 처리할 수 있다.

스택을 사용하는 이유

• 스택의 특징
  
  • 스택은 후입선출(LIFO) 구조다. 이 특성을 이용하면, 배열을 한 번 순회하면서 "아직 답을 찾지 못한 원소들의 인덱스"를 스택에 저장해 두고, 새로운 원소가 들어올 때마다 이전 원소들과 비교하여 조건(큰 혹은 큰/같은)을 만족하는지 빠르게 확인할 수 있다.
• 시간복잡도
  • 각 원소는 스택에 한 번 push되고, 조건이 맞으면 pop되므로 각 원소가 스택에 들어가고 나오는 과정이 한 번씩 이루어집니다. 따라서 전체 시간 복잡도는 O(n)이 됩니다.

알고리즘 동작 과정

1. 초기화:
   빈 스택을 준비하고, 결과를 저장할 배열을 초기화한다. 결과 배열은 각 원소의 "다음 큰(또는 같은) 수"의 인덱스나 값을 저장할 수 있다.
2. 배열 순회:
   배열의 인덱스를 0부터 n-1까지 순회한다.
   • 현재 원소와 비교:
     현재 원소(A[i])가 들어왔을 때, 스택의 최상단에 있는 인덱스(예: j)를 확인한다.
     • 만약 A[i]가 A[j]보다 크거나(또는 크거나 같은) 하면, A[i]는 A[j]의 조건(다음 큰 또는 같은 수)을 만족하는 원소가 된다.
       따라서 결과 배열의 j번째 위치에 A[i] 또는 인덱스 i를 저장하고, 스택에서 j를 pop한다.
     • 이 과정을 스택이 비거나, 스택의 최상단 원소가 현재 원소보다 크거나 같은 조건을 만족할 때까지 반복한다.
   • 현재 인덱스 push:
     그 후, 현재 인덱스 i를 스택에 push한다.
3. 후처리:
   배열 순회가 끝난 후에도 스택에 남아있는 인덱스들은 오른쪽에 조건을 만족하는 원소가 없는 경우다. 이 경우, 결과 배열에 -1 또는 0을 기록한다.

Python 코드 예시

def next_greater_or_equal(arr):
    n = len(arr)
    result = [-1] * n  # 조건을 만족하는 원소가 없으면 -1로 처리
    stack = []  # 인덱스를 저장하는 스택

    for i in range(n):
        # 현재 원소 arr[i]가 스택의 최상단 원소보다 크거나 같으면 조건을 만족
        while stack and arr[stack[-1]] <= arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    
    return result

# 예시 실행
A = [3, 5, 2, 7, 5]
print(next_greater_or_equal(A))  # 출력 예: [5, 7, 7, -1, -1]

위 글을 요약하자면 다음과 같다.

• 문제: 각 원소에 대해 오른쪽에서 처음으로 자신보다 크거나 같은 원소를 찾는 문제.
• 단순 방법: 이중 반복문을 사용하면 O(n^2) 시간복잡도.
• 스택 사용: 스택을 이용하면 각 원소가 한 번씩만 처리되므로 O(n) 시간복잡도로 해결 가능.
• 핵심: 스택에 아직 답을 찾지 못한 원소의 인덱스를 저장하고, 새 원소가 들어올 때마다 조건에 맞는 이전 원소들을 처리.

<내 코드>

N = int(input())
H = list(map(int, input().split()))
result = [0] * N

for i in range(N):
    cnt_zero = 0

    for j in range(N):
        if cnt_zero == H[i] and result[j] == 0:
            result[j] = i + 1  # 수 1 ~ N
            break
        elif(result[j] == 0):
            cnt_zero += 1

print(*result)

입력 값으로 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. 그리고 줄을 선 순서대로 키를 출력하면 된다. 

# result
# 입력: [2, 1, 1, 0]
[0, 0, 1, 0]
[0, 2, 1, 0]
[0, 2, 1, 3]
[4, 2, 1, 3]

차례대로 각자 왼쪽에 큰 사람이 몇 명인지를 0의 개수로 판단해서 자리에 넣어준다. 예를 들어 왼쪽에 2명이 있다 하면 결과값 배열에 [0, 0, 현재,...] 즉, 자신보다 큰 2명의 자리를 비워두고 자리에 들어가면 된다. 그렇게 되면 다음 사람은 앞전보다 큰 사람이기 때문에 앞사람 위치는 무시하고 자신보다 큰 사람 수와 0의 수만 같으면 그 자리에 들어가면 된다.

<내 코드>

N = int(input())

weights = [int(input()) for _ in range(N)]
weights.sort(reverse=True)  # 내림차순


for i in range(N):
    weights[i] = weights[i] * (i+1)

print(max(weights))

문제 접근 방법

- 로프를 병렬로 연결하면 각 로프에는 w/k만큼의 동일한 중량이 걸린다.

- 즉, 가장 작은 무게를 들 수 있는 로프가 들 수 있는 질량 * 병렬연결 로프 개수 = 최종 무게

- 가장 무거운 무게를 들 수 있는 로프부터 내림차순으로 정렬한다.

처음에는 너무 어렵게 접근해서 복잡하게 생각했다. 그래서 디큐를 활용해 하나씩 빼고 넣고 하려고 했다가 실패했다. 이렇게 단순하게 풀릴지는... 후..

<내 코드>

T = int(input())

A, B, C = 0, 0, 0

while T > 0:
    if T >= 300:
        A = (T // 300)
        T = (T % 300)
    if (T >= 60) and (T < 300):
        B = (T // 60)
        T = (T % 60)
    if (T < 60):
        C = (T // 10)
        if (T % 10) == 0:
            print("{} {} {}".format(A, B, C))
            break
        else:
            print(-1)
            break

특별히 어려운 조건이 없는 문제였다. 최소한의 버튼 클릭 수를 구하기 위해 입력값을 큰 값으로 최대한 나누면 된다. 입력 값이 단위별로 나눌 수 있는 값인지 판단 후 계산을 하고 몫을 출력해주면 된다. 마지막에 10초로 나눴을 때 나머지가 0이 아니면 -1을 출력한다.

<내 코드>

N = int(input())

times = [list(map(int, input().split())) for _ in range(N)]
times.sort(key=lambda x: (x[1], x[0])) # 끝 시간으로 정렬 후, 시작 시간으로 정렬

cnt = 1
end_time = times[0][1]
for i in range(1, N):
    if times[i][0] >= end_time: # 앞 요소의 끝 시간보다 현재 요소의 시작시간이 크거나 같을 때
        cnt += 1
        end_time = times[i][1]

print(cnt)

문제에서 제약조건이 다음과 같이 주어졌다.

- 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

- 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

최대한 많은 회의를 잡기 위해서는 끝나는 시간이 짧아야 한다. 회의가 빨리 끝나야 다음 회의를 시작할 수 있다. 

그래서 우선 끝나는 시간으로 정렬한다. 여기서 중요한 것이 시작 시간과 끝나는 시간이 같은 케이스다.

예를 들어 (2,2) 와 (1,2) 있을 때 끝나는 시간으로 정렬을 한다면 (2,2)가 먼저 정렬되고 (1,2)가 무시된다. 그래서 시작과 끝 시간이 같은 경우는 시작 시간 기준으로 다시 정렬을 해줘야 한다.

<내 코드>

n = int(input())
tri = [list(map(int, input().split())) for _ in range(n)]
k = 2
for i in range(1, n):
    for j in range(len(tri[i])):
        if j == 0:  # 가장 왼쪽값일 경우 현재 값이랑 바로 위랑 더함
            tri[i][j] = tri[i-1][j] + tri[i][j]
        elif j == len(tri[i])-1:    # 가장 오른쪽일 경우 현재 값이랑 바로 위랑 더함
            tri[i][j] = tri[i-1][-1] + tri[i][j]
        else:  # 양 끝값이 아닌, 중간일 경우, 대각선 왼쪽과 오른쪽 중 큰 값과 더함
            tri[i][j] = max(tri[i-1][j-1], tri[i-1][j]) + tri[i][j]
    k += 1
print(max(tri[n-1]))

규칙을 찾아서 재귀 형태의 점화식을 찾아내는 것이 중요했다. 삼각형의 가장 왼쪽과 오른쪽 값은 위의 값과 바로 더해주면 되고, 중간의 값들은 대각선 왼쪽과 오른쪽의 값 중 최댓값과 더해줬다. 

<내 코드>

n = int(input())
costs = [0 for _ in range(n+1)]
for i in range(1, n+1):
    costs[i] = list(map(int, input().split()))

for i in range(2, n+1):
    costs[i][0] = costs[i][0] + min(costs[i-1][1], costs[i-1][2])
    costs[i][1] = costs[i][1] + min(costs[i-1][0], costs[i-1][2])
    costs[i][2] = costs[i][2] + min(costs[i-1][0], costs[i-1][1])
   
print(min(costs[n][0], costs[n][1], costs[n][2]))

처음에 생각했을 때는 맨 처음 요소에서 최솟값을 구하면 최소가 되는 줄 알았는데, 그게 아니고 어떤 값을 선택했을 때 최소가 될지는 다 따져줘야 하는 문제였다. 다른 사람의 풀이를 참고하기 전까지는 쓸데없이 어렵게 풀고 헤맸다...

1. 첫 요소는 고정이므로 인덱스를 2번째부터 돌리면 된다. 

2. 현재 인덱스 요소의 값과 앞 요소에서 같은 색을 제외한 2가지 중에 최소를 더해준다.

3. 같은 방식으로 마지막까지 3가지 색에 대해 계산을 한다.

4. 마지막 요소의 3가지 값 중 최솟값을 선택하면 최소 비용값을 구할 수 있다.

동적 계획법이란?

어떤 문제를 풀기 위해 그 문제를 더 작은 문제들로 나누고, 작은 문제들에서 구한 해를 어딘가에 저장한 다음 활용해 문제를 해결하는 알고리즘 설계 기법이다. DP는 이름처럼 다이내믹한 프로그래밍이라는 거리가 멀다. 단순히 붙여진 이름일 뿐이라고 한다.

분할 정복 방식과 차이점

DP의 문제 접근 방식은 기본적으로 '분할 정복 알고리즘(Divide and Conquer)'과 비슷하다. 두 경우 모두 문제를 부분으로 나누어 각 부분 문제의 답을 계산하고, 이 값을 이용해 원래 문제를 해결하는 과정이다. DP와 분할 정복의 차이는 부분 문제로 나누는 방식에 차이가 있다. DP는 작은 문제들이 반복적으로 사용되며 (즉, 답이 바뀌지 않음) 반대로 동적 계획법은 작은 문제가 중복이 발생하지 않고 단순히 나누어 푸는 방법이다.

DP 문제의 해결 순서

1. 큰 문제를 작은 문제로 나눈다.

2. 재귀적인 구조를 활용할 수 있는 점화식을 만든다.

3. 작은 문제의 도출 값을 메모하고, 큰 문제를 풀어나갈 때 작은 문제가 반복되면 메모한 값을 이용한다. (Memoization방식)

DP의 조건

1. 작은 문제가 반복, 중복이 일어나는 경우

2. 같은 문제의 값은 매번 같다.

여기서 반복적으로 중복이 일어난 부분이 있다. 원으로 표시한 부분만 아니라 F(4)와 F(3)을 구하기 위해 모두 F(2)를 계산해야한다. 이런 식으로 매번 다 계산을 하면 시간적으로 비효율적이다. 그래서 DP방식을 이용해 메모이제이션을 통해 값을 활용해서 문제를 해결하면 훨씬 빠른 계산이 가능해진다.