차곡차곡

그리디 알고리즘 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 탐욕법이라고도 불리는데 이름에서 알 수 있듯이 단순 무식하게, 탐욕적(현재 상황에서 지금 당장 좋은 것만 고르는 것)으로 문제를 해결하는 알고리즘이다. 매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 대체로 그리디 알고리즘 문제는 정렬 알고리즘과 짝을 이뤄 출제된다. 그리디 알고리즘 적용 조건 탐욕적 선택 속성 : 앞의 선택이 이후의 선택이 영향을 주지 않는다. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. 그리디(탐욕) 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느정도 최적에 근사한 값을 빠르게 도출할 수 있..

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-..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 정답 code # 2*n 타일링 import sys input = sys.stdin.readline n = int(input()) sol = [0]*n for i in range(1,n+1): if i == 1: sol[i-1] = 1 elif i == 2: sol[i-1] = 2 else: sol[i-1] = sol[i-2] + sol[i-3] print(sol[-1]%10007) solution 2*n 직사각형에 ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 정답 code #1, 2, 3 더하기 def sol(n): if n == 1: return 1 elif n == 2: return 2 elif n == 3: return 4 else: return sol(n-1) + sol(n-2) + sol(n-3) t = int(input()) for _ in range(t): n = int(input()) print(sol(n)) solution n = 1 이면 방법의수 는 1 n = 2 이면 방법의 수는 2 n = 3 이면 방법의 수는 4 n = 4이면 ..