알고리즘28 DFS와 BFS DFS(깊이 우선 탐색) -> **스택(혹은 재귀)** 구현 **스택**에 시작 노드를 넣는다 스택이 비어있으면 실행을 멈추고 False 반환 스택의 맨 위 노드가 찾고자 하는 노드라면 탐색을 종료하고 True 반환 3에서 스택의 맨 위 노드가 찾고자 하는 노드가 아니라면 해당 노드를 POP. 스택에 들어온 적이 없는 POP한 노드의 모든 이웃 노드를 찾아 순서대로 스택에 넣는다 3으로 돌아간다 DFS(G,u) u.visited = ture for each v ∈ G.Adj[u] if v.visited == false DFS(G, v) init() For each u ∈ G u.visited = false For each u ∈ G DFS(G, u) 장점 현 경로상의 노드를 기억하기 때문에 적은 메모리 .. 2022. 3. 27. 정렬 [정렬] 버블 정렬 두 인접한 데이터를 비교해 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 총 라운드 = **배열크기 - 1** 각 라운드별 비교 횟수 = **배열 크기 - 라운드 횟수**  https://en.wikipedia.org/wiki/Bubble_sort public class Bubble_Sort{ public static void bubble_sort(int[] a){ bubble_sort(a, a.length); } private static void bubble_sort(int[] a, int size).. 2022. 3. 4. [백준]11047번-동전 0 동전의 개수가 N개 주어지고 N 개의 동전을 적절히 사용해 합을 K로 만든다. 이때, 필요한 동전의 최소값을 구하여라 #값 입력 n, k = map(int, input().split()) #coin_list = list() #for i in range(n): # coin_list.append(int(input())) coin_list=[int(input()) for _ in range(n)] #코인 총 개수 입력 변수 count = 0 #큰 값을 가진 것부터 나누어 구하기 위해 coin_list.sort(reverse=True) for i in coin_list: if k == 0: break #남은 돈이 없을 경우 break count +=k//i k%=i print(count) 2021. 7. 21. 그리디 알고리즘 그리디 알고리즘 '매 선택에서 현재 당장의 최적인 답' 백트래킹을 통해 추가 점검을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능 경우는 검증하지 않는다  전체에서 최적 값을 언제나 구할 수 없다는 단점 최초 선택에서 최적의 선택을 통해 **부분 최적해는 구했지만** **전체 문제에서는 최적값을 구하지 못함** 최적해를 가지기 위해 다음 두 조건을 만족해야 한다 탐욕 선택 속성(Greedy Choice Property) 이전에 선택이 이후에 영향을 주지 않음을 의미 최적 부분 구조(Optimal Substructure) 부분 문제의 최.. 2021. 7. 21. 이전 1 2 3 4 ··· 7 다음
