본문 바로가기
반응형

Programming/BOJ277

[C/C++] 백준 #2877 4와 7(수학) 이번 문제는 접근하는 방법을 알고 있으면 쉽게 문제를 풀 수 있습니다. 문제의 링크는 다음과 같습니다.https://www.acmicpc.net/problem/2877  k번째 작은 숫자라고 했으니까, k+1의 숫자를 2진수로 변환합니다.  예를 들어서 k가 9이라면 k+1은 10이 되며, 이진수로 변환하면, \(1010_2\)가 됩니다.  그러면  처음 1을 제외하고, 1을 7로, 0을 4라 변환하면 됩니다.  결과는 474을 얻게 되겠죠.  4, 7, 44, 47, 74, 77, 444, 447, 474 이므로 우리가 원하는 결과를 얻었음을 알 수 있습니다. 왜 k+1을 했는가를 생각한다면, 전 이 문제를 맨 처음은 무조건 1이 있다고 가정했습니다.  이진수 \(1_2\)는 아무것도 없는 상태이고,.. 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( \log N )\)이 됩니다.  하지만, 어떤 지점을 기준으로 실패와 성공이 갈릴 때, 그 기준점을 찾을 때에도 유용합니다.  나무 자르기 문제 역시 이분 탐색을 이용하여 성공할 때 최적값을 찾을 수 있습니다. 문제의 링크는 다음과 같습니다.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(\phi^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.
728x90

티스토리툴바