빅맥좋아요

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 백준 11659번 구간 합 구하기 4를 풀었다. 입력으로 받은 배열을 그대로 사용해서 구간 i부터 j까지의 합을 구하려고 하면 시간 초과가 나온다. 최악의 경우 10만개의 수를 10만번 더해야 해서 시간복잡도가 O(N^2)으로 예상된다. 따라서 누적 합을 사용해서 풀었다. 입력 받은 배열 index 0 1 2 3 4 value 5 4 3 2 1 누적 합으로 바꾼 배열 ind..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 백준 9251번 LCS를 풀었다. LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 처음엔 모든 경우의 수를 찾으려 했는데 안될 것 같아서 고민하다가 다른 사람들..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 백준 2565번 전깃줄 문제를 풀었다. 처음에 그리디 방식으로 가장 많이 겹치게 되는 전깃줄을 지우려 했는데 실패하고 다른 사람의 코드를 찾아봤다. 이 문제는 가장 긴 증가하는 부분 수열로 풀 수 있는 문제였다. 입력으로 받은 전깃줄을 A에 대해 오름차순으로 정렬한 뒤에 B를 보면 된다. 문제의 예제를 기준으로 B는 { 8, 2, 9, 1, 4, 6, 7, 10 } 이 된다. 여기서 없애지 않아도 되는 ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 백준 12865번 평범한 배낭 문제를 풀었습니다. 0-1 냅색 문제입니다. arr[i][j]는 배낭 용량이 j일 때, 첫 번째 물건부터 i번째 물건까지 넣어본 최댓값을 가지고 있습니다. i번째 물건의 무게가 j보다 크다면 가방에 물건을 넣을 수 없으므로 arr[i][j]는 arr[i-1][j]이 됩니다. i번째 물건의 무게가 j보다..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 백준 1904번 01타일을 풀었습니다. 간단한 DP문제입니다. 피보나치 수열같이 규칙을 찾고 점화식을 만들면 됩니다. 아래는 전체 코드입니다. #include #include #include using namespace std; #define MOD 15746 int N; int arr[1000000]; int DP(int n) { if (arr[n] != 0) return arr[n]; if (n =..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 백준 2579번 계단 오르기를 풀어봤습니다. DP문제이고 점화식과 base condition을 잘 설정하면 됩니다. 아래는 전체 코드입니다. #include #include #include using namespace std; int N; int stair[300]; int score[300]; int dp(int n) { if (n < 0) return 0; if (score[n] != 0) return s..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 백준 1912번 연속합 문제를 풀어봤습니다. 아래는 전체 코드입니다. #include #include #include using namespace std; int n; int sequence[100000]; int sum[100000]; void dp(int n) { sum[0] = sequence[0]; int result = sum[0]; for (int i = 1; i < n; i++) { sum[i]..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 백준 11053번 가장 긴 증가하는 부분 수열을 풀어봤습니다. 아래는 전체 코드입니다. #include #include #include using namespace std; int n; int sequence[1000]; int len[1000]; void dp(int N) { for (int i = 0; i < N; ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 백준 2156번 포도주 시식을 풀어봤습니다. base condition과 점화식만 잘 설정해주면 됩니다. 아래는 전체 코드입니다. #include #include using namespace std; int n; int wine[10000]; int cost[10000]; int dp(int n) { if (n < 0) return 0; if (cost[n] != -1) return cost[n];..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 10844번 쉬운 계단 수를 풀어봤습니다. 동적계획법 문제이고 bottom-up, top-down 두 가지 방식으로 풀 수 있습니다. 아래는 전체 코드입니다. #include #include #include using namespace std; #define MOD 1000000000 int N; int arr[100][10]; int dp(int n, int k) { if (k 9) return 0; if (arr[n][k] != 0) return arr[n][k]; if (n == 0)..