분류 전체보기582 [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. [C/C++] 백준 #2698 인접한 비트의 개수(동적 계획법) 동적 계획법(Dynamic Programming)으로 문제를 풀기 위해서는, 해당 문제에 대한 모델링을 해주어야 합니다. 모델링(modeling)을 할 때에는 N의 문제를 그보다 크기가 작은 N-1이나 N/2의 문제 등 보다 작은 형태로 나누어 주어야 하죠. 보통 N-1 문제로 표현할 수 있는 경우에는 시간 복잡도가 O(N)이 되며, N/2 문제로 표현할 수 있는 문제는 O(logN) 또는 O(NlogN) 문제로 표현될 수 있습니다. 예를 들어서 피보나치 수열의 경우에는 N의 문제를 N-1 문제와 N-2 문제로 해결하며, 이 것을 그대로 적용하면 O(N)이 되며, 보다 적극적인 방법으로 이분 탐색을 진행한다면, O(logN) 복잡도로 해결할 수 있습.. 2024. 8. 9. [C/C++] 백준 #2696 중앙값 구하기(힙) 힙(heap) 자료구조는 알고리즘에서 다양한 곳에서 사용할 수 있습니다. 우선순위큐가 대표적이고, 이 문제와 같이 중앙값을 찾는 용도로도 사용할 수 있습니다. 검색, 삽입, 삭제가 모두 O(logN) 의 시간 복잡도를 가지므로, 큰 N에 대해서도 매우 빠르게 검색, 삽입, 삭제를 할 수 있습니다. 아래는 문제의 링크입니다.https://www.acmicpc.net/problem/2696 주요 포인트는 다음과 같습니다. 1. 입력과 출력 관리 • scanf를 사용하여 입력을 받고, printf와 putchar를 사용하여 출력을 합니다. • 여러 테스트 케이스를 지원합니다. 2. 힙(heap)을 이용한 중간값 찾기 • 최대 힙(max-heap)과 최소 힙(min-heap)을 사용하여 중간값을.. 2024. 8. 7. 이전 1 ··· 9 10 11 12 13 14 15 ··· 97 다음 728x90
