728x90 반응형 백준241 [백준] 17299번 : 오등큰수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/17299 1. 문제 설명2. 풀이과정해당 문제는 이전의 17298번 : 오큰수 문제와 유사한 문제이다.이전의 오큰수 문제는 단순히 오른쪽에 있는 값들 중 큰 값에서 가장 왼쪽에 있는 값을 구하는 문제였지만,해당 오등큰수 문제는 거기에 숫자의 개수도 커야 하는 조건이 추가되었다. N의 최대 크기가 1,000,000이므로 반복문을 사용해 오등큰수를 찾으면 제한 시간을 초과하게 된다.하여 스택을 활용해 문제를 해결한다.오등큰수가 존재하지 않는 수는 -1을 출력하므로 오등큰수를 저장할 리스트를 -1로 초기화한다.오등큰수는 해당 수 다음 수들에서 찾아야 하므로 숫자들의 개별 값이 아닌 인덱스를 저장할 스택을 생성한다.스택에 원소가 있고 스택의 제일 마지막.. 2024. 9. 11. [백준] 9935번 : 문자열 폭발 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/9935 1. 문제 설명2. 풀이과정해당 문제는 폭발 문자열이 문자열에 없을 때까지 반복하며 최종적으로 남은 문자열을 출력하는 문제이다.만약 남은 문자열이 없으면 FRILA를 출력한다.스택 자료구조를 활용하여 전체 문자열에서 문자를 하나씩 가져오며 스택 자료구조에 추가한 뒤, 스택 자료구조에서 폭발 문자열의 길이만큼의 마지막 부분을 확인하여 폭발 문자열과 일치하면 해당 문자열을 제거한다.전체 문자열에서 각 문자를 하나씩 가져오며 매번 폭발 문자열이 있는지 확인할 것이기 때문에 늘 마지막 부분만 확인하여 제거해 주면 된다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys전체 문자열을 입력받는다... 2024. 9. 9. [백준] 7579번 : 앱 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/7579 1. 문제 설명2. 풀이과정해당 문제는 주어진 M 바이트 이상의 메모리를 추가로 확보할 때 드는 비용의 최솟값을 구하는 문제이다.해당 문제는 배낭 문제(Knapsack Problem)와 유사하여 이와 관련된 다이나믹 프로그래밍(Dynamic Programming) 알고리즘을 사용하면 해결할 수 있다.2차원 dp 배열을 생성하여 dp[i][j] 값에 i번째까지의 앱을 고려했을 때 j 비용만 들여 확보할 수 있는 최대의 메모리를 저장하면 된다.비용의 최댓값은 모든 앱을 비활성화했을 경우 드는 비용이므로 모든 앱의 비용을 더해주면 된다.처음 각 앱까지만 고려했을 때 비용에 따른 최대 메모리는 이전 앱까지만 고려했을 때 비용에 따른 최대 메모리로.. 2024. 9. 8. [백준] 2293번 : 동전 1 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/2293 1. 문제 설명2. 풀이과정해당 문제는 동전을 여러 개 사용하여 가치의 합을 맞출 수 있는 모든 경우의 수를 구하는 문제이다.모든 경우의 수를 다 찾을 수 없으므로 동전의 가치가 가장 작은 것부터 가치의 합을 1부터 k까지 각 경우의 수를 차례대로 구하여 저장한 다음, 가치가 큰 동전을 하나씩 불러오며 해당 동전만으로 만들 수 있는 값을 구해 그 경우의 수를 이전 경우의 수에 추가한다.예제를 예시로 보면 동전의 가치가 가장 작은 1부터 각 가치를 1만 사용하여 경우를 구한다. 다음으로 2만 사용하여 경우를 이전의 경우에 추가하여 구한다.여기서 2는 0의 경우에 2를 추가한 경우이고, 3은 1의 경우에 2를 추가한 경우이다.4는 2의 경우에.. 2024. 9. 7. [백준] 2629번 : 양팔저울 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/2629 1. 문제 설명2. 풀이과정해당 문제는 여러 개의 추를 가지고 구슬의 무게를 확인하는 문제이다.각 구슬별로 무게를 확인할 수 있는지 없는지 출력하는 문제이다.해당 문제 총 3가지의 동작을 반복적으로 수행하며 확인하려는 구슬의 무게를 만들 수 있는지 없는지 확인하고 결과를 출력하면 된다. 따라서 재귀적으로 수행되어야 하고 만들 수 있는 무게를 저장하며 문제를 해결해야 한다.문제에서 이뤄지는 행동 3가지를 살펴보면 아래와 같이 나타낼 수 있다.추를 저울에 놓는다.추를 저울의 반대쪽에 놓는다. (저울에서 뺀다.)추를 놓지 않는다.3가지 행동을 하며 추를 활용해 확인할 수 있는 구슬의 무게를 찾는다.이때 만약 추의 개수가 전체 추의 개수를 넘어가.. 2024. 8. 28. [백준] 1520번 : 내리막 길 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1520 1. 문제 설명2. 풀이과정해당 문제는 이전 위치에서 다음 위치로 이동할 때 다음 위치가 이전 위치보다 낮은 높이로 이동해야 한다.마지막 위치까지 이동하면서 이동 가능한 총 이동 가능 경로의 수를 반환하는 문제이다.지도를 이동하는 문제라는 점에서 dfs나 bfs 알고리즘으로 해결해야 한다는 것을 파악할 수 있다.또 이동 가능한 총 경로의 수를 반환해야 한다는 점에서 이전의 결과들을 저장하는 다이나믹 프로그래밍 알고리즘을 활용해야 한다는 것도 파악할 수 있다.dfs 알고리즘으로 0, 0에서 출발하여 이동 가능한 다음 위치를 찾아 최대한 마지막 위치까지 이동한다.만약 마지막 위치에 도달하면 가능한 경로를 찾았으므로 1을 반환한다. 만약 도달한.. 2024. 8. 3. [백준] 11049번 : 행렬 곱셈 순서 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/11049 1. 문제 설명2. 풀이과정해당 문제는 백준 11066번 : 파일 합지기 문제와 풀이 방법이 유사하다.해당 문제 역시 행렬을 모두 곱하는 연산을 수행할 때 필요한 곱셈 연산의 수가 최소가 되는 값을 구하는 문제이다.행렬을 하나하나 곱하면서 최종 결과가 최적일 때, 바로 이전의 결과들 또한 최적이어야 하는 문제, 즉 이전 11066번 문제와 동일하므로 다이나믹 프로그래밍 알고리즘을 활용하여 문제를 해결해야 한다. 이번 문제는 단순히 덧셈 연산만 존재하는 것이 아니라 행렬의 곱셈 연산으로 인해 곱셈 연산이 추가되었다.추가된 곱셈 연산을 어떻게 수행해야 하는지를 찾는 것이 중요하다.11066번 문제와 마찬가지로 곱셈할 행렬의 개수를 늘려가며 .. 2024. 7. 31. [백준] 11066번 : 파일 합치기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/11066 1. 문제 설명2. 풀이과정해당 문제는 여러 개의 파일을 하나의 파일로 합치는 과정에서 필요한 총 비용을 구하는 문제이다.해당 문제의 핵심은 파일을 합치는데 필요한 최소 비용을 구하는 것이다.문제의 첫 번째 예시를 살펴보면 각 파일의 크기가 40, 30, 30, 50 일 때, 파일을 하나로 합칠 수 있는 방법은 총 5가지이다.5가지 방법 중 최소 비용인 300을 구하는 것이 문제의 핵심이 된다. 문제를 해결하기 위해서는 2개의 파일을 1개의 파일로 합치는 과정을 최종 1개의 파일이 될 때까지 반복해야 한다.이를 다시 생각해 보면 최종 결과가 최적의 경우일 때, 이전의 2개의 파일을 1개의 파일로 합치는 2개의 파일 또한 최적의 경우이어야.. 2024. 7. 29. [백준] 1927번 : 최소 힙 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1927 1. 문제 설명2. 풀이과정해당 문제는 백준 11279번 : 최대 힙 문제와 유사하다.이전 11279번 문제는 우선순위 큐에서 최댓값을 반환하도록 구현했다면 이번 문제는 최솟값을 반환하도록 구현해야 한다.기본적으로 우선순위 큐 자료구조를 구현하면 값들이 오름차순으로 정렬되어 저장되므로 그냥 값을 추가하고 저장된 큐 자료구조에서 값을 가져오면 최솟값이 반환된다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys우선순위 큐 자료구조를 구현하기 위해 queue 모듈에서 PriorityQueue 함수를 불러온다. from queue import PriorityQueue입력할 연산의 개수를 입력.. 2024. 7. 27. [백준] 11279번 : 최대 힙 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/11279 1. 문제 설명2. 풀이과정해당 문제는 자료구조 중 최대 힙을 이용하여 자연수를 배열에 넣거나 배열에서 가장 큰 값을 출력하고 값을 배열에서 제거하는 문제이다.문제는 최대 힙 자료구조를 구현해서 해결해야 하는데, 최대 힙 자료구조는 우선순위 큐 자료구조를 활용해 구현한다.우선순위 큐 자료구조를 활용해 값을 넣고 제거하는데, 기본 우선순위 큐는 오름차순으로 값이 정렬되어 값을 가져오면 저장되어 있는 값들 중 가장 작은 값을 가져오게 된다.하지만 해당 문제에서는 값을 가져올 때 가장 큰 값을 가져와야 하므로 우선순위 큐가 내림차순으로 정렬되어야 한다.하여 우선순위 큐에 값을 추가할 때 (기준, 값)과 같이 튜플 형태로 값을 추가한다.이때 기.. 2024. 7. 26. 이전 1 2 3 4 ··· 25 다음 728x90 반응형
