본문 바로가기

BaekJoon/Algorithm 8

[백준,Python]7576번 토마토(Graph Search/BFS, 시간초과 해결) [백준,Python]7576번 토마토(Graph Search/BFS) www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 테스트 케이스들을 모두 통과하도록 코드를 짰지만 , 반복문이 많이 들어가서 불안했는데 '시간초과'가 발생하였다. 시간초과가 발생했던 코드와 개선하여 효율적으로 짠 코드를 비교해가며 이번 문제를 설명하려 한다. 1. 처음 코드( 시간 초과) import sys input = sys.stdin.readline m,n = map(i.. 2021. 2. 21.
[백준,Python]15903번 카드 합체 놀이(Greedy) [백준,Python]15903번 카드 합체 놀이(Greedy) www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 이번 문제의 알고리즘은 Greedy이고, 1. 처음 푼 풀이와 2. 효율적인 풀이를 비교하며 설명하려고 한다. 1. 처음 푼 풀이 import sys input = sys.stdin.readline a,b = map(int, input().split()) card = list(map(int,input().spli.. 2021. 2. 19.
[백준,Python]16953번 A->B(Greedy) [백준,Python]16953번 A->B(Greedy) www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 이번 문제는 빠른 시간안에 문제 해결을 하였지만, 시간 초과 문제로 여러가지 고민을 하게 만들었던 문제이다. 문제 해결 알고리즘은 B를 처음에 10으로 나눈 나머지가 1인 것 체크하고 다음으로 2로 나눈 나머지가 0 인것들을 체크하여 b를 계속 수정하여 A에 도달하게 만들도록 구현하였고, 첫번째 코드는 시간초과, 두번째 코드는 그 문제를 해결한 코드이다. 처음 코드(시간초과) import sys input = sys.stdin.readline().strip a,b = map(int.. 2021. 2. 12.
[백준,Python]1003번 피보나치 함수(DP,dynamic programming) 1003번 피보나치 함수(DP)문제 : https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 이 문제는 테스트 케이스 수를 받고, 피보나치 함수를 실행했을 때 Fib(0)과 FIb(1), 0과 1이 몇 번 호출되는지 출력하는 문제입니다. 일단, 다른 문제들에서는 그렇게 시간 제한에 대한 제약이 없었는데, 이번 문제에서는 확실히 0.25초(감이 잘 안잡히긴 하지만) 줄어들었습니다.. 문제에서 요구하는 바가 확실히 , '이러이러한 식으로 풀면 컴파일 시간이 오래 걸리기에 풀지 마라'라고 정의 해 둔 것으로 느껴집니다. 일단 그런 것 상관없이 설마 시.. 2020. 8. 19.
[백준,Python]1932번 정수 삼각형(DP,dynamic programming) 백준 1932번 정수 삼각형(DP)문제 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 정수 삼각형에서 이어지는 경로로 탐색했을 때 모든 노드 수의 합의 최댓값을 구하는 문제를 리뷰하겠습니다. Dynamic Programming으로 푸는 문제이며, 하나씩 depth을 증가시키며 이어지는 경로로 내려가며 탐색을 진행해야 하므로 배열 arr이 있다고 하면, arr[i][j] = arr[i][j] +( arr[i.. 2020. 8. 17.
[백준,Python]1697번 숨바꼭질(BFS) 백준 1697번: 숨바꼭질 문제를 리뷰하는 시간을 가져보겠습니다. 문제를 요약하면, -N과K 두 수를 입력 받아 N이 K에 도달하는 최단 시간을 구하는 문제이고, N은 1초에 +1,-1,*2방법을 통해 이동할 수 있습니다. (자세한 문제 설명은 https://www.acmicpc.net/problem/1697를 참고하시면 됩니다.) 먼저, 이 문제는 BFS로 푸는 문제이며, DFS와의 차이에 대해서 간략하게 설명드리겠습니다. DFS는 탐색하면서 depth가 증가할 때 마다, 기준점을 바꾸고 재귀를 써서 탐색을 진행하게 되는데, 이 문제를 그렇게 풀 경우 무한 루프에 빠지므로 BFS로 푸는 방식을 이용해 탐색을 진행하도록 구현하였습니다. DFS로 풀지 않고 BFS로 푼다의 가장 큰 특징은 for문 또는 w.. 2020. 8. 15.

티스토리툴바