본문 바로가기
반응형

전체 글172

[백준/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.
[LeetCode] 66. Plus One (파이썬) 문제 링크 코딩하기 전 생각하기 ''' answer 배열을 생성한다. digits 배열을 숫자로 변환하자. 숫자에 1을 더한다. 숫자를 문자열로 변환하고 문자열을 순회하여 answer 배열을 채운다. ''' 코드 class Solution: def plusOne(self, digits: List[int]) -> List[int]: answer = [] num = 0 for n in digits: num = num * 10 + n num += 1 for c in str(num): answer.append(c) return answer 느낀점 c++로 먼저 하다가 오버플로우가 발생해서 파이썬으로 해결하였다. (주의) 기록용으로 작성한 글입니다. 코드가 허접하거나 알고리즘의 효율이 낮을 수 있습니다. 댓글 환.. 2021. 7. 24.
[프로그래머스] 2016년 (C++) 문제 링크 코딩하기 전 생각하기 /* 월별 날짜의 수가 담긴 벡터를 생성한다. 요일의 이름이 담긴 벡터를 생성한다. 날짜가 2016년의 몇번째 날인지 구하고 7로 나눈 나머지를 구하여 요일의 이름을 반환한다. */ 코드 #include using namespace std; string solution(int a, int b) { vector month_day = {31,29,31,30,31,30,31,31,30,31,30,31}; vector week = {"SUN","MON","TUE","WED","THU","FRI","SAT"}; int day = 4; for ( int i = 0; i < a - 1; i++ ) day += month_day[i]; day += b; return week[day % .. 2021. 7. 24.
[프로그래머스] 콜라츠 추측 (C++) 문제 링크 코딩하기 전 생각하기 /* 다음을 500번 반복한다. 숫자가 1이면 break한다. 숫자가 짝수이면 2로 나눈다. 숫자가 홀수이면 3을 곱하고 1을 더한다. 반복문이 끝날 때 까지 1이 나오지 않았으면 -1을 반환한다. 반복된 수를 반환한다. */ 코드 #include using namespace std; int solution(int num) { int i; long long n = num; for ( i = 0; i < 500; i++ ) { if ( n == 1 ) break; if ( n % 2 == 0 ) n /= 2; else n = n * 3 + 1; } if ( i == 500 ) return -1; return i; } 느낀점 디버깅을 해보니 num을 int로 했을 때 오버플로.. 2021. 7. 24.
[프로그래머스] 방문 길이 (C++) 문제 링크 코딩하기 전 생각하기 /* 이동 기록을 set에 저장하자. 처음 좌표를 0, 0으로 설정하자. dirs를 순회하자. 경계를 넘지 않고 이동했으면 원래좌표 + 현재좌표의 값을 set에 저장한다. set의 크기를 반환한다. */ 코드 #include #include using namespace std; int solution(string dirs) { int x = 0, y = 0; unordered_set s; string str1, str2; for ( auto c : dirs ) { int tmp_x = x; int tmp_y = y; bool go = false; if ( c == 'U' ) { if ( y < 5 ) { y++; go = true; } } if ( c == 'D' ) { .. 2021. 7. 24.
[프로그래머스] 약수의 개수와 덧셈 (C++) 문제 링크 코딩하기 전 생각하기 /* left부터 right까지 반복한다. (i) 1부터 i까지 반복한다. (j) i를 j로 나눴을 때 나머지가 0이면 count에 1를 더한다. count가 짝수이면 answer에 i을 더하고 아니라면 answer에 i를 뺀다. answer를 반환한다. */ 코드 #include using namespace std; int solution(int left, int right) { int answer = 0; for ( int i = left; i 2021. 7. 23.
[프로그래머스] 소수 만들기 (C++) 문제 링크 코딩하기 전 생각하기 /* 소수인지를 판별하는 함수를 선언하자. 2부터 해당 숫자가 되기 전까지의 수를 나누는데 나누어 떨어지는 수가 있으면 false를 반환한다. 3중 배열을 통해 세 개의 수를 선택하는 모든 경우의 수를 확인한다. 세 수를 더했을 때 소수가 나오면 count에 1을 더한다. count를 반환한다. */ 코드 #include using namespace std; bool is_prime(int n) { for ( int i = 2; i < n; i++ ) { if ( n % i == 0 ) return false; } return true; } int solution(vector nums) { int count = 0; for ( int i = 0; i < nums.size(.. 2021. 7. 23.
[프로그래머스] 하샤드 수 (C++) 문제 링크 코딩하기 전 생각하기 /* 숫자를 문자열로 변환 후 순회하여 자리 수의 합을 구한다. 숫자가 자리 수의 합으로 나누어 떨어지면 true를, 아니라면 false를 반환한다. */ 코드 #include using namespace std; bool solution(int x) { int sum = 0; for ( auto c : to_string(x) ) sum += c - '0'; if ( x % sum == 0 ) return true; return false; } 느낀점 딱히 없다. (주의) 기록용으로 작성한 글입니다. 코드가 허접하거나 알고리즘의 효율이 낮을 수 있습니다. 댓글 환영합니다! 2021. 7. 23.
[백준/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.
반응형

티스토리툴바