::SemiColon;;

이번 시간에는 저번시간 컴파일러 설치에 이어 c++ 개발환경설정을 위해 vscode를 설정해보겠습니다. 먼저 vscode extension을 설치해보겠습니다. vscode에 들어오셔서 맨왼쪽 이런 아이콘을 누르고 검색창에 c++이라고 치시면 다양한 extension들이 나옵니다. 여기서 C/C++ C/C++ Extension Pack C++ Intellisense C/C++ Theme 정도 설치해주시면 됩니다. 참고로 vscode 한국어 번역을 원하시면 검색창에 korean 치시고 Korean(사용법) Language Pack for Visual Studio Code 설치해주시면됩니다. 그리고 이제 vscode를 설정해주기 전에 파일을 생성해야합니다. 원하시는 곳 아무데나 폴더를 만들어서 vscode 파..

저는 원래 예전부터 c++로 문제풀이를 할때 계속 visual studio를 쓰다가 visual studio 프로그램 자체가 너무 크다 보니 텍스트 편집기로 바꿔야겠다라는 생각에 찾아보았습니다. 그러다 다른 언어들로는 visual studio code로 쓰고 있어서 visual studio code로 바꿔야겠다는 생각을 해서 c++ IDE를 visual studio code로 바꿔보았습니다. 그리고 제가 경험했던 것들을 이 visual studio code c++ 개발환경설정이라는 제목으로 순서대로 제가 어떻게 하였는지 알려드릴까합니다. 일단 저의 조건은 운영체제 64bit windows를 사용하고 있습니다. 처음으로는 visual studio code에는 따로 컴파일러가 없기 때문에 컴파일러를 설치해야..

1. 문제 https://www.acmicpc.net/problem/1654 2. 풀이 이 문제는 답을 이분탐색을 이용하여 구하는 문제이다. 답은 1부터 2^31 - 1사이에 존재한다. 따라서 이 사이의 값 중 답이 되는 값중에 최댓값을 구하기 위해 이분탐색을 사용하면 된다. 또 다른 주의할점은 이분탐색을 할때 mid값을 구할때 m = (l + r) / 2인데 l이 1이고, r이 2^31 - 1이어서 더하게 되면 int형 사이즈를 초과하기때문에 l, r, m을 long long 형으로 변환시켜줘야한다. 3. 소스코드 #include #include using namespace std; int n, k, arr[10000]; bool makeN(int m) { int line = 0; for (int i ..

1. 문제 https://www.acmicpc.net/problem/2579 2. 풀이 이 문제는 DP를 이용해 푸는문제이다. dp[i]는 i번째 계단은 밟고, 1부터 i번째까지 최대의 수이다. 즉 dp[i]는 그 바로 전단계의 계단을 밟은 여부에 따라 바뀌는 것이다. (시작) dp[0] = 0 dp[1] = arr[1] dp[2] = arr[1] +arr[2] (3≤i≤n) dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] +arr[i])이다. cf) https://zcacoding.tistory.com/20 [백준/BOJ] 2156 - 포도주 시식 (c++) (DP) 1. 문제 https://www.acmicpc.net/problem/2156 2. 풀이 이 문제는..

1. 문제 https://www.acmicpc.net/problem/1932 2. 풀이 이 문제는 DP를 이용하여 푸는 문제이다. 이번 dp배열은 2차원 배열을 사용할 것이다. 점화식부터 살펴보자면 초기값: dp[0][0] = tri[0][0] (j=0) dp[i][j] = dp[i-1][j] + tri[i][j] (j=i-1) dp[i][j] = dp[i-1][j-1] + tri[i][j] (1≤j≤i-2) dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j] 이다. dp는 위에서부터 최대값을 구할 것이다. 자기자신의 위에 있는 왼쪽, 오른쪽 중 dp값의 더 큰 값을 구해 자기자신(tri[i][j])의 값과 더하면 dp[i][j]가 만들어지는 것이다. 하지만 맨..

1. 문제 https://www.acmicpc.net/problem/9461 2. 풀이 문제에서 P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이라고 하였다. 위의 수열을 보면 P(i) = P(i-2) + P(i-3)이라는 것을 알 수 있다. 이를 통해 코딩을 하면된다. 3. 소스코드 #include using namespace std; int t, n, mxn = 3; long long dp[101]; int main() { ios::sync_with_stdio(0); cin.tie(), cout.tie(); dp[1] = dp[2] = dp[3] = 1; cin >> t; while (t--) { cin >> n; if (mxn < n) { for (..

1. 문제 https://www.acmicpc.net/problem/2156 2. 풀이 이 문제는 DP를 이용하여 푸는 문제이다. 중요한점은 dp[i]를 i번째 포도주(자기자신)을 먹은 여부에 따라 설정하는 것이다. 일단 첫번째로 i번째 포도주(자기자신)을 먹었다고 한다면 i번째 포도주(자기자신)을 먹었기 때문에 i-1번째 포도주를 안 먹었다면 dp[i] = dp[i-2] + arr[i]이다. i-1번째 포도주를 먹었다면 dp[i] = dp[i-3] + arr[i-1] + arr[i]이다. 두번째로 i번째 포도주(자기자신)를 안먹었다고한다면 i-1번째 포도주를 먹든 안먹든 상관이 없어지기 때문에 dp[i]는 dp[i-1]이게 된다. 즉 dp[0] = 0, dp[1] = arr[1], dp[2] = dp[..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 위의 문제는 계단수의 성질와 DP를 이용하여 푸는 문제입니다. 맨 앞자리는 0이 오지못한다는 주의할 점도 있습니다. 맨뒷자리에 따라 뒤에 올 수 있는 수가 정해져있습니다. 맨 뒷자리가 0: 1, 1: 0, 2, 2: 1, 3, ... 8: 7, 9, 9: 8 이렇게 됩니다. 즉 인접하는 수의 전단계 계단수를 더하면 현재의 계단수를 구할 수 있게되는것입니다. 점화식으로 작성해보자면 dp[i][j]: 길이가 i이고 마지막 수가 j인 계단수의 개수 j=0 이면 dp[i][0] = dp[i-1][1] j=9 이면 dp..

https://www.acmicpc.net/problem/1003 피보나치 함수는 대표적인 다이나믹프로그래밍 문제이다. 피보나치 함수는 f(0) = 0, f(1) = 1, n>=2, f(n) = f(n-1) + f(n-2)의 꼴이다. 위의 문제는 0이 나오는 횟수와 1이 나오는 횟수를 출력하는 것이다. 따라서 n=0: {1,0} n=1: {0,1} n=2: {1,1} n=3: {1,2} n=4: {2,3} .... 이렇게 이어진다. 위의 순서를 보고 규칙을 찾으면 n=i: {i-1 의 첫번째 원소 + i-2 의 첫번째 원소, i-1 의 두번째 원소 + i-2 의 두번째 원소}이다. 따라서 이에 맞게 함수를 작성하면 pair fibo(int a) { if (dp[a] != make_pair(0, 0)) r..

https://www.acmicpc.net/problem/1149 기본적인 DP문제입니다. 문제를 푸는 아이디어는 집을 색칠할 수 있는 3가지 색깔의 경우의수를 모두다 구해보는 것입니다. 코드로는 for (int i = 1; i < N; i++) { dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + input[i][0]; dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + input[i][1]; dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + input[i][2]; } 이렇게 될것입니다. dp[i][j]는 i번째 집을 j색깔로 칠했을때의 최소비용입니다. 따라서 dp[i][0]은 i번째 집을 0번 페인트로 칠했을때 ..