분류 전체보기80 [DFS] 1012 - 유기농 배추 (실버2) with Python https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 주저리 주저리 문제는 간단한 탐색 문제이다. 너비 탐색이던 깊이 탐색이던 문제가 없어서 깊이 탐색으로 진행하였다. 대표적인 dfs, bfs 문제로서 한번쯤 풀어보면 좋은 문제인것 같다. 문제 해결 import sys input = sys.stdin.readline T = int(input()) maps = [[False for _ in range(51)] for _ in range(51)] dx = [1,-1.. 2023. 2. 18. [DP] 9184 - 신나는 함수 실행 (실버2) with Python https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 주저리 주저리 문제에서 대놓고 시간이 오래 걸린다고 하고 있다. 재귀를 빠르게 끝내는 방법인 분할 정복 or dp 중에서 고르라는 것 같은데 문제를 보니 피보나치 처럼 이전 값을 메모라이징 하는 것이 옳다 판단해 dp로 작업을 시작하였다. 문제 풀이 일단 w함수를 수도코드에서 파이썬에 맞게 코드를 고쳐주었다. 그렇게 이제 dp를 만들고 메모라이징을 할려는 순간 a,b,c의 범위에 마이너스가 포함된 것.. 2023. 2. 18. [DP] 1149 - RGB 거리 (실버1) with Python https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 주저리 주저리 문제를 읽자마자 이게 어떻게 풀어야 할까 순간 고민을 했다. 하지만 시간이 0.5초이고... 그러면 적어도 브루트 포스나 백트래킹은 아닐거라 판단하였다. 하지만 탐색하면서 찾아야 하는 거기에 그럼 DP를 도입하기로 결정하였다. 문제는 간단하다 이웃하는 집과는 색이 달라야한다 끝! 다행이 첫 집과 끝 집이 연결되어 있는 원형모양이 아닌 직선모양인것이 쉬운 점이라 .. 2023. 2. 18. [이분탐색][해시] 1920 수 찾기 (실버4) with Python https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 주저리 설명 문제는 간단하다. A라는 배열을 주고 M이라는 배열을 주어 M의 배열 숫자 중 A의 배열에 들어가 있는것이 있는가? 이것이 문제이다. 문제는 시간 초이다. N이 십만, M이 십만 순전히 이를 다 찾는 다면 걸리는 시간은 O(n^2) 이러면 1초내로 실행이 될 거라 판단 되지 않는다. 따라서 문제에서 요구하는 것은 시간을 어떻게 줄일 것인.. 2023. 2. 18. 이전 1 ··· 15 16 17 18 19 20 다음 728x90
