프로그래밍

[백준_python] 회의실 배정 || 1931

www.acmicpc.net/problem/1931 1931번: 회의실 배정(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.www.acmicpc.net#회의실 배정 n = int(input()) #회의의 수 meeting = [] for _ in range(n): x, y = map(int, input().split(' ')) meeting.append((x, y)) meeting.sort(key = lambda x : (x[1], x[0])) cnt = 1 end = meeting[0][1] for i in range(1, n): if end > meeting[i][0]: pass else: end = meeting[i][1] cnt += 1 print(cnt)일단, 회의의 최..

[백준_python] ATM || 11399

www.acmicpc.net/problem/11399 11399번: ATM첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)www.acmicpc.net#ATM n = int(input()) person = list(map(int, input().split(' '))) person.sort() time = result = 0 for i in person: time += i result += time print(result)

[백준_python] 소인수분해 || 11653

www.acmicpc.net/problem/11653 11653번: 소인수분해첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.www.acmicpc.net에라토스테네스의 체를 이용해야하는 줄 알았따...#소인수분해(시간초과) def isprime(num): if num == 1: return False for i in range(2, int(num**0.5)+1): if num % i == 0: return False return True n = int(input()) prime = [] for i in range(1, n+1): if isprime(i): prime.append(i) while n!= 1: for i in prime: if n % i ==0: n = n/i print(..

[백준_python] 최소공배수 || 1934 (유클리드 호제법)

www.acmicpc.net/problem/1934 1934번: 최소공배수두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있www.acmicpc.net유클리드 호제법,,,기억이 안났다. ㅋㅋㅋㅋㅋㅋ 그래서 이전에 풀었던 2609문제를 다시 보며 적용해주었다..!#최소공배수 t = int(input()) for _ in range(t): x, y = map(int, input().split(' ')) a, b = x, y while b!=0: r = a % b a, b = b, r #유클리드 호제법 print(int(x * y / a))dmaol..

[백준_python] 파도반 수열 || 9461

www.acmicpc.net/problem/9461 9461번: 파도반 수열오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net1, 1, 1, 2, 2가 되기까지 규칙을 모르겠다가 그 후로부터 첫 요소와 끝 요소가 합해져서 3, 두 번째 요소와 끝 요소가 합해져서 4 ... 등등으로 쭉 늘어나는 규칙을 확인했다. dp[n] = dp[n-1] + dp[n-5] (점화식) t = int(input()) for _ in range(t): num = int(input()) arr = [1, 1, 1, 2, 2] if num > 4: for i in r..

[백준_python] 소수 구하기 || 1929

www.acmicpc.net/problem/1929 1929번: 소수 구하기첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.www.acmicpc.net2부터 쭉 나눠보기# 소수 구하기 # ? 시간 초과 m, n = map(int, input().split(' ')) arr = [i for i in range(m, n+1)] for i in arr: if i == 1: continue if i == 2: print(i) continue cnt = 0 for j in range(2, i): if i % j == 0: cnt += 1 if cnt == 0: print(i)시간 초과 발생!!에라토스테네..

[백준_python] 1, 2, 3 더하기 || 9095

www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.www.acmicpc.net이 문제 또한, 다이나믹 프로그래밍 문제이다. 1 : (1) 2 : (1, 1) (2) 3 : (1, 1, 1) (1, 2) (2, 1) (3) 4 : (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (2, 1, 1) (1, 3) (3, 1) (2, 2) → 7개 5 : (1, 1, 1, 1, 1) (1, 1, 1, 2) x 4 (1, 1, 3) x 3 (2, 3) x 2 (1, 2, 2) x 3 → 13개 = 7 + 4 + 2 6 : (1, 1, 1, 1, 1, 1) (1, 1, 1, 1, 2) x 5..

[백준_python] 1로 만들기 || 1463

www.acmicpc.net/problem/1463 1463번: 1로 만들기첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.www.acmicpc.net이 문제는 다이나믹 프로그래밍과 관련된 문제이다. 다이나믹 프로그래밍이란? 큰 문제를 작은 문제로 나누어서 푸는 기법, 작은 부분 문제들이 반복되는 경우를 매번 재계산하지 않고 재사용을 하는 기법이라고 한다. 구현 방식으로는 bottom-up과 top-down이 있다. bottom-up은 작은 문제부터 차근차근 푸는 것이고 top-down은 보통 우리가 아는 재귀 함수로, 큰 문제를 풀려하고 작은 문제가 풀리지 않았다면, 작은 문제를 푸는 방식이다.2 → 1 3번째 연산을 1회 해준다. 10 → 5 →4 →2→1이라는 방식도있지만..

[백준_python] 회전하는 큐 || 1021(global, deque.rotate())

www.acmicpc.net/problem/1021 1021번: 회전하는 큐첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net2번 연산은 1 2 3 -> 2 3 1 3번 연산은 1 2 3 -> 3 1 2 뽑으려는 값이 큐의 첫 번째 요소가 될 때까지 둘 연산을 각각 반복하고 그 중에 최소값을 선택하여 합하면서 총 연산의 최소 횟수를 구해준다.# 회전하는 큐 n, m = map(int, input().split(' ')) # n : 큐의 크기, m : 몇 번 뽑아낼 건지 arr = list(map(int, input().split(' ..

[백준_python] 패션왕 신해빈 || 9375

www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다.www.acmicpc.net# 패션왕 신해빈 from collections import Counter t = int(input()) for _ in range(t): n = int(input()) arr = [] for i in range(n): clothes, kind = input().split(' ') arr.append(kind) wear = ..