Algorithm/Python30 [Python] 백준 - 2220번 힙 정렬(DP) ◈ 오류 정정 및 피드백 환영 2220번: 힙 정렬 힙은 자료의 추가, 우선순위가 제일 높은 자료의 삭제가 가능한 자료구조이다. 이와 같은 힙에는 두 종류가 있는데, 각각 최소-힙, 최대-힙이다. 이 문제에서는 최대-힙을 다루기로 하자. 이와 같 www.acmicpc.net 🔎문제 분석 예제를 직접 그려보면 금방 알겠지만 n=6일 때 출력되는 힙을 만들기 위해서는 n=5일 때 출력되는 힙이 필요하다. 즉, 힙을 만드는 과정이 반복되므로 DP로 접근하면 되며, Bottom-Up으로 구현하면 된다. Bottom-Up으로 흐름을 따라가 보면 규칙은 다음과 같다. i=2에서 시작 root 노드가 1인지 확인 If no, 부모 노드가 1보다 클 경우 swap하는 과정을 root 노드가 1이 될 때까지 반복 If .. 2022. 2. 20. [Python] 알고리즘 - 트리 순회(전위 순회 vs 중위 순회 vs 후위 순회) ◈ 오류 정정 및 피드백 환영 📌개념 부모 노드(A)와 왼쪽 자식 노드(B), 오른쪽 자식 노드(C)가 주어졌을 때 트리 순회는 방문 순서에 따라 3종류로 나뉜다. 전위 순회(preorder) - 부모(A) → 왼쪽(B) → 오른쪽(C) 중위 순회(inorder) - 왼쪽(B) → 부모(A) → 오른쪽(C) 후위 순회(postorder) - 왼쪽(B) → 오른쪽(C) → 부모(A) 위와 같은 3가지 트리 순회는 DFS로 구현이 가능하다. 🔎구현 class Node: def __init__(self, node): self.left = None self.right = None self.node = node def preorder(root): if root: print(root.node, end = ' '),.. 2022. 2. 19. [Python] 백준 - 2178번 미로 탐색(BFS) ◈ 오류 정정 및 피드백 환영 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 🔎문제 분석 최소의 칸 수 즉, 최단 거리를 찾는 문제이니 BFS로 접근하면 된다. DFS - 처음부터 끝까지 이동한 뒤에 또 다른 경로를 탐색 BFS - 1칸으로 갈 수 있는 방향을 모두 탐색하고 또 1칸 이동해서 탐색 큐(queue)에는 이동한 칸의 좌표를 저장하면 된다. 우선 특정 좌표 (x, y)를 기준으로 위 그림과 같이 상우좌하 순으로 움직이면 좌표는 다음과 같다. (x-1, y) → (x, y+1) → (x+1, y) → (x, y-1) dx = [-.. 2022. 2. 18. 이전 1 2 3 4 다음
