선릉역 1번 출구

백준 15500 - 이상한 하노이 탑 https://www.acmicpc.net/problem/15500 15500번: 이상한 하노이 탑 첫 번째 줄에 원판을 옮긴 횟수 K (0 ≤ K ≤ 12345) 를 출력한다. 다음 K 개 줄에 걸쳐 A B (1 ≤ A, B ≤ 3) 를 출력하는데 A 번째 장대 맨위에 있는 원판 하나를 B 번째 장대 맨위로 옮긴다는 뜻이다. www.acmicpc.net n = int(input()) stack_1 = list(map(int, input().split())) stack_2 = [] ans = [] flag = True max_hanoi = n while max_hanoi > 0: if flag: while stack_1: if stack_1[-1] == max_han..

problem. n개의 정수로 이루어진 임의의 수열이 주어짐 -> 연속된 수들의 합의 최댓값을 찾는 것 key point 10 -4 3 -7 2 10 6 9 2 4 import sys n = int(input()) dp = list(map(int, sys.stdin.readline().split())) for i in range(1, n): if dp[i] dp[i]라면 dp[i-1]는 양수이기 때문에 연속하는 것이 맞고, 그 반대는 음수이기 때문에 dp[i]를 최댓값으로 취하는 것이 맞다.

problem. 가장 긴 부분의 갯수 출력(11053과 동일), 부분 수열 출력 key point 이중 for문을 돌릴 때 for i in range(n): k = 0 for j in range(i): if ls[j]

최장 증가 부분 수열이란? 원소가 n개인 배열의 일부 원소를 골라내 만든 부분 수열 중에서(상대적인 순서는 유지) 길이가 최대인 수열을 의미한다. ex) {4, 2, 3, 1, 6, 5}이라면? {2, 3, 6}이 된다. 가장 기본적인 해결 방안은 dynamic programming을 사용하는 것이다. dp[i] : i까지 인덱스 중 가장 긴 수열의 길이 dp = [1] * n for i in range(n): for j in range(i): if ls[j] 2, 1 번째 -> 3, 2 번째 -> 3, 3 번째 -> 4, 4번째 -> 4가 된다.

problem. 주어진 수열 중에서 가장 긴 부분의 length를 찾는 문제 key point. 이 문제를 최장 증가 부분 수열이라고 부른다. 그래서 이 알고리즘을 사용해서 문제를 풀면 바로 해결이 된다. 자세한 것은 algorithm study 카테고리에 작성할 것이다. import sys n = int(input()) ls = list(map(int, sys.stdin.readline().split())) dp = [1] * n // 기본적인 길이는 1이기 때문에 default value를 1로 해준다. for i in range(n): for j in range(i): if ls[j]

problem. 0으로 시작x, 1은 연속으로 들어갈 수 없음 key point 1 2 1 10 0으로 시작할 수 없으니 길이가 1인 경우는 1뿐이다. 그리고 길이가 2인 경우는 1뒤에 1이 연속으로 올 수 없기 때문에 10뿐이다. 핵심 포인트는 1뒤에는 1이 올 수 없으니 길이가 n이면서 마지막 숫자가 1인 경우는 n-1에서 마지막 숫자가 0으로 끝나는 수와 같다. 0의 경우는 1, 0 뒤에 모두 올 수 있기 때문에 이전 n-1의 sum()값이다. 그럼 이제 배열은 선언해주어야 하는데 type이 0, 1 2개이기 때문에 dp[n + 1][2]으로 선언을 해준다. n = int(input()) dp = [[0 for _ in range(2)] for _ in range(n + 1)] dp[1][1] = ..