Storage Gonie

2xn 타일링2 문제 https://www.acmicpc.net/problem/11727 문제요약 2xn 직사각형을 2x1과 2x2 타일로 채워넣는 모든 방법의 수를 구하고, 이를 10007로 나눈 나머지를 출력해라 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "2 x N 직사각형을 채우는 모든 방법의 수를 10007로 나눈 나머지" -> "2 x N 직사각형을 채우는 모든 방법의 수" 로만 일단 생각하자. 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 2 x N의 직사각형이 주어지면 마지막 위치에 3가지 방법 중 1가지를 선택할 수 있다. Case1) 세로로 1개를 놓는 경우 - 나머지 2 x (n-1) 크기의 직사각형을 채워넣..

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-3-다이나믹-프로그래밍-문제-풀이2 # C++(Top-down 방식) #include using namespace std; int d[1001] = {1, 1}; // d[0] = 1, d[1] = 1, d[0~99] = 0 // d[0] = 1; 이 문제에서 점화식이 정상적으로 작동하려면 d[0]이 1이어야함. // d[1] = 1; 원래 d[1]은 1이라서. // N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수 int getAllCombiCount(int n) { if (n 0) // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환 return d[..

2xn 타일링 문제 https://www.acmicpc.net/problem/11726 문제요약 2xn 크기의 직사각형을 1x2, 2x1 타일로 채워넣는 모든 방법의 수를 구하고, 이를 10007로 나눈 나머지를 출력해라 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "2 x N 직사각형을 채우는 모든 방법의 수를 10007로 나눈 나머지" -> "2 x N 직사각형을 채우는 모든 방법의 수" 로만 일단 생각하자. 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 2 x N의 직사각형이 주어지면 마지막 위치에 2가지 방법 중 1가지를 선택할 수 있다. Case1) 세로로 1개를 놓는 경우 - 나머지 2 x (n-1) 크기의 직사각형을 ..

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-2-다이나믹-프로그래밍2 # C++(Top-down방식) #include using namespace std; int d[1000000] = {0}; // 1에서 1로 가는건 연산을 필요로 하지 않으므로 d[1] = 0, 그냥 모두 d[0~99] = 0 // N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수 int getSmallestCalCount(int n) { if (n 0) // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환 return d[n]; else { // 모든 수에서 가능한 연산인 -1을 먼저 해준다. d[n] = getSmallest..

1로 만들기 문제 https://www.acmicpc.net/problem/1463 문제요약 어떤 정수 N에 대해 다음과 같은 연산중 하나를 선택할 수 있다. 1) 3으로 나누어 떨어지면 3으로 나눈다. 2) 2로 나누어 떨어지면 2로 나눈다. 3) 1을 뺀다. 이를 반복하여 1을 만들려고 하는데 연산을 사용하는 횟수의 최소값을 출력해라. 해결방법 - 다른 문제에도 공통적으로 적용됨 1. D[N]에 어떤 값을저장할 것인지 문장으로 정의해줘야 한다. - 대부분의 다이나믹 문제는 문제에서 구하라는 값을 그대로 D[N]에 넣어주면 된다. - 따라서, D[N]= "정수 N을 1로 만드는데 필요한 연산 횟수의 최소값" 이라고 정의해 줄 수 있다. 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다...

* 최우선 순위라도 제대로 완료하면 미션 클리어. # 최우선 순위 - 코딩시험에서 '부족했던 점' 혹은 '주의할 점' 정리하기 @ 첫 번째 - 아무리 쉬운 문제일지라도 주석으로 구조를 나눈 다음 코딩하는 습관이 부족했으니 이를 고치자. @ 두 번째 - cin 혹은 scanf 다음에 바로 getline()을 호출 하게되면, 개행문자를 바로 받아버려서 getline()이 제대로 작동하지 않는 문제가 발생한다. 이를 해결하기 위해 실제 코딩시험에서는 둘의 연쇄작용이 일어나는 부분 즉, test_case가 1 일 때의 부분에 getchar()를 삽입해 주었다. cin >> T for(int test_case = 1; test_case A // input2 -> A B // input3 -> A B C #case..

# 배열 선언방법 @ 정적배열 // N * M 행렬 int arr[3][5]; // N * M 행렬 int arr[3][5] = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}}; // 배열 선언시 왼쪽인자를 생략할 수 있음. (오른쪽 인자는 생략 불가, 둘다 생략하는 것도 불가) int arr[][5] = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}}; @ 동적배열 - 아직까진 사용할 일이 없었어서 학습 보류(동적할당이 필요한 이유 포함) // 1차원 배열 할당받는 방법 int width = 8; int *arr; arr = (int *) malloc ( sizeof(int) * width )..

다이나믹 프로그래밍의 개념 # 다이나믹 프로그래밍(DP, Dynamic Programming) - 큰 문제를 작은 문제로 나눠서 푸는 알고리즘, 중복되는 작은 문제가 존재해 이에 대한 결과값을 저장해두어 계산 중복을 없애는 것. - 1940년 Richard Bellman이 단지 이름이 멋있어보여서 사용하게됨. - 한글로 '동적 계획법'이라고 불리는데, 이름은 아무의미없으니 이름에서 뜻을 찾지 말아라. # 위 알고리즘을 이용한 문제해결시 필요한 요소 - 아래의 두가지 전제조건 만족해야함 - 중간 결과값 메모(Memoization)를 위한 '배열'이 필요함 # 이 유형의 문제해결 능력 향상을 위해서 필요한 것 - 어려워 보이지만 패턴을 가지기 때문에 문제들을 많이 풀어보면서 감을 잡는 것이 중요하다. # 다..

# 사용방법 - 템플릿을 사용하므로 정수형, 벡터형 등 대부분 가능하다. #include #include #include using namespace std; int main(void) { int x = 10; int y = 20; vector vec1(4, x); // x로 초기화된 4개의 원소를 가지는 벡터 vector vec2(6, y); // y로 초기화된 4개의 원소를 가지는 벡터 swap(x, y); cout

# 배열 정렬 - sort(vec.begin(), v.end()) : 오름차순(default) - sort(vec.begin(), v.end(), less()) : 오름차순 - sort(vec.begin(), v.end(), greater()) : 내림차순 - sort(vec.begin(), v.end(), greater(), compare) : 함수기준 #include #include using namespace std; int main() { int arr[] = {3, 7, 2, 4, 1, 0, 8, 5, 6, 8}; int length = sizeof(arr) / sizeof(int); sort(arr, arr+length); for (int i=0; i< length ; i++) cout