본문 바로가기

파이썬47

[백준/파이썬] 1956 : 운동 https://www.acmicpc.net/problem/1956 1956번: 운동첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의www.acmicpc.net문제 요약 : V개의 마을과 E개의 일방 통행 도로가 있다. 최소 사이클의 도로 길이 합을 출력하라. 불가능할 경우에는 -1을 출력하라. 다 풀어놓고 한참을 고생했다. 알고보니, INF값을 나름대로 큰 값을 준다고 변수들의 값을 참고해서 지정했는데, 거기부터 잘못된 시도였다.. V의 범위가 0부터 400사이였고, E의 범위가 V 보다 작거나 같았기 때문에 INF를 50.. 2023. 4. 1.
[백준/파이썬] 17427 : 약수의 합 2 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 문제 요약 : 자연수 A의 약수의 합은 f(A)이다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)이다. 자연수 N이 주어졌을 때, g(N)을 구하라. 시도 ) # 약수의 합2 import sys input = sys.stdin.readline ans = 0 for number in range(1,int(input(.. 2023. 3. 27.
[알고리즘/Python] 분할 정복(Divide and Conquer) 1. 분할 정복(Divide and Conquer)이란? 큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결하여 전체 문제의 해답을 구하는 알고리즘 문제의 크기가 커서 직접적인 해결이 어려운 경우 유용하다. 대표적인 예로, 정렬 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있다. 2. 동작 방식 문제를 작은 부분 문제들로 분할한다. 분할된 부분 문제들을 각각 재귀적으로 해결한다. 부분 문제들의 해답을 결합하여 전체 문제의 해답을 얻는다. 3. 시간 복잡도 시간 복잡도는 일반적으로 부분 문제의 개수, 분할된 문제의 크기, 분할과정의 복잡도에 따라 결정된다. 대부분의 경우, 분할 정복 알고리즘은 재귀적인 방법으로 문제를 해결하므로, 재귀 호출의 깊이에 따라 .. 2023. 3. 24.
[백준/파이썬] 6549 : 히스토그램에서 가장 큰 직사각형 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 요약 : 히스토그램의 개수n과 높이를 나타내는 정수들이 주어졌다. n이 0이 나오기 전까지 히스토그램 내부에 가장 넓이가 큰 직사각형의 크기를 구해라. 히스토그램과 거의 똑같은 문제! 풀이 ) 풀이의 흐름 입력값 read를 받아 histogram함수에 넣어준다. read[0]은 직사각형의 개수 N read[1:]은 각 직사각형의 높이 .. 2023. 3. 24.
[백준/파이썬] 1725 : 히스토그램 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 문제 요약 : 히스토그램의 높이가 주어졌다. 히스토그램 내부에 가장 넓이가 큰 직사각형의 크기를 구해라. 플래티넘인데 쉬워보이는데..? 했다가 며칠간 아주아주 치열하게 고민한 문제.. 맞은 코드는 아래 내리면 풀이에 작성해두었습니다! 시도 1 ) 스택문제인 만큼 스택의 특징을 잘 이용해야할 것이라 생각했다. 그치만 일단은 문제를 어떻게 풀어가야할 지 생각하기 위해 무식.. 2023. 3. 23.

티스토리툴바