반응형 Algorithm/Baekjoon54 [백준/BOJ] 4150번 - 피보나치 수 (파이썬) 문제 링크 코딩하기 전 생각하기 ''' 메모이제이션을 활용하는 피보나치 재귀함수를 선언하자. ''' 코드 import sys sys.setrecursionlimit(10**6) memo = {} def fib(n): if n == 1: return 1 if n == 2: return 1 if n in memo: return memo[n] memo[n] = fib(n - 1) + fib(n - 2) return memo[n] n = int(input()) print(fib(n)) 느낀점 이 문제를 통해서 메모이제이션이라는 개념에 대해서 알 수 있었다. 이 방식의 시간복잡도는 O(N)이다. 다음 링크를 참고하였다. https://www.acmicpc.net/blog/view/28 피보나치 수를 구하는 여러가.. 2021. 7. 24. [백준/BOJ] 16435번 - 스네이크버드 (C++) 문제 링크 코딩하기 전 생각하기 /* 과일의 개수와, 처음 길이, 과일 벡터를 입력받는다. 과일 벡터를 오름차순으로 정렬한다. 과일의 개수만큼 반복한다. 과일이 스네이크버드의 길이보다 작거나 같으면, 스네이크버드의 길이에 1을 더한다. 아니라면, break 한다. 스네이크버드의 길이를 출력한다. */ 코드 #include #include using namespace std; int main() { int n, l, a; vector h; cin >> n >> l; for ( int i = 0; i > a; h.push_back(a); } sort(h.begin(), h.end()); for ( int i = 0; i = h[i] ) l.. 2021. 7. 23. [백준/BOJ] 1541번 - 잃어버린 괄호 (C++) 문제 링크 코딩하기 전 생각하기 /* '-'가 나오는 순간부터 다음 나오는 숫자들은 모두 뺄셈을 해주자. 기본값이 '+'인 연산자 변수를 선언하자. result 변수를 선언한다. 문자열을 입력받고 문자열을 순회한다. 문자가 숫자이면 숫자 변수에 저장한다. 문자가 숫자가 아닐 때, 연산자가 '+'이면 result에 숫자를 더한다. 연산자가 '-'이면 result에 숫자를 뺀다. 문자가 '-'이면 연산자를 '-'로 저장한다. result를 출력한다. */ 코드 #include #include using namespace std; int main() { string s; cin >> s; int result = 0, n = 0; char op = '+'; for ( auto c : s ) { if ( c >=.. 2021. 7. 23. [백준/BOJ] 11047번 - 동전 0 (C++) 문제 링크 코딩하기 전 생각하기 /* n과 k, 동전 벡터를 입력받는다. k가 0이 될 때 까지 다음을 반복한다. 동전 벡터의 뒤에서 부터 시작하여서 동전이 k보다 작거나 같으면 그 동전을 쓰고 count에 1을 더해준다. count를 출력한다. */ 코드 #include #include using namespace std; int main() { int n, k, a; cin >> n >> k; int count = 0; vector v; for ( int i = 0; i > a; v.push_back(a); } while ( k > 0 ) { for ( int i = v.size() - 1; i >= 0; i-- ) { if ( v[i] 2021. 7. 20. [백준/BOJ] 1181번 - 단어 정렬 (C++) 문제 링크 코딩하기 전 생각하기 /* 중복을 허용하지 않고 정렬하면서 값을 추가할 수 있는 set을 선언하자. n만큼 단어를 입력받고 set에 추가한다. set을 출력한다. */ 코드 #include #include using namespace std; bool comp(string a, string b) { if ( a.length() != b.length() ) return a.length() > n; set dict(comp); string s; for ( int i = 0; i > s; dict.insert(s); } for ( auto i : dict ) cout 2021. 7. 20. [백준/BOJ] 3040번 - 백설 공주와 일곱 난쟁이 (C++) 문제 링크 코딩하기 전 생각하기 /* 9개의 정수를 입력받는다. 2중배열을 이용해서 숫자 두개를 뺐을 때 합이 100이 되는 경우의 수를 찾는다. */ 코드 #include #include using namespace std; int main() { int a[9]; for ( int i = 0; i > a[i]; for ( int i = 0; i < 9; i++ ) { for ( int j = 0; j < 9; j++ ) { if ( i == j ) continue; int sum = 0; for ( int k = 0; k < 9; k++ ) { if ( k == i || k == j ) continue; sum += a[k]; } if ( sum == 100 ) { for.. 2021. 7. 18. [백준/BOJ] 15552번 - 빠른 A+B (C++) 문제 링크 코딩하기 전 생각하기 /* ios::sync_with_stdio(0)과 cin.tie(0)을 적용해준다. t을 입력받고 t만큼 반복한다. a, b를 입력받고 a + b를 출력한다. */ 코드 #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t, a, b; cin >> t; for ( int i = 0; i > a >> b; cout 2021. 7. 17. [백준/BOJ] 1920번 - 수 찾기 (C++) 문제 링크 코딩하기 전 생각하기 /* unordered_set을 선언한다. n을 입력받고 n만큼 반복한다. 정수를 입력받고 set에 저장한다. m을 입력받고 m만큼 반복한다. 정수를 입력받고 그 수가 set에 있는지 확인한다. set에 있으면 1을 출력하고 없으면 0을 출력한다. */ 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); unordered_set s; int n, m, a; cin >> n; for ( int i = 0; i > a; s.insert(a); } cin >> m; for ( int i = 0; i < m; i++ ) .. 2021. 7. 17. [백준/BOJ] 2839번 - 설탕 배달 (C++) 문제 링크 코딩하기 전 생각하기 /* n을 입력받는다. n이 0이 될 때 까지 다음을 반복한다. n이 5로는 안나눠지는데 3으로는 나눠지면 3kg봉지를 하나 쓴다. 위의 경우가 아니면 5kg봉지를 하나 쓴다. 위의 경우가 아닌데 n이 5보다 작으면 -1을 출력하고 종료한다. 봉지의 개수를 출력한다. */ 코드 #include #include using namespace std; int main() { int n, count = 0; cin >> n; while ( n > 0 ) { if ( n % 5 != 0 && n % 3 == 0 ) { n -= 3; count++; } else if ( n >= 5 ) { n -= 5; count++; } else { cout 2021. 7. 17. [백준/BOJ] 11478번 - 서로 다른 부분 문자열의 개수 (C++) 문제 링크 코딩하기 전 생각하기 /* unordered_set으로 사전을 만들어보자. 2중 반복문과 substr 메서드를 이용해서 만들어지는 부분 문자열을 모두 구한다. 부분 문자열을 사전에 추가한다. 사전의 크기를 출력한다. */ 코드 #include #include #include using namespace std; int main() { unordered_set dict; string s; cin >> s; int len = s.length(); for ( int i = 0; i < len; i++ ) { for ( int j = 1; j < len - i + 1; j++ ) dict.insert(s.substr(i, j)); } cout 2021. 7. 17. 이전 1 2 3 4 5 6 다음 반응형