백준

[python] 백준 - 1325. 효율적인 해킹

🤔문제 해결 S2 | 그래프, BFS(DFS) 단순한 그래프 문제였는데 전부다 시간초과 발생.... 다른 분들 제출한것도 보니까 대부분 시간초과이다. (그래서 pypy3로 제출하니 성공) 풀이방법은 인접리스트 생성 (이 문제에서는 a->b가 아니라 b->a 이다) 모든 노드에 대해서 BFS를 돌린다. 그 때 몇개의 노드를 돌았는지 숫자를 세준다. 가장 높은 카운트의 노드들을 출력한다. 다른 분들의 풀이를 봤는데 풀이가 나랑똑같다. 하지만 어떻게 통과했는지... 💻소스 코드 import sys from collections import defaultdict from collections import deque def bfs(start): q = deque([start]) visited = [0] * (N ..

[python] 백준 - 2512. 예산

🤔문제 해결 S3 | 이분탐색 이분 탐색의 기본문제 이분탐색이란? 탐색 부분을 두 부분으로 분할해서 답을 찾는 과정이다. 1부터 10까지 값이 있다고 가정했을 때 7이란 값을 찾아보자 최소는 1이고 최대는 10이다. 절반으로 나누면 5인데 운이 좋아서 5가 맞으면 정답, 하지만 찾는 값은 7이므로 정답이 아니다 크기를 비교해서 찾는 값이 5보다 작으면 최대를 줄이고, 찾는 값이 5보다 크면 최소를 늘린다. 찾는 값이 5보다 크므로 최소를 늘린다. 최소는 절반+1 최대는 그대로 10이다. 절반으로 나누면 8 찾는 값은 8보다 작으므로 최대를 줄인다. 최소는 6 최대는 절반-1이다. 절반으로 나누면 6 찾는 값이 6보다 크므로 최소를 늘린다. 최소는 절반+1 최대는 7이다. 절반으로 나누면 7이므로 정답! ..

[python] 백준 - 2004. 조합 0의 개수

🤔문제 해결 S2 | 수학 진짜 팩토리얼로 구해서 문제를 해결하게 되면 시간초과 발생 끝자리가 0이라는 것은 10의 배수 10은 2와 5로 구성되어 있음 2와 5 짝이 맞아야 10이 되므로 2의 개수와 5의 개수중 더 작은게 10의 개수이다. 💻소스 코드 N, M = map(int, input().split()) # 진짜 팩토리얼로 구해서 문제를 해결하게 되면 시간초과 발생 # 끝자리가 0이라는 것은 10의 배수 # 10은 2와 5로 구성되어 있음 # 2와 5 짝이 맞아야 10이 되므로 2의 개수와 5의 개수중 더 작은게 10의 개수이다. def count_number(n, k): count = 0 while n: n //= k count += n return count five_count = count..

[python] 백준 - 2110. 공유기 설치

🤔문제 해결 S2 | 이분탐색 특정 범위 안에서 개수를 정한다? => 이분 탐색 공유기를 설치할 수 있는 최소간격과 최대간격의 중간값부터 시작 중간값(공유기 설치 간격)으로 공유기를 설치 했을 때 설치한 공유기가 부족하면 설치 간격을 좁혀서 더 많이 설치하자 설치한 공유기가 많거나 같으면 설치한 간격을 늘려서 덜 설치하거나 최대로 간격을 늘려보자 💻소스 코드 import sys N, C = map(int, input().split()) house = [int(sys.stdin.readline()) for _ in range(N)] # 정렬 house.sort() # 와이파이 간격을 얼마나 해야할지 모르니 최대거리와 최소거리의 중간부터 시작 left = 1 right = house[-1] - house[0..

[python] 백준 - 1735. 분수 합

🤔문제 해결 S2 | 수학 분수를 더해준다. ( 이 정도는 다 알고있을 것이다. ) 분자와 분모의 최대공약수(GCD)를 구한다. ( math 함수에 있는 기능 ) 분자와 분모를 GCD로 나누어준다. 💻소스 코드 import math a1, b1 = map(int, input().split()) a2, b2 = map(int, input().split()) bunjja = a1 * b2 + a2 * b1 bunmo = b1 * b2 my = math.gcd(bunjja, bunmo) bunjja //= my bunmo //= my print(bunjja, bunmo) 📕문제 확인 출처: BACKJOON ONLINE JUDGE 링크: https://www.acmicpc.net/problem/1735 1735..

[python] 백준 - 1965. 상자 넣기

🤔문제 해결 S2 | DP [python] 백준 - 11055. 가장 큰 증가 부분 수열 🤔문제 해결 S2 | 다이나믹프로그래밍 역시 이런 문제는 DP문제이다. dp 리스트를 만든다.(1차원, 인풋값으로 받은 수열과 똑같은 값으로 만든다.) 수열에서 자신보다 앞 쪽에 있는 값 중에서 자신 deok2kim.tistory.com 위의 문제와 살짝 비슷한 느낌이다. 값이 1로 셋팅된 길이가 n 인 dp 리스트를 만든다. dp = [1, 1, 1, ... ] 각각의 값은 현재 포함한 상자의 갯수이다. 맨앞의 상자부터 하나씩 뒤로가며 앞의 상자를 몇개나 담을 수 있는 지 체크한다. 만약 내앞의 상자가 나보다 작고 그 상자가 담고 있는 상자의 갯수(본인포함)가 5개라면 지금 나의 상자는 앞의 상자까지 담을 수 있으..