다이나믹 프로그래밍 (Dynamic Programming) : DP 개념 : 문제를 더 작은 단위로 쪼개어 해결하는 알고리즘. (분할 정복 알고리즘과 비슷하다. 차이점은 바로 아랫줄.) 핵심은, 그 작은 단위의 문제들이 반복해서 일어나기 때문에, 그값들을 저장해놓는 식으로 해결해나가는 알고리즘 (다이나믹이라는 이름에는 아무 뜻도 없다고 한다.) *다이나믹 프로그래밍을 사용하기 위한 조건 1. 부분 문제들이 겹치는가 (반복 되는가) ex ) 피보나치 수 : N번째 항(큰 문제) = N-1번째 항(작은 문제) + N-2 번째 항(작은 문제) 피보나치의 특성을 잘 살펴보면 Fibo(10)을 구할때는 Fibo(9)+Fibo(8)...........Fibo(1) 까지 모두 필요합니다. 이때 메모이제이션을 통해 배..

문제 링크 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 문제 분류 : 브루트 포스 https://infinitt.tistory.com/241 백준 (boj) 파이썬 , C+..

문제 링크 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 알고리즘 분류 : 이분탐색 문제 제출시, python으로는 아무리 해도 시간초과가 발생했다. 어쩔 수 없이 pypy로 ..

문제 링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 분류 : 이분탐색 정답코드 - 파이썬(python) import sys input= sys.stdin.readline K,N = map(int,input().split()) arr = [int(input())..

문제 링크 : https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1 www.acmicpc.net 분류 : 브루트 포스 https://infinitt.tistory.com/240 알고리즘 (2) - 브루트 포스(Brut..

문제 링크 : https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 가장 간단한 형태의 브루트 포스문제이다. 브루트포스란 ? https://infinitt.tistory.com/240 알고리즘 (2) - 브루트 포스(Brute Force) * 브루트 포스 (Brute Force) 무차별 대입하여 억지로 문제를 해결한다는 뜻이다. 즉, 모든 경우의 수를 다 탐색하여 문제를 해결하는 알고리즘이다. ex ) 네자리 비밀번호의 자물쇠는 0000~9999를 전부 대입..