Programming/BOJ277 [C/C++] 백준 #2877 4와 7(수학) 이번 문제는 접근하는 방법을 알고 있으면 쉽게 문제를 풀 수 있습니다. 문제의 링크는 다음과 같습니다.https://www.acmicpc.net/problem/2877 k번째 작은 숫자라고 했으니까, k+1의 숫자를 2진수로 변환합니다. 예를 들어서 k가 9이라면 k+1은 10이 되며, 이진수로 변환하면, 10102가 됩니다. 그러면 처음 1을 제외하고, 1을 7로, 0을 4라 변환하면 됩니다. 결과는 474을 얻게 되겠죠. 4, 7, 44, 47, 74, 77, 444, 447, 474 이므로 우리가 원하는 결과를 얻었음을 알 수 있습니다. 왜 k+1을 했는가를 생각한다면, 전 이 문제를 맨 처음은 무조건 1이 있다고 가정했습니다. 이진수 12는 아무것도 없는 상태이고,.. 2024. 8. 23. [Python]백준 #2824 최대공약수(큰수자료구조) 사실 이 문제는 복잡하게 문제를 풀어야 하지만,큰수(big integer)가 지원된다면, 유클리드 알고리즘으로 간단하게 구할 수 있습니다.보통은 제가 C/C++을 이용해서 풀이를 해오고 있지만, 큰수 자료구조를 사용하기 위해서 파이썬을 이용해보았습니다. https://www.acmicpc.net/problem/2824 만약 큰수 자료구조를 지원하지 않는다면, 가장 큰 수의 제곱근을 기준으로 해서 그 이하의 소수들에 대하여 공약수를 구하는 방식을 사용해야 합니다. 큰수 자료구조끼리의 연산이 시간이 오래 걸리지만, 이 문제에 있어서는 큰수 자료구조를 사용한다고 해서 문제가 될만큼은 아닙니다. """ baekjoon #2824 - by Aubrey Choi - created .. 2024. 8. 18. [Python] 백준 #2812 크게 만들기(탐욕 알고리즘) 이번 문제는 n개의 자리를 가진 숫자에서 k개의 자리수를 제거하여 n-k개의 자리를 가진 수 중에 가장 큰 수를 만드는 것입니다. 문제의 링크는 다음과 같습니다.https://www.acmicpc.net/problem/2812 저는 스택(stack)을 이용한 탐욕 알고리즘을 이용해서 문제를 풀었습니다. 알고리즘은 간단합니다. 다음수가 맨 마지막수보다 크고 빼어야할 수가 있다면, 맨 마지막수를 빼고 다음수를 추가하는 방식입니다. 입력 받기n, k = map(int, input().split())- 이 부분은 `n`과 `k`를 입력받습니다. `n`은 문자열 `s`의 길이, `k`는 제거할 문자 개수를 의미합니다.스택 초기화stack = ["9"]- 가장 큰 수를 만들기 위해 사용할 스택을 초기화합니다... 2024. 8. 17. [C/C++] 백준 #2805 나무 자르기(이분 탐색) 이분 탐색은 단순증가하는 형태의 함수에서 원하는 값을 빠르게 찾는데 사용을 합니다. 시간 복잡도는 O(logN)이 됩니다. 하지만, 어떤 지점을 기준으로 실패와 성공이 갈릴 때, 그 기준점을 찾을 때에도 유용합니다. 나무 자르기 문제 역시 이분 탐색을 이용하여 성공할 때 최적값을 찾을 수 있습니다. 문제의 링크는 다음과 같습니다.https://www.acmicpc.net/problem/2805 코드 설명1. `readint()` 함수int readint() { int s=0,c; for(;;){ c=getchar(); if(c'9') break; s=s*10+c-'0'; } return s;}- 이 함수는 표준 입력으로부터 정.. 2024. 8. 16. [C/C++] 백준 #2749 피보나치 수 3(분할정복) 피보나치 수에 대한 알고리즘은 점화식에서 출발해서 재귀함수(recursion)를 배울 때 자주 인용되는 것이죠. 재귀함수를 사용하는 방법이 매우 많은 중복이 발생한다는 문제를 거론하면서 동적계획법(Dynamic Programming)을 사용해야 하는 이유를 설명할 때에도 많이 쓰입니다. 재귀함수를 단순하게 이용하면, 시간 복잡도가 O(ϕN)으로 기하급수로 늘어나지만, 이를 동적 계획법 또는 포워드 프로그래밍(Forward Programming)을 사용하면, 시간 복잡도가 O(N)으로 급격하게 줄어들 수 있습니다. 하지만 이번 문제는 N 자체가 O(N) 알고리즘으로 해결하기 어려운 문제입니다. 그래서 분할 정복을 사용해야 하고, 이를 이용하면 시간 복잡도를 \(O(\log.. 2024. 8. 12. [C/C++] 백준 #2718 타일 채우기(동적계획법) 경우의 수를 알아내라는 문제들 상당수는 동적계획법(Dynamic Programming)으로 해결할 수 있습니다.하지만 동적계획법을 사용하기 위해서는 문제를 올바르게 이해하는 것이 선행되어야 합니다. 2xn일 때에는 피보나치 수열과 비슷한 점화식을 얻을 수가 있습니다. 하지만 3xn, 4xn 과 같이 수가 늘어나면 조금 더 복잡한 점화식이 필요합니다. 일단 제가 모델링한 것은 조금 복잡합니다.이전값에 대해서 4개값까지 참고를 하니까요. 문제는 다음 링크와 같습니다.https://www.acmicpc.net/problem/2718 프로그램 설명: 1. 함수 solve(int n) • 이 함수는 주어진 n 크기의 바닥을 채우는 방법의 수를 계산하고 출력합니다. • 이 문제에서는 특이한 점이 있는데, 점화.. 2024. 8. 10. 이전 1 2 3 4 5 ··· 47 다음 728x90
