차곡차곡

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV3 문제 설명 삼각형 모양으로 꼭대기에서 바닥까지 이어지는 경로 중 숫자의 합이 최대가 되는 경우의 합을 Return해준다. 아래칸으로 이동할때 대각선 방향으로 한칸 오른쪽 왼쪽 으로만 이동 가능하다. 접근법 삼각형 꼭대기 한칸 아래에서부터 위에서 내려올 수 있는 경우에 대해 최대 값을 더해준다. 만약 양끝에 있는 경우에는 가능한 값이 하나밖에 없으므로 별..

동적 계획법(Dynamic Progamming) 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하고 다시 큰 문제를 해결할 때 사용하는 알고리즘 설계 기법이다. 각 하위 문제를 먼저 해결하고 저장하기 때문에 같은 하위 문제가 나왔을 경우 저장한 값을 이용하여 간단하게 해결할 수 있다. 이를 통해 계산 횟수를 줄이기 때문에 하위 문제의 수가 기하 급수적으로 증가할 때 유용하다. 사용 용도 최단 경로 문제 행렬의 제곱 문제 최적화 문제 ex) 문제의 숫자 범위가 크고, 경우의 수가 많은 경우 사용 조건 - 아래 두 조건이 만족하는 경우 다이나믹 프로그래밍을 이용하여 문제를 해결하는데 유용하다. 부분 중복(반복) 문제 - 이미 진행했던 연산임에도 불구하고 재귀되며 반복적으로 연산되는 문제 최적..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 정답 code #내려가기 import sys input = sys.stdin.readline n = int(input()) score = list(map(int,input().split())) maxdp = score mindp = score for _ in range(n-1): a,b,c = map(int,input().split()) maxdp = [a+max(maxdp[0], maxdp[1]), b+max..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 정답 code #정수 삼각형 import sys input = sys.stdin.readline n = int(input()) t = [] for _ in range(n): num = list(map(int,input().split())) t.append(num) for i in range(1,n): # 층수 (0층은 한개의 값) for j in range(i+1): #가로줄 선택 (층수+1)개만큼 존재 # 가장 왼쪽 값일때 위의 값 if j == 0: t[i][j] ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 정답 code #RGB거리 import sys input = sys.stdin.readline n = int(input()) cost = [] for _ in range(n): r,g,b = map(int,input().split()) cost.append([r,g,b]) for i in range(1,n): cost[i][0] = min(cost[i-1][1],cost[i-..

정답 code #Four Squares import sys def check(n): # n의 제곱근이 정수라면 1출력 if (n**0.5).is_integer() : return 1 # n보다 작은 어떤 수를 뺀 수의 제곱근이 정수라면 2출력 ex(A^2+B^2) for i in range(1, int(n**0.5)+1): if (int(n-i*i)**0.5).is_integer(): return 2 #n보다 작은 어떤 제곱근의 수를 두개뺀 수의 제곱근이 정수라면 3출력 ex(A^2+B^2+C^3) for i in range(1,int(n**0.5)+1): for j in range(1, int((n-i*i)**0.5)+1) : if ((n-(i*i)-(j*j))**0.5).is_integer(): re..