728x90 반응형 파이썬438 [백준] 7576번 : 토마토 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/7576 1. 문제 설명2. 풀이과정해당 문제는 박스 안 토마토가 다 익을 때까지의 최소 날짜를 구하는 문제이다.만약 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지 못하는 상황이면 -1을 출력해야 한다.보관 후 하루가 지날 때마다 익은 토마토의 인접한 익지 않은 토마토들이 익게 된다.이렇게 익지 않은 토마토들이 익어가며 모든 토마토가 익는 최소 날짜를 구하면 된다.이는 박스 안 익은 토마토의 범위를 4방향으로 넓혀가며 모든 토마토가 익을 수 있는지 익을 수 있다면 최소 날짜를 구하는 문제이므로 너비 우선 탐색(BFS)으로 쉽게 구할 수 있다.해당 경로를 찾아나가는 것이 아니라 범위를 점점 넓혀가며 가능한 범.. 2024. 10. 6. [백준] 1725번 : 히스토그램 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1725 1. 문제 설명2. 풀이과정해당 문제는 이전의 6549번 : 히스토그램에서 가장 큰 직사각형 문제와 유사한 문제이다.하지만 이전 6549번 문제와 다른 점은 시간 제한이 1초에서 0.7초로 줄었다는 점이다.시간 제한이 줄었기 때문에 6549번 문제를 풀었을 때처럼 해결하면 시간초과가 발생할 수 있다.시간을 줄이기 위해 반복문이 최대한 적게 실행되도록 수정해보려고 했다.하여 이전 6549번 코드의 for 문 안 while 반복문이 최소한으로 실행되도록 수정했다. 스택 자료구조를 그대로 사용하고 막대의 위치를 한 번씩만 가져와서 스택 자료구조에 막대가 있고 마지막으로 저장된 막대의 높이가 현재 지정하고 있는 막대의 높이보다 크면 막대를 제거하.. 2024. 9. 28. [백준] 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. 이전 1 2 3 4 ··· 44 다음 728x90 반응형
