HwangHub

백준 10870. 피보나치 수 풀이 1 : 일반 반복문 구현 import sys input = sys.stdin.readline n = int(input()) first = 0 second = 1 result = 0 if n == 0: print(first) elif n == 1: print(second) else: for i in range(n-1): result = (first + second) first = second second = result print(result) 풀이 2 : 재귀 n

문제 해석 스택에 우선순위와 location을 튜플로 묶어서 같이 저장하는 기법을 이용하면 훨씬 직관적이다. 하지만 이를 딕셔너리로 구현하고, 포인터를 옮기는 방식으로 구현해도 똑같지 않나? 아니다. 스택과 튜플을 같이 이용하는 방식과 딕셔너리를 사용하는 방식은 그 목적이 다르다. 기본적으로 key-value 매핑은 딕셔너리를 이용해도 무방하지만, 해당 로직에서는 조건을 만족하는 요소를 주기적으로 제거해줘야 한다. 따라서 이 문제에서는 stack + tuple 방식을 더 선호하고자 한다. 물론 딕셔너리로 구현할 수도 있을테지만, 더 쉽게 이해할 수 있는 방식으로 구현하는 것을 우선하자. esp, 여기선 popleft()를 활용해야 하니 스택이 아닌 덱을 적용하려고 한다. 풀이 코드 from collect..

문제 풀이 이 문제도 전형적인 스택 문제라고 느꼈다. 스택 문제들은 일반적으로 스택에 있는 것을 뽑아내서 기존에 주어진 리스트와 값을 비교, 조건에 맞으면 정답 리스트(ans)에 추가하고, 아니면 버리는 방식을 취한다. 이 문제에서는 더하여서, 정답 리스트를 0으로 초기화해서 탑에서 발사한 레이저가 막히지 않는 것을 기본으로 했다. n = int(input()) # 탑의 수 li = list(map(int, input().split())) # 탑의 높이 ans = [0] * (n) stack = [] for i in range(len(li)): while stack and li[stack[-1]] < li[i]: stack.pop() if stack: ans[i] = stack[-1] +1 else: a..

풀이 첫 번째 시도 n, k = map(int, input().split()) li = [i for i in input()] find_length = n - k tmp = li[:k] idx = tmp.index(max(tmp)) k -= idx li = li[idx:] targets = list() for i in range(len(li)-1): if not k: break if li[i] < li[i+1] : li.pop(i); k -= 1 # O(N^2) 발생 지점 print(''.join(map(str, li))) 위 풀이는 단순하게 문제를 바라본 경우 나올 수 있는 로직이고, 이는 시간복잡도를 고려하지 않은 풀이이다. 리스트의 pop() 연산을 수행하기 위해선 O(N)이 될 수 있음을 항상 유념..

문제 링크 문제 해석 처음에는 큐 문제일 거라고 생각했고, 사실 맞추고 보니까 큐 문제라고는 하는데, 나는 그냥 연결 리스트 개념으로 풀었다. 다만, 파이썬에서는 연결 리스트 pop() 을 기존에 C++로 구현한 것 처럼 참조변수가 갖는 주소값을 temp 등의 변수에 저장해놓고 중간 노드를 떼어내고 하는 작업이 없기 때문에 연결 리스트라고 인지되지 않을 수 있을 것 같다. 중간 지점을 뽑아낸다는 개념으로 연결 리스트라고 정의하고 시작하겠다. (== 파이썬 리스트와 .pop() 메소드를 활용했다.) 풀이 """ n, k 입력이 주어지면 기본적으로 li = [i for i in range(1,n+1)] 인 리스트가 있고, 이 리스트가 원으로 이루어져 있는 방식 루프를 걸고 idx += k idx = (idx..

백준 17298. 오큰수 첫 번째 시도 from collections import deque import sys input = sys.stdin.readline ans = [] t = int(input()) dq = deque((map(int, input().split()))) for i in range(t): cmp = dq.popleft() res = [] for elem in dq: if elem > cmp: res.append(elem) if len(res): ans.append(res[0]) else: ans.append(-1) print(*ans) 위 풀이로 접근하게 되면 O(N^2)이므로 시간 안에 문제를 풀 수 없다. 따라서 다른 풀이가 필요하다. 두 번째 시도 import sys inpu..

https://www.acmicpc.net/problem/21318 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 문제 해석 해당 문제는 구간을 주고, 그 구간 내에서 특정 조건을 만족하는 경우를 '세어' 달라고 했다. 만약 일반적인 경우처럼 크게 입력값을 받는 loop로 묶고, 그 안에서 입력받은 것에 따라 x부터 y까지 슬라이싱을 하고, 슬라이싱한 배열을 sum 함수로 돌린다면 시간복잡도가 O(Q*N*(y-x))이다. 최악의 경우 이미 0.5초를 훌쩍 넘겨 버리므로, 다른 방안을 고려해야 한다. 마침 ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 해석 해당 문제는 "넓은 탐색 범위에서 특정 숫자를 찾는 것"이므로 시간복잡도를 고려했을 때 이분탐색으로 풀어야 한다. 문제 풀이 첫 번째 시도 import sys input = sys.stdin.readline """real input""" n, m = map(int, input().split()) li = list(map(int, input().sp..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 해석 쉬운 이분탐색 문제이다. 만약 단순히 for loop과 in 연산자를 이용해서 탐색하려 한다면, 그 시간복잡도가 O(n^2)이고 M의 개수가 100,000이므로 1초는 가볍게 넘길 것이다. 따라서 단순히 모든 요소를 탐색하는 개념으로 접근해서는 안된다. 이러한 경우 절반씩 짤라서 탐색하는 이분탐색(Binary Search)를 이용하면 O(..

https://www.acmicpc.net/problem/13423 13423번: Three Dots 직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 www.acmicpc.net 문제 분석 우선 탐색을 해야 하는 문제이다. 이진 탐색에 대한 이야기해보면 필요 없는 범위에 대한 탐색을 막음으로서 탐색을 좀 더 빠르게 수행하는 방법이다. 보통 O(logN)을 갖는다. """(이진탐색) 첫 번째 풀이-시간초과""" t = int(input()) for i in range(t): n = int(input()) li = sorted(list(map(in..