본문 바로가기

파이썬 5

[백준,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]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]PEP-8 코딩 스타일 [파이썬, Python]PEP-8 코딩 스타일 코딩을 하면서 좋은 코딩 습관, 스타일을 갖추는 것이 중요하다는 생각이 들었다. 그래서 기존 코딩 스타일을 버리고, 파이썬 프로그래머들의 일반적인 코딩 스타일인 'PEP-8' 스타일로 코딩 습관을 갖춰보려고 중요한 내용을 정리해 보려고 한다. www.python.org/dev/peps/pep-0008/ PEP 8 -- Style Guide for Python Code The official home of the Python Programming Language www.python.org 이 링크를 통해 들어가보면 PEP 8에 대한 자세한 소개가 있다. "PEP-8"스타일에 대한 장점 -이 코딩 스타일을 적용하는 것은 자신의 코드를 명료하게 할 뿐만 아니라, .. 2020. 12. 23.
[백준,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.

티스토리툴바