Coding_Test_C++
BaekJoon 2579번: 계단 오르기
풀이법 1) n의 수가 작다면 Backtracking으로 풀 수 있는 문제이지만 현재 n이 300까지 나올 수 있기에 DP로 푸는 것이 좋다. 2) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다. 단순한 1차원 배열로는 해당 문제에 대한 점화식을 도출하는 것이 쉽지 않을 것이라 생각한다. 해당 값이 연속된 계단인지 아닌지를 확인할 수 있는 점화식을 도출하는 것이 핵심이다. arr[i] : i번째 계단에 대한 입력 값 ans[i][0] : i 번째 계단을 밟았지만 연속된 계단이 아닐 때 ans[i][1] : i 번째 계단을 밟았는데 연속된 계단일 때 ans[i][0] = max(ans[i - 2][0], ans[i - 2][1]) + arr[i]; ans[i][1] = ans[i - 1][..
BaekJoon 9095번: 1, 2, 3 더하기
풀이법 1) n의 수가 작기에 for문을 이용하거나 다른 방식을 써도 좋지만 확장성을 고려한다면 DP로 푸는 것이 중요하다. 2) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다. 예시에 있는 4의 경우 1+1+1+1 / 1+2+1 / 2+1+1 / 3+1 1+1+2/ 2+2 1+3 형태를 띄는 것을 알 수 있다. 끝이 1로 끝나는 경우 3을 1, 2, 3의 합으로 나타내는 방법의 개수와 같고, 끝이 2로 끝나는 경우 2를 1, 2, 3의 합으로 나타내는 방법의 개수와 같고, 끝이 3으로 끝나는 경우 1을 1, 2, 3의 합으로 나타내는 방법의 개수와 같다. 최종 점화식은 D[i]=D[i-1]+D[i-2]+D[i-3] 이 될 것이다. #include #include #include #inc..
BaekJoon 12865번: 평범한 배낭
풀이법 1) DP를 이용하지 않으면 시간 초과가 일어날 수 있기에 DP를 이용해야 한다. 2) 유명한 0-1 Knapsack문제로 알고리즘 수업을 들은 학생들은 점화식을 생각해 내기 쉬울 것이다. 3) 점화식을 어떻게 세울지를 직접 고민하는 것이 추후 DP 문제를 풀 때 더 도움이 될 듯하여 자세한 풀이는 적지 않았다. 밑의 소스 코드에는 답이 있으므로 꼭 깊이 있게 생각하고 읽어주길 바란다. #include #include #include using namespace std; int n, k; vectorarr; bool visited[101]; long long maxNum = -1; int ans[100001]; void dfs(int weight, int value,int index) { if (..
BaekJoon 1026번: 보물
풀이법 1) 그리디 접근법을 사용하면 쉽게 풀 수 있는 문제이다. 2) A배열은 오름차순으로 B배열은 내림차순으로 정렬 후 이를 곱한 값들은 더하면 답을 쉽게 구할 수 있다. #include #include #include using namespace std; int n; vector a; vector b; long long ans=0; bool compare(int a, int b) { if (a > n; for (int i = 0; i > num; a.push_back(num); } for (int i = 0; i > num; b.push_back(num); } sort(a.begin(), a.end());/..
BaekJoon 2217번: 로프
풀이법 1) 그리디 접근법을 사용하면 쉽게 풀 수 있는 문제이다. 2) 내림차순으로 배열을 정렬한 후 하나씩 넣어보며 최대값을 비교한다면 어렵지 않게 풀 수 있을 것이다. #include using namespace std; int n; vector arr; long long ans=0; bool compare(int a, int b) { if (a > n; for (int i = 0; i > a; arr.push_back(a); } sort(arr.begin(), arr.end(),compare); for (int i = 0; i 25가 되어 값이 25..
BaekJoon 1074번: Z
풀이법 1) N의 크기가 크지 않기에 재귀함수로 풀 수 있는 대표적인 문제이다. 2) 분할과 재귀함수를 통해 시간 제한인 0.5초 이내에 값을 도출할 수 있었다. #include #include using namespace std; int n,r,c; int arr[2][2] = { {3,2},{1,0} }; void z(int r, int c,int n, long long max) { if (n == 1) { cout = a / 2) { max = max - (int)pow(4, n - 1)*2; z(r, c-a / 2, n - 1,max); } else if (r >= a / 2 && c < a/2) { max = max - (int)pow(4, n - 1); z(r-a / 2, c, n - 1,ma..
BaekJoon 2447번: 별 찍기 - 10
풀이법 1) N의 크기가 크지 않기에 재귀함수로 풀 수 있는 대표적인 문제이다. 2) 귀납적인 사고를 통해 문제를 해결하는 것이 Key point이다. 3) 종료 조건을 확실하게 정하는 것과, 좌표계를 이용하면 풀 수 있는 문제이다. #include using namespace std; int n; void star(int i, int j, int N) { if (N == 1) { cout n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { star(i, j, n); } cout
BaekJoon 11729번: 하노이 탑 이동 순서
풀이법 1) N의 크기가 크지 않기에 재귀함수로 풀 수 있는 대표적인 문제이다. 2) 귀납적인 사고를 통해 문제를 해결하는 것이 Key point이다. 1->3, 1->2, 2->3 등과 같이 기존에 절차 지향적으로 문제를 해결했던 분들에게는 어려웠을 문제라 생각된다. 어렵겠지만, 'k-1번째에서 가능하면 k 번째에서 가능하다'와 같은 귀납적인 사고를 이용한다면 문제를 수월하게 해결 할 수 있을 것이다. 3) 위의 그림에서 장대를 각각 stack 이라 부르고, 원판을 pan이라고 임의로 칭하겠다. 3번 stack에 5번 pan을 올리기 위해서는 2번 stack에 n-1번 pan까지 올려야한다. (핵심) #include #include #include #include #include #define INF ..
BaekJoon 14889번: 스타트와 링크
풀이법 1) N=20일 경우 시간 초과가 발생할 수 있으니 이를 고려해야 코딩해야 한다. 2) dfs와 백트래킹을 이용해서 모든 경우의 수를 돌아보는 완전 탐색 문제이다. 3) 백트래킹을 이용하여 스타트 팀으로 뽑을 선수 번호를 뽑는 것을 반복한다. #include #include #include #include #define INF 1000000001 using namespace std; int n; int arr[21][21]; bool visited[21]; int ans = INF; void backtracking(int player, int level) { if (level == n / 2) { vector start; vector link; int sumLink = 0; int sumStart..
BaekJoon 14888번: 연산자 끼워넣기
풀이법 1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다. 2) 재귀의 흐름과 매개변수를 잘 고르는 것이 중요하다. #include #include #include #include #define INF 1000000001 using namespace std; int n; vector vec; int arith[4]; int visit[4]; int maxVal = -INF; int minVal = INF; void backtrack(int temp,int level) { if (level == n) { if (temp > maxVal) { maxVal=temp; } if (temp < minVal) { minVal = temp; } return; }..