몽상실현개발주의

https://www.algospot.com/judge/problem/read/RATIO# algospot.com :: RATIO 승률올리기 문제 정보 문제 싸비는 윈도우XP 운영체제에 포함되어 있는 스파이더 카드게임을 매우 좋아한다. 처음에는 지는 경우가 있었는데, 점점 연습을 함에 따라 필승법을 발견하였고 매번 www.algospot.com 풀이 주어진 승률에서, 승률을 1% 올리기위한 연승 횟수를 구하는 문제이다. 먼저, 최대 횟수 연승 후에도 승률 1% 가 오르지 않는 경우를 제외하였다. 그리고 최소 연승 횟수가 최대 연승 횟수와 같아질 때 까지 이진탐색을 시행하였다. T = int(input()) for _ in range(T): N, M = map(int, input().split()) Z =..

https://www.algospot.com/judge/problem/read/LOAN# algospot.com :: LOAN 전세금 균등상환 문제 정보 문제 집을 떠나 혼자 살게 된 재훈이는 회사 근처의 전세집을 알아보고 있습니다. 전세금은 N원인데, 재훈이는 이것을 연이율 P%로 대출받을 수 있습니다. 재훈이는 M www.algospot.com 풀이 대출금의 연 이자를 특정 개월 수로 균등상환 하였을때, 상환 금액을 이분법을 이용하여 구하는 문제이다. 이분법을 시작 할 때, hi 금액은 할부금을 값지 않은 상황인 "원금+이자" 가 된다. T = int(input()) def checkC(N, M, P, C): for _ in range(M): N += (N * P / 12 / 100) N -= C r..

https://www.algospot.com/judge/problem/read/ROOTS algospot.com :: ROOTS 단변수 다항 방정식 해결하기 문제 정보 문제 실수 근만을 갖는 ax2 + bx + c = 0과 같은 형태의 단변수 다항 방정식이 주어질 때, 이들의 근을 계산하는 프로그램을 작성하세요. 다항식의 모든 해의 www.algospot.com 풀이 최대 5차 방정식의 해를 이분법을 이용하여 근사하는 문제이다. 이분법의 구간은 최소 -10, 주어진 방정식 그래프의 변곡점, 최대 10 으로 두고 이분법을 실행하여야 한다. 변곡점은 주어진 방정식을 미분한 식의 해 이므로, 해를 근사 할 수 있는 1차방정식까지 연속하여 미분하고 이를 이용하여 해를 구하는 방법으로 풀이하였다. C = int(..

[프로그래머스] level2 / 거리두기 확인하기 / Python 파이썬 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 풀이 주어진 지도..

[BOJ] 2143 / 두 배열의 합 / Python 파이썬 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 두 배열의 부분 배열의 합이 T 가 되는 경우의 수를 구하는 문제이다. 배열 A와 B 의 부분 배열의 합은 각각 구하여 이분탐색으로 경우의 수를 줄였고, 배열의 합을 탐색하는 방법은 두 포인터를 이용하였다. T = int(input()) N = int(..

[BOJ] 2632 / 피자판매 / Python 파이썬 https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 풀이 피자 A 와 B 를 원형 queue 로 설정하고, 이분탐색으로 경우의 수를 구하여 해결하였다. import sys input = sys.stdin.readline BUY = int(input()) M, N = map(int, input().split()) A = [] for _ in range(M): A.append(..

[BOJ] 7453 / 합이 0인 네 정수 / Python 파이썬 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 풀이 A, B, C, D 네 배열 각각의 원소 하나씩을 뽑아 그 합이 0이 되는 쌍의 조합의 개수를 구하는 문제이다. A, B, C, D 네 쌍을 한번에 완전탐색으로 진행하게 되면 최대 4000**4 가 되기 때문에 A 와 B 의 원소 조합으로 만들수 있는 경우를 구한뒤, C 와 D 의 조합을 구하여 해결하였다. ..

https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 1181 / 부분수열의 합 문제의 심화 문제이다. 부분수열의 합 문제의 경우에는 주어진 수열의 길이가 최대 20개 이므로 Combinations 과 DFS 로 모든 경우의 수를 구하여서 해결 하였다. 하지만 부분수열의 합 2 문제에서는 수열의 길이가 최대 40이기 때문에, 모든 경우가 2**40 개로 어마어마한 시간이 걸리게 된다. 이를 극복하기 위하여..