N

피보나치 수열을 DP로 풀었다. 피보나치 수열에 관한 문제는 재귀, DP, 반복문을 사용하여 풀 수 있는데, 시간을 고려해야 하는 경우는 대부분 DP를 이용하면 풀 수 있다. 배열을 이용하여 F(n) = F(n - 1) + F(n - 2) 의 값을 저장한다. 반복문을 돌면서 계속해서 F(n - 1), F(n - 2)의 값을 가져오기 때문에 재귀보다 빠르게 풀 수 있다. #include #include using namespace std; int solution(int n) { int answer = 0; int num[100001] = {0, }; num[0] = 0; num[1] = 1; for(int i = 2; i

행렬의 곱셈을 구하는 문제다..! 제한 조건이 크지 않기 때문에 일반적으로 알고있는 행렬의 곱셈 방법으로 문제를 풀었다..! 딱히 설명할 부분은 없는 것 같다. 행렬의 곱셈만 할 줄 알면 풀 수 있는 문제..! #include #include #include using namespace std; vector solution(vector arr1, vector arr2) { vector answer(arr1.size(), vector(arr2[0].size(), 0)); for(int i = 0; i < arr1.size(); i++) { for(int j = 0; j < arr2[0].size(); j++) { for(int k = 0; k < arr1[0].size(); k++) answer[i][j]..

문자열의 대소문자를 변환해주는 toupper()와 tolower() 함수를 이용하였다. toupper()는 대문자로, tolower()는 소문자로 변환해준다..! 해당 문자가 알파벳인 경우 알맞게 변환해주고, 알파벳이 아닌 경우는 문자 그대로 리턴되기 때문에 이 특징을 살려서 함수를 사용하였다. 그리고 문자의 위치를 나타내는 index를 선언하였고, index가 0인 경우는 대문자로 변환해준다. 우선 s.size()만큼 반복하자. s[i]가 공백인지 아닌지를 검사해야 한다. 공백은 그대로 넣어주고, 공백 다음 문자는 JadenCase이기 때문에 index = 0으로 바꿔준다. 만약 공백이 아니라면 해당 문자는 알파벳이다. 그러면 index를 검사하여 0인지 아닌지 판단한다. 0이면 toupper(s[i]..

최대 공약수를 이용하여 최소 공배수를 구하는 방식을 사용하였다. gcd(최대 공약수) 함수와 lcm(최소 공배수) 함수를 정의하였다. for문을 돌면서 arr[i]와 arr[i + 1]의 최소 공배수를 구하여 arr[i + 1]에 다시 넣어주었다. 그래야 다음 최소 공배수를 구할 수 있기 때문이다..! arr.size() - 1 만큼 반복하면 N개의 최소 공배수를 구할 수 있다..! #include #include #include using namespace std; int gcd(int a, int b) { int c; while(b != 0) { c = a % b; a = b; b = c; } return a; } int lcm(int a, int b) { return a * b / gcd(a, b)..

스택을 이용하여 풀면 쉽게 해결할 수 있다. s.size()만큼 반복문을 돌면서 스택에 넣어주자. 만약 스택이 비어있거나 스택의 top이 현재 s[i]와 같지 않다면 스택에 s[i] 문자를 넣어주자..! 하지만 스택의 top이 s[i]와 같다면 pop()을 해주어 같은 문자를 제거하면 된다. 반복문을 다 돌게 되었을 때, 스택이 비어있다면 모든 문자를 짝지어서 제거했기 때문에 1을 반환, 비어있지 않으면 문자가 남아있다는 뜻이므로 0을 반환하면 된다..! #include #include #include using namespace std; int solution(string s) { int answer = 0; stack stk; for(int i = 0; i < s.size(); i++) { if(st..

dfs를 이용하여 문제를 풀어야 한다. 형태는 void dfs(vector& numbers, int target, int sum, int count) 이다. 처음 시작할 때는 sum은 0, numbers의 인덱스를 0으로 시작한다. dfs 내부) 우선 종료 조건을 선언하자. numbers의 익덱스를 나타내는 count가 numbers.size()인지 확인하면 된다. 그리고 현재 sum이 target과 같으면 answer++을 해주고 return을 시키면 알아서 카운팅이 된다. 만약 count가 numbers.size()보다 작다면 계속 탐색을 해야한다. 현재 sum에 + numbers[count]와 - numbers[count]를 하여 target과 같은지 탐색하면 끝..! #include #includ..

완전 탐색으로 문제를 풀었다..! 우선 카펫의 총 격자수를 sum과 current에 저장하고, while문으로 current > 1 일 때까지 반복하였다. while문 내부) 우선 sum의 약수를 구해야 하기 때문에 sum % current == 0인 수만 찾도록 한다. row는 나누려고 하는 수, col은 sum / current를 했을 때의 몫이다. 그러면 row * col == sum 이므로 약수가 된다. 약수를 구했다면 이제 brown과 yellow의 개수가 맞는지 확인해야 한다. 우선 col > 1이여야 한다. 왜냐하면 yellow의 개수를 구할 때 col - 2 를 해야하는데 음수가 나오면 안되기 때문이다. 그리고 문제에 나와있듯이 가로의 길이는 세로 길이와 같거나 길다고 하였기 때문에 row..

탐욕법으로 문제를 풀어야 한다. 우선 front와 back을 선언하여 각각 0, people.size() - 1을 대입한다. while문을 통해 front