본문 바로가기
728x90

분류 전체보기149

[백준] 1927번: 최소 힙 - python https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 힙 자료구조를 잘 사용할 수 있는지 테스트하는 문제 ^^ 전에 회의실 문제에서 사용해서 익숙해서 쉽게 풀었다. import heapq import sys input = sys.stdin.readline n = int(input()) hq = [] for i in range(n): m = int(input()) if m: heapq.heappush(hq, m) else: if h.. 2024. 4. 5.
[백준] 11724번: 연결 요소의 개수 - python https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 그래프 문제를 많이 풀어본적이 없어서 구현을 어떻게 해야할지 애를 많이 썻던 문제 아이디어 간선의 개수를 gragh 리스트에 전부 저장을 해준 뒤 방문 유무를 체크하면서 BFS로 색칠을 해준다. 그 후 cnt값을 계속 증가시키면서 최종 cnt를 출력하는 방식으로 구현하였다. from collections import deque imp.. 2024. 4. 5.
[백준] 5347번: LCM - python https://www.acmicpc.net/problem/5347 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. www.acmicpc.net 간단한 최소공배수 문제 간만에 최소공배수를 어떻게 구해야했는지 상기시킬 수 있었던 문제였다. 아이디어는 a * b 를 한 다음에 빼나가면서 작은게 0이면 그 나머지 값으로 나누는 아이디어다. n = int(input()) for i in range(n): a, b =map(int,input().split()) tmp = 0 s = a * b while b: tmp = b b = a % b a = tmp print(s // .. 2024. 4. 4.
[백준] 2630번: 색종이 만들기 - python https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 처음에 작성한 무지성 4로 나눠 재귀하기 코드이다. 너무 비효율적이고 틀렷다고 떠서 다시 로직을 작성하였다. n = int(input()) arr = [] blue = 0 white = 0 def paper(n, x_start, x_end, y_start, y_end): global blue global white x_mid = (x_start + x_end) //2 y.. 2024. 4. 4.
728x90

티스토리툴바