기록하는 습관

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net #구슬 탈출2 from sys import stdin from collections import deque input = stdin.readline n,m = map(int, input().split()) graph = [list(input().strip()) for _ in range(n)] check = [[[[False] * m for _ in range(..

동적계획법(Dynamic Programming) 문제 풀 때 확인하기 1. 전체 -> 부분 문제로 나누었는가? 2. 부분 문제를 해결한 후의 결과를 메모이제이션 하는가? www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net import sys n, k = map(int, sys.stdin.readline().split()) coin = [] for _ in range(n): coin.append(int(sys.stdin.readline())) dp = [0] * (..

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net s[k] : max(s[k-1] + k 번째 값 vs 처음부터 다시 시작하기 (a[k])) import sys N = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) s = [0] * N s[0] = a[0] for k in range(N): s[k] = max(s[k - 1] + a[k], a[k]) print(max(s))

www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net i+1번째 집은 i번째 집에 칠한 컬러를 제외한 나머지 색을 칠했을 때의 최소 비용을 생각하며 점화식을 세운다. import sys N = int(sys.stdin.readline()) rgb = [] d = [[0] * 3 for _ in range(N)] for i in range(N): tmp = list(map(int, sys.stdin.readline().split())) rgb...

www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net DP 문제 풀 때 1차원 배열로 안되겠다 싶으면 바로 2차원 배열 떠올리자. n = int(input()) a = [0] * (n + 1) for i in range(1, n + 1): a[i] = int(input()) d = [[0] * 3 for _ in range(n + 1)] for k in range(1, n + 1): d[k][1] = max(d[k - 2][1], d[k - 2][2]) + a[k] d[k][..

한동안 코테 스터디 하느라 블로그에 코딩 공부 글을 올리지 못했다.. (?모순) 코테 스터디 내용은 차차 올릴 예정이다. 이제 스터디도 끝나서 다시 혼자 공부해야 하는데 열심히 문제풀이 올리면서 꾸준히 공부해야지. :) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 점화식 : d[a] = min ( d[a // 3] +1, d[a // 2] + 1 , d[a - 1] + 1 ) 시간 복잡도 : O(N) a = int(input()) d = [0] * (a + 1) for x in range(2, a + 1): d[x] = d[x - 1] + 1 if x %..

브랜디 코딩대회 '코드네임B'를 우연히 알게 되어 응시를 했다. 학부 때 알고리즘을 이론으로 배웠지만 코테 문제를 풀기 시작한건 얼마 되지 않았다. 코딩 테스트 준비를 8월 말부터 본격적으로 시작했다고 할 수 있는 시점에서 브랜디 코딩대회는 실제 내가 어느정도 위치인지, 공부를 올바른 방향으로 하고 있는지 알 수 있는 기회였다! 일단, 내 실력이 많이 부족하더라도 부딪혀보자! 생각하고 코딩 테스트를 응시했다. 처음엔 4문제 모두 다 풀어야 2차 가는 줄 알고 끝나자마자 좌절했다.. 왜냐하면 2문제 + 1문제 테스트 케이스 몇 개를 풀었기 때문이다. 역시나 내 실력에 많이 부족함을 느끼고 아직 멀었다고 생각했다. 하지만 얼마 지나 합격 메일이 왔다. 처음엔 믿기지 않았다. 나한테 메일이 잘못 온건가? 생각..

[문제] NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다. 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다. 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 ..