HwangHub

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 해석 : 노드의 관계를 묻고 있으니 그래프 문제이고, 모든 노드가 연결되어 있으면 되므로 깊이가 5가 되면 된다. (1부터 시작) """ 사람 수 N : 5

2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 첫 번째 시도 # 부모와 자식 : 1촌 # 사람들은 1, 2, 3, ... , n (1

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