Algorithm/정리 검색 결과

해당 글 9건

[백준] 알고리즘 3-7일차 다이나믹 프로그래밍

1. 2156번 : 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 포도주를 마셔도되고, 안마셔도 상관없다. 다만 연속으로 3번은 마실 수 없다. 연속한지 안한지를 검토하기 위해 2차원 배열로 해결할 수 있다. dp[i][j] i번째포도주를 j(몇번 연속으로 마셨는가?)를 기록하는게 필요하다. i번째 포도주를 안마셨을 때를 0이라 해보자...
Algorithm/정리 2021. 8. 15. 19:14

[백준] 알고리즘 3-5일차 다이나믹 프로그래밍

1. 15988번 : 1,2,3 더하기 3 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1,2,3 더하기와 같은 문제로 풀면된다. DP[N] = DP[N-1] + DP[N-2] + DP[N-3] 마지막 자리를 1로 할 것인지 2로 할 것인지 3으로 할 것인지를 결정해주면 된다. 매번 테스트케이스때마다 DP안에 있는 값을 계산해주면 너무 비효율적이다. 백만까지 모든 경우를 다구한 이후에 N값을 입력받아 그냥 출력해주면 된다. 문제에서 10억9로 나눈 나머지를 출력하라 했으니 분명 INT의 범위보다 높을 것이므로 LONG LONG으로 설정해준다. #include..
Algorithm/정리 2021. 8. 12. 12:42

[백준] 알고리즘 3-4일차 다이나믹 프로그래밍

1. 1699번 : 제곱수의 합 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net DP[N] = 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 저장 N이 되기위해 제곱수들의 합으로 표현할 때 가장 마지막에 오는 숫자가 중요하다. 가장 마지막에 오는 숫자를 j라고 한다면 1부터 N까지 j*j를 계속해서 반복해서 경우의 수를 살펴볼 것이다. 그렇다면 dp[i] = dp[i-j*j]+1 이라는 식을 도출해낼 수 있다. 마지막의 제곱수에서 N을 뺀다면 현재의 제곱수 이전의 값..
Algorithm/정리 2021. 8. 11. 12:04

[백준] 알고리즘 3-3일차 다이나믹 프로그래밍

1. 11053번 : 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net DP[N] = 가장 긴 증가하는 부분 수열의 길이를 저장한다. 하지만 여기서 아이디어가 필요로한데 단순히 모든 경우를 다 해본다면 2^1000승으로 시간초과가 나게된다. 배열 ARR[i]를 마지막으로 하는 부분수열을 저장해줘야 문제를 해결할 수 있다. LIS 라고하며 정답은 DP[1]~DP[N] 사이의 최댓값이 정답이 된다. #inclu..
Algorithm/정리 2021. 8. 9. 12:36

[백준] 알고리즘 3-2일차 다이나믹 프로그래밍

연속, 인접이라는 처리는 마지막에 무엇이 오는지 기록하는 방식으로 문제를 해결한다. 1. 15990번 : 1,2,3 더하기 5 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net DP[i][j] i를 1, 2, 3의 합으로 나타내는 방법의 수와 j가 마지막에 오는 경우의 조건을 추가한 점화식 이전에 풀었던 문제와 다른점은 조건이 하나 추가되었기 때문에 연속된 숫자의 경우를 배제해야한다. DP[i][1] i를 합으로 나타내는데 마지막에 1이 오는경우는 = DP[i-1][2] + DP[i-1][3] i-1까지의 마지막 숫자가 1만아니면 된다. 즉 마지막에 오는 숫자를 ..
Algorithm/정리 2021. 8. 7. 21:19

[백준] 알고리즘 3-1일차 다이나믹 프로그래밍

1. 11726번 : 2 x n 타일링 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2xn 타일링 문제는 큰 문제에서 작은문제로 어떻게 만들것인가가 중요한데, 오른쪽 끝에 타일을 붙여서 모양을 만든다고 생각하면 가로가 1인경우와 2인경우로 나눌 수 있다. 즉 오른쪽에 가로가 1인 타일을 붙이면 총 가로가 N일때, 남은 부분은 N-1의 크기가된다. 마찬가지로 2로 N-2가 된다. 점화식을 주석에 있는 것처럼 세워준후 문제를 해결한다. #include #include using namespace std; int dp[1001]..
Algorithm/정리 2021. 8. 7. 18:10

[백준] 알고리즘 3일차 다이나믹 프로그래밍

큰 문제를 작은 문제로 나눠서 푸는 알고리즘 1. 겹치는 작은 문제 ex) 피보나치 수 Fn = Fn-1 + Fn-2 - 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. - 문제를 작은 문제로 쪼갤 수 있다. 큰문제 = 작은 문제 2. 최적 부분 구조 - 문제의 정답을 작은 문제의 정답에서 구할 수 있다. - 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다. 즉 다이나믹 프로그래밍은 두 가지를 만족한다. - 2를 만족하기에 같은 문제는 구할 때마다 정답이 같다. - 정답을 구했으면 배열에 저장한다. - 메모하는 부분을 메모제이션이라고 한다. - 모든 문제를 풀어야 한다. - 모든 문제는 1번만 풀어야 한다. 방법 문제를 푸는데 필요한 재귀식인 점화식을 구해야한다. 문제를 작게 만드는 방법을 찾..
Algorithm/정리 2021. 8. 7. 14:39

[백준] 알고리즘 2일차 문제 및 복습

1. 16936번 : 나3곱2 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 3으로 나누는 것 - 3^k x A / 3 = 3^k-1 x A 즉 3으로 몇 번 나눠지냐 이걸 확인해준 후, 오름차순으로 정렬만 해주면 된다. 문제에서 항상 정답이 존재하는 경우에만 입력으로 주어지고, 애당초 수열B는 A를 섞어서 입력받는 거기 때문에, 안되는 경우는 없다. 9 - 3 - 6 - 12 - 4 - 8 #include using namespace std; bool cmp(pair &a, pair &b)..
Algorithm/정리 2021. 5. 7. 21:46

[백준] 알고리즘 강의 1일차 문제 및 복습

브루트 포스 1. 16968번 : 차량 번호 문제 16968번: 차량 번호판 1 00부터 99까지 총 100가지 중에서 00, 11, 22, 33, 44, 55, 66, 77, 88, 99가 불가능하다. www.acmicpc.net #include using namespace std; int go(string &s, int index, char last) { if (s.length() == index) return 1; char start = (s[index] == 'c' ? 'a' : '0'); char end = (s[index] == 'c' ? 'z' : '9'); int ans = 0; for (char i = start; i > s; cout 0&&s[i] == s[i-1]) { cnt=cnt-..
Algorithm/정리 2021. 5. 2. 20:31