HwangHub

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 기본 개념 한국어도 직역한 단어지만, 영어로 트리 순회 개념을 이해해두고 넘어가면 쉽다. 트리 순회 개념은 root 노드를 언제 들르냐에 따라 나뉜다. preorder : 먼저 root부터 들르고 왼쪽자식 순회, 그리고 오른쪽 자식 순회 def preorder(root): if root != '.': print(root, end='') # root preorder(tree[root][0]) # left preorder(tree[root][1]) # r..

문제 해석 위 문제는 DP를 연습하기 좋은, 쉬운 DP 유형입니다. DP는 큰 문제를 유닛으로 쪼개어 풀어내고, 이를 활용하여 큰 문제의 답을 도출하는 문제 해결 기법입니다. 이 문제에서 타일을 계속 붙이는 경우의 수를 구하는데, 길이가 N인 타일을 만드는 경우의 수를 구하기 위해서는 N-2의 길이와 N-1의 길이일 때 어떻게 타일을 쌓는지를 알아냄으로써 N이 어떤 길이여도 답을 구할 수 있게 풀어낼 수 있습니다. N-2와 N-1로 경우를 나누는 이유는, 타일의 유형이 1x2, 2x1 두 개 뿐이기 때문입니다. N-2일 때에는 1x2로 두 개를 쌓는 경우만 생각하면 되고, N-1일 때에는 2x1을 쌓는 경우만 생각하면 됩니다. N-2일 때 2x1을 두 개 쌓는 경우도 고려해야 하는 것이 아니냐 생각하실 ..

문제 해석 위 문제는 N개의 수가 주어질 때, 해당 수들이 일직선 상에서 왼쪽부터 "몇 번째" 숫자인지만 출력해주면 되는 문제다. 즉, 중복된 숫자의 개수는 고려하지 않아도 된다.(ㅎㅎ) 풀이 코드 첫 번째 생각 문제를 잘못 이해하고 짠 코드이다. 아래 코드는 예제 2를 3 0 3 0 3 0 으로 출력한다. 당연히 중복된 숫자가 나온 뒤에는 accumulative value를 계산해줘야 한다고 생각했는데, 그렇게 하면 예제 2에서 3 0 3 0 3 0이 나오는 게 맞다. 그래서 고민하다가, "아, 그냥 동일 숫자는 동일 순번만 뽑아주고 넘어가는구나..."라고 이해했다. 코드 순서를 고려해서 기껏 구현해놨더니 내 생각보다는 더 단순한 문제였다. # N개의 수가 주어지고 : 1

문제 해석 이 문제는 리스트에서 가장 큰 수를 계속 찾아내어서 값을 빼주고, 이를 비교값에 반영해주면 되는 문제다. N과 M의 크기가 크지 않으므로 단순하게 떠오르는 로직을 구현하면 되는 문제이며, 이를 구현하는 방법을 아는지 묻는 문제인 것으로 보인다. 파이썬에는 최소 힙 이라는 우선순위 큐가 콜렉션으로 구현되어 있고, 이를 이용해 최대 힙으로 사용하여 문제를 풀어낼 수 있다. 문제 풀이 # 국회의원 후보 N명 (1

문제 해석 이 문제는 N이 500,000까지이므로 우선 2중 for문을 사용하지 않겠다고 유념하고 덤벼야 한다. 이를 적용하기 위해 딕셔너리를 활용하였다. 어려운 문제는 사실 아닌 것 같고, 다른 풀이도 존재할 수 있지만, 개인적으로 나쁘지 않게 푼 것 같다. 풀이 코드 시간복잡도를 고려하지 않은 풀이 import sys input = sys.stdin.readline K, L = map(int, input().split()) li = [] for _ in range(L): s = input() if s in li: idx = li.index(s) li.pop(idx) li.append(s) for i in range(K): print(li[i]) 여기서 pop()과 index()의 내부 구현 로직에 따..

첫 번째 풀이 : sort() 사용 -> 메모리 초과 풀릴 리 없는 줄은 알았지만, 그래도 바로 떠오르는 방법을 해 봐야 직성이 풀리는 스타일인지라 한번 해 봤습니다. import sys input = sys.stdin.readline t = int(input()) ans = [] for i in range(t): ans.append(int(input())) ans.sort(key=lambda x : x) for i in ans: print(i) 두 번째 풀이 : counting sort -> 메모리 초과 파이썬에서 사용하는 sort() 와 sorted() 메소드는 팀 정렬이라는 방식을 사용한다고 합니다. 이와 유사히 볼 수 있는 방식이 퀵 정렬이고, 정렬을 사용할 때 가장 일반적으로 많이 사용하는 방식..

문제 해석 위 문제는 람다를 활용한 정렬 문제이다. 간단하므로 풀이는 생략하겠다. 풀이 코드 첫 번째 시도 : 정답 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 방식으로 적용되는데, 해당 문제에서는..