MakerHyeon

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 본 문제는 시간 제한이 1초이다. 단순풀이 재귀를 사용할경우 시간초과가 난다. 따라서 이미 구한 값들을 다시 활용하는 DP방식을 사용해야한다. SOLUTION CODE # PYTHON DP 적용 전(단순풀이->시간초과) def f(n): if n==0: return 0 elif n==1: return 1 return f(n-1)+f(n-2) print(f(int..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이중 for문은 N^2 이 되어 통과하지못함! 이분탐색을 이용해야 한다. SOLUTION CODE # PYTHON 풀이 1) 이분탐색 함수 이용 # 입력값 받기 N = int(input()) arr = list(map(int,input().split())) arr.sort() M = int(input()) user_input = list(map(int,input()...

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 방법이 여러가지 떠올라 고민을 정말 많이 했다. 명료하게 구해야하는것에 집중하자. '배정된 예산들 중 최댓값인 정수를 출력' 해야 한다. 이분탐색을 이용해 정답을 좁혀나간다. 예산이 너무크면 줄이고,너무 작으면 늘린다. (파라메트릭 서치) 예산이 맞는지 확인하는 방법은 다음과 같다. 예산요청값vs예산값 비교 후, 예산요청값이 예산값보다 작으면 전자,크면 후자를 배정한 값을 모두 더한다. 이 ..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net SOLUTION CODE # PYTHON from collections import deque dy = (0, 1, 0, -1) dx = (1, 0 ,-1, 0) N,M = map(int,input().split()) board = [input() for _ in range(N)] # String으로 받음 def is_valid_coord(y,x): return 0

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 SOLUTION CODE # PYTHON import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline # input많을시. N, M = map(int, input().split()) adj = [[0] * N for _ in range(N)] for _ in range(M): ..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 테이프를 최소로 쓰기 위해선 어떻게 해야할까? 바로 구멍난 곳들을 왼쪽 기준으로 차례로 붙여나가면 된다. SOLUTION CODE # PYTHON 1) 좌표로 풀기 N,L = map(int,input().split()) coord = [False] * 1001 for i in map(int,input().split()): coord[i]=True ans = 0 x = 0 while..

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net SOLUTION CODE # PYTHON 1) Combination from itertools import combinations # arr=[] # for i in range(9): # arr.append(int(input())) heights = [int(input()) for _ in range(9)] for combi in combinations(heights,7): if sum(combi)==10..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 해당문제는 파이썬의 경우 튜플과 최소힙/최대힙을 따로 두는 형식으로 풀 수있었으며 C++은 후자의 방식으로 풀었다. 파이썬 튜플의 경우 정렬시 맨앞의 값을 기준으로정렬해나가며,값이같다면 뒤의 값으로 정렬을 이어나간다. 헷갈리지말자.파이썬은 최소힙이 기본이며,C++은 최대힙을 기본으로 지원한다! SOLUTION CODE # PYTHON 1) 튜플 이용 import heapq a..