HwangHub

문제 해석 위 문제는 람다를 활용한 정렬 문제이다. 간단하므로 풀이는 생략하겠다. 풀이 코드 첫 번째 시도 : 정답 import sys input = sys.stdin.readline n = int(input()) members = [] for _ in range(n): age, name = input().split() age = int(age) members.append((age, name)) members.sort(key=lambda x: x[0]) for member in members: print(*member)

문제 해석 처음에는 하노이 이동 횟수를 구하기 위해 DP를 사용하였다. 점화식을 세워보니 이전 결과를 계속 사용한다 느껴서 DP가 적절할 것이라고 생각한 게 문제였다. 실제 정답을 얻을 수 있었던 코드는 하노이의 탑을 이해한 채로, 단순 구현으로 접근하면 풀 수 있었다..! 교훈 : 문제 풀이를 위한 알고리즘을 선택할 땐 신중하게 따져보자... DP는 누적되는 값을 사용한다 하더라도, 일회성으로 값을 구할땐 비효율적이다! 풀이 코드 첫 번째 시도 : 메모리 초과 import sys input = sys.stdin.readline def hanoi_res(n): if n

풀이 코드 문제가 너무 쉽지만 시험기간 이후 다시 알고리즘을 풀기 시작한거라, 기억이나 되짚을 겸 그냥 풀었다. 푼 김에 기록한다. import sys input = sys.stdin.readline li = list(input().rstrip()) li.sort(reverse=True) print(''.join(li))

문제 해석 이 문제는 단순히 생각하면 최대 합을 나타내는 경우의 수 또는 조합을 구하는 문제이다. 단순하게 우선 브루트포스가 가능한지 보기 위해서는 시간복잡도를 분석해보면 되는데, n개의 칸을 선택하는지 여부에 따라 대략적으로 O(2^n)이 될 것으로 보인다. 따라서 경우의 수를 뽑는다던지 하는 방식으로는 접근하기 어려울 것으로 보았다. 이 문제는 대표적으로 DP를 적용하는 문제이다. 다이나믹 프로그래밍은 대개 이전 데이터를 이후에 계속 사용하는 방식에서, 이를 효율적으로 다루기 위해 사용된다. 재귀 방식에도 적용할 수 있고, 이처럼 문제 해석상 앞에서 적용한 데이터를 계속 사용하는 경우에 적용 가능하다. DP는 일반적으로 top-down 방식 또는 bottom-up 방식으로 적용되는데, 해당 문제에서는..

백준 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..