Storage Gonie

용도 : 두개의 타입을 하나로 묶어줌 1. 헤더파일 #include 2. 변수 선언 - 값을 할당하는 방법은 2가지 방법중 선택가능 pair p1; // 사용 예시 : 문자 빈도수 계산후 저장 용도 p1.first = 10; p1.second = 'c'; pair p2; // 사용 예시 : 문자 빈도수 계산후 저장 용도 p1.first = 10; p1.second = "sample"; pair p3; // 사용예시 : x, y 좌표 같은 것 p3 = make_pair(40, 30); 3. vector타입을 이용한 pair 배열 vector vec; vec.push_back(make_pair(20, 30)); vec.push_back(make_pair(10, 15)); vector vec(2); vec[0..

문제 풀이 자세한 풀이 : # C++(방법1 : Quick Sort 직접 구현 - lomuto partition 알고리즘 사용) #include using namespace std; int a[1000000]; void swap(int &x, int &y) { int z = x; x = y; y = z; } int choosePivot(int low, int high) { return low + (high-low)/2; // 중간 index 반환 } /* i와 j가 모두 증가하는 Lomuto Partition방식의 구현으로 swap을 진행하고 분할기준점을 반환함*/ int partition(int low, int high) { int pivotIndex = choosePivot(low, high); //..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-11-DP-문제-풀이10-백준-No2156-포도주-시식 # C++(Bottom-up방식 - 2차원 배열 사용) #include #include using namespace std; int arr[10001]; int d[10001][3]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; for (int i = 1; i > arr[i]; d[1][1] = arr[1]; // 1잔만 있을 경우 최대 값은 1잔을 마시는 것이므로. d[2][0] = arr[1]; // 2잔만 있을 경우 2번째 자리의 상태..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-10-DP-문제-풀이9-백준-No9465-스티커 # C++(Bottom-up방식) - max함수 쓸 때 STL은 인자 2개만 받는 것으로 정의되어있으니 2개씩 나눠서 해줘야 한다. #include #include using namespace std; int arr[100001][2]; // N번째라는 용어를 사용하여 알고리즘을 생각했으므로 index를 [1~100000][0~1] 를 사용할 수 있도록 함 int d[100001][3]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T; cin >> T; for (int..

포도주 시식 문제 - https://www.acmicpc.net/problem/2156 문제요약 포도주가 일렬로 놓여져 있고, 다음과 같은 2가지 규칙을 지키면서 포도주를 최대한 많이 마시려고 한다. 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 2. 연속적으로 놓여 있는 3잔을 모두 마실 수는 없다. 해결 방법1 (2차원 배열) 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "A[1]~A[N] 즉, N개의 포도주가 있을 때 가장 최대로 마실 수 있는 양" D[N][S] = "N개의 포도주 잔이 있고, N번째 포도주 잔의 상태가 S일 때 가장 최대로 마실 수 있는 양" S는 3가지 상태일 수 있..

스티커 문제 - https://www.acmicpc.net/problem/9465 문제요약 2xn 모양으로 놓여진 스티커가 있는데 각각의 스티커는 점수를 가지고 있다. 한장을 뗄 때마다 변을 공유하는 상하좌우의 스티커는 찢어져서 사용할 수 없게된다. 이때 떼어낸 스티커 점수들의 합의 최대값을 출력하시오. 해결 방법 무조건 큰 수부터 뜯어내면 최대합을 만들 수 있을까? 정답은 X 이다. 아래의 2x3 모양의 스티커 예시를 보자. 99 100 99 1 99 1 가장 큰 수인 100을 뜯어내면 합은 100 + 1 + 1 = 102이고, 99를 뜯어낸다고 하면 99 + 99 + 99 = 297이다. 따라서 최대합을 만들기 위해 무조건 큰 수 부터 떼네는 것은 옳지 않다. 위의 이유로 뜯는 순서가 정해져 있지 않..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-9-DP-문제-풀이8-백준-No11057-오르막-수 # C++(Bottom-up방식) #include using namespace std; int d[1001][10]; int main() { int n; cin >> n; // d[1][0~9], "길이가 1이고 0~9로 끝나는 수"에 대한 값 초기화 for (int i = 0; i

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-8-DP-문제-풀이6-백준-No10844-쉬운-계단-수?category=864321 # C++(Bottom-up방식) #include using namespace std; int d[101][10]; int main() { int n; cin >> n; // n이 1일 때 결과가 9이므로 해주는 초기화 for (int i = 1; i

다이나믹 프로그래밍 문제 * 다이나믹 문제만이 가지고 있는 패턴을 익히기 위해 많은 문제를 풀어보는 것이 중요함 1. 결과를 특정한 수로 나눈 나머지를 출력하라는 유형의 문제 - 접근 방법 : 최종 연산된 결과에만 나머지 연산을 수행하면 안되고, 값을 계산할 때 마다 d 배열에 나머지를 저장해야함. 그 이유는 출제자가 이미 중간 연산의 결과가 데이터의 저장범위를 넘어가는 것을 알고 있기에 이런 문제를 내는 것이고, 이렇게 해주지 않으면 의도된 답을 구할 수 없게 된다. 2. 2차원 이상의 배열을 사용해야하는 유형의 문제 - 접근 방법 : 점화식을 만들고 구현하는 것은 1차원 배열을 사용하는 문제와 동일하니, 1차원 배열로 풀어야하는지 2차원 배열로 풀어야 하는지 판단하는 능력을 길러야 한다. 1차원 배열..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-7-DP-문제-풀이6-백준-No0000-카?category=864321 # C++(Top-down방식) #include using namespace std; long long d[91] = {0}; long long getTwoChinNum(int n) { if ( n 0) return d[n]; else d[n] = getTwoChinNum(n-1) + getTwoChinNum(n-2); return d[n]; } int main() { int n; cin >> n; d[1] = 1; d[2] = 1; cout > n; d[1] = 1; d[2] = 1; for (int i=3; i