Computer Science/Algorithm2 [이것이 코딩테스트다] Greedy 알고리즘 * 이것이 코딩테스트다 책을 읽은 후 기억하고 싶은 내용을 정리한 글입니다. 그리디 알고리즘 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘이다. 코딩 테스트에서는 '최적의 해'를 찾는 문제가 출제되기 때문에 그리디 알고리즘의 정당성을 고민해봐야 한다. 거스름돈 문제, 1이 될 때까지 문제가 전형적인 그리디 알고리즘 문제이다. 다익스트라, 크루스칼 알고리즘도 그리디 유형에 해당. [문제 3] 숫자 카드 게임 숫자 카드 게임은 여러 개의 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 게임의 룰은 다음과 같다. 1. 숫자가 쓰인 카드들이 N * M 형태로 놓여 있다. (N: 행, M: 열) 2. 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 3. 선택된 행에 포함된 카드들 중.. 2022. 7. 9. [Algorithm] BFS/DFS 정리 너비 우선 탐색(BFS, Breadth-First Search) - BFS 루트 노드의 자식 노드들을 먼저 방문한 후, 방문했던 자식노드들을 기준으로 해당 노드의 자식노드들을 차례로 방문하는 방식 시작 정점으로부터 방문 가능한 가까운 정점들을 먼저 방문하는 것이다. 인전합 노드들을 탐색 후, 차례로 다시 너비우선탐색을 진행 => 선입선출 형태의 자료구조 큐이용 - 탐색 방법 1. 시작하는 칸을 큐에 넣고 방문표시 2. 큐가 빌때까지 아래의 과정을 반복 1) 원소를 꺼낸다. 2) 꺼낸 정점의 인접한 정점 탐색 3) 인접한 정점이 방문했던 적이 없다면, 방문 표시를 남긴 후 해당 칸을 큐에 넣는다. - 시간 복잡도 칸이 N개일 때: O(N) , 행이 R, 열이 C 인 경우: O(RC) 깊이 우선 탐색(DFS.. 2022. 4. 23. 이전 1 다음