본문 바로가기

Algorithms63

백준 1427. 소트인사이드 오늘은 간단한 문제라 다행히 첫트에 성공 ! 문제를 보자마자 문자열로 바꾸고, 각 char를 리스트에 넣은 후 거꾸로 정렬하면 되겠다는 생각을 했다. n = input for (int i=0; i 2022. 6. 7.
백준 2108. 통계학 def heapify(lst, idx, n): s_idx = idx l = idx * 2 r = idx * 2 + 1 if l lst[l]: s_idx = l if r lst[r]: s_idx = r if s_idx != idx: lst[s_idx], lst[idx] = lst[idx], lst[s_idx] return heapify(lst, s_idx, n) def heap_sort(lst): n = len(lst) lst = [0] + lst for i in range(n, 0, -1): heapify(lst, i, n) arr = [] for i in range(n, 0, -1): arr.append(lst[1]) lst[1], lst[i] = lst[i], lst[1] heapify(lst, 1,.. 2022. 6. 7.
백준 2750. 수 정렬하기1 https://www.acmicpc.net/problem/2750 시간 제한이 꽤 널널해서 복잡한 정렬을 사용할 필요 없이, 복잡도가 O(n^2)인 버블 정렬이나 삽입 정렬로 풀 수 있다. 개인적으로 버블 소트가 쉬워서 우선 버블 소트에 대한 Pseudo code를 작성하면 for (i=0; i array[j + 1]): array[j], array[j + 1] = array[j + 1], array[j] 가 된다. 최종 코드는 n = int(input()) lst=[] for i in range(n): lst.append(int(input())) for i in range(n): for j in range(n - i - 1): if lst[j] > lst[j + 1]: lst[j], lst[j + 1].. 2022. 6. 7.
BFS : 너비 우선 탐색 (Java) 너비 우선 탐색 또한 그래프 탐색 이론이다. 깊이 우선 탐색과의 차이점은, BFS는 현재 노드 기준 가장 가까운 노드들을 모두 거치고 지나간다. 특징으로는 1번, 재귀적으로 작동하지 않는다. 2번, 노드에 방문했던 사실을 체크해줘야 한다. 3번, 동일 깊이의 노드들을 선입선출을 기반으로 하는 큐에 넣어두었다가 사용한다. 이런 순서로! 엄밀히 말하면 같은 깊이의 노드들을 한 번에 처리하는 것은 아니지만. 똑같이 인접 행렬로 구현한다. 알고리즘을 정렬해보면: 1. 시작 노드의 번호를 큐에 넣는다. 2. 큐에 있는 노드를 꺼낸다. 3. 해당 노드와 연결되어 있는 노드들 중에 방문하지 않은 노드들을 큐에 넣는다. 4. 큐가 비어있지 않으면 2~4번을 반복한다. 코드로 한 번 구현해보자. import java.u.. 2021. 10. 7.

티스토리툴바