문제풀이

동기의 문제 풀이 발표 중 김현수 코치님의 피드백:
면접에서 왜 그렇게 접근했는지 설명할 수 있어야 한다.
예: dp를 적용하게 된 이유, dp 적용 조건, 코드 구조

오늘 배운 것들

1. 동적 프로그래밍(계속)

1-1. 계단 오르기(백준 2579)

• 점화식
  계단 $I_n$가 주어졌을 때 최대 점수가 $MS_{I_n}$라고 할 때
  $MS_{I_n}=max(MS_{I_{n-2},2}+I[n], MS_{I_{n-1}, 1}+I[n])$

import sys

input = sys.stdin.readline

def main() -> None:
    N = int(input())
    S = [int(input()) for _ in range(N)]
    A = [[0]*N for _ in range(2)] # with small double jumps, with big single jump

    A[0][0], A[1][0] = 0+S[0], 0+S[0]
    if N > 1:
        A[0][1], A[1][1] = A[1][0]+S[1], 0+S[1]

    for i in range(2, N):
        A[0][i] = A[1][i-1]+S[i]
        A[1][i] = max(A[0][i-2], A[1][i-2])+S[i]

    print(max(A[0][N-1], A[1][N-1]))

if __name__ == "__main__":
    main()

2. 그리디 알고리즘

미래 선택을 고려하지 않고 현 시점 최선(순간 최적해)을 선택해가며 전체 문제의 해를 구하는 알고리즘
그리디 알고리즘을 통해 전역 최적해를 달성하기 위해서는 문제가 아래 두 조건을 만족해야 한다.

2-1. 사용 조건

1. 탐욕 선택 속성(Greedy Choice Property):
   각 단계에서의 그리디 선택이 최적해의 일부여야 한다.
   전체 문제의 최적해를 찾기 위해 각 단계에서 최적의 선택을 해도 최적해에 도달하여야 한다.
2. 최적 부분 구조(Optimal Substructure):
   전역 최적해가 하위 문제들의 최적해로 표현될 수 있다.
   동적 프로그래밍의 경우와 공유하는 조건이다. 따라서 대부분의 그리디 해결 문제는 동적 프로래밍으로도 해결할 수 있다.

그리디 알고리즘이 언제나 최적해를 보장하는 것은 아니다.
따라서 그리디 알고리즘이 문제에 적용 가능한지 확인하는 것이 중요하다.(근사해를 찾는 데 사용하기도 한다.)

예: 다익스트라 알고리즘에서 현재 최소 비용으로 방문할 수 있는 노드는 다른 노드를 추가로 경유할 경우 무조건 비용이 증가한다(양의 가중치 조건). 따라서 최소 비용인 노드를 방문하는 것(그리디 선택)이 무조건 최적해의 일부이다.

2-2. 접근 방법

그리디 알고리즘을 만드는 구체적인 방법은 다음과 같다:
1. 문제의 최적 부분 구조를 결정한다.
2. 재귀 해를 만든다.
3. 그리디 선택을 하고 나면 단 하나의 부분 문제만 남음을 보인다.
4. 그리디 선택이 항상 최적해에 포함됨을 보인다.
5. 그리디 방법론을 구현하는 재귀 알고리즘을 만든다.
6. 재귀 알고리즘을 순환 반복 알고리즘으로 바꾼다.

좀 더 일반적인 방법:
1. 하나의 부분 문제만이 남는 선택을 찾는다.
2. 최적해 중에서 그리디 선택이 반드시 존재함을 증명한다.
3. 부분 문제에 그리디 선택을 결합하면 항상 최적해를 얻게되는 최적 부분 구조를 구한다.

숏코딩

잃어버린 괄호(백준 1541)

a,*A=[sum(map(int,s.split('+')))for s in input().split('-')];print(a-sum(A))

76바이트
이 밑으로 줄이려면 다른 풀이를 생각해내야 하지만 이거 저거 시도해봐도 나는 생각할 수가 없다.
파이썬 1등은 74바이트.
76바이트 동점자들은 변수명을 빼고 한치의 오차도 없이 같은 코드를 제출했다는 것이 흥미롭다(수렴진화인가).