반응형 Algorithm10 [Algorithm] BFS BFS BFS는 Breadth First Search, '너비 우선 탐색'이라는 의미를 가진다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다고 했는데, BFS는 그 반대다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행할 수 있게 된다. BFS 알고리즘의 정확한 동작 방식은 다음과 같다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다. 3. 2번 과정.. 2021. 1. 8. [Algorithm] DFS 탐색(Search): 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 DFS/BFS는 대표적인 탐색 알고리즘이다. DFS DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 다음 그림을 보자. step 1. 시작 노드 '0'을 스택에 삽입하고 방문 처리 한다. .. 2021. 1. 8. [Algorithm] 멀티탭 스케줄링 (백준 1931) 소스코드 Github : github.com/minkwns/CodingTestStudy/tree/main/greedy/JunhyoungPark/%EB%A9%80%ED%8B%B0%ED%83%AD%20%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81 처음에 코드 짤 때 기능 목록을 작성하지 않고 바로 개발에 돌입했다. 내가 만든 테스트 케이스는 맞다고 나와서 오류를 찾지 못했고, 구글링의 힘을 조금 빌려 기능 목록부터 다시 짜보았다. 기능 목록 - 멀티탭 홀을 초기화 - 멀티탭에 이름이 존재할 때 - 멀티탭에 이름이 존재하지 않지만 빈 공간이 있을 때 - 멀티탭에 빈 공간이 없을 때 - 이후 nameList에 이름이 존재하지 않을 때 - 이후 nameList에 이름이 존재할 때, swap 할.. 2021. 1. 7. [Algorithm] Greedy Algorithm (그리디 알고리즘) 그리디(Greedy) 알고리즘은 '당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘'이다. 그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있다. 또한 '특정한 상황'에 있어서는 그리디 알고리즘이 최적의 해를 보장할 수도 있다. 그리디 알고리즘의 대표적인 예는 거스름 돈 문제이다. 853원의 거스름돈을 주어야 할 때 1원짜리 853개를 주는 것보다 500원 1개, 100원 3개, 50원 1개, 1원 3개를 주는 것이 더 효율적이다. 따라서 이런 경우 '무조건 더 큰 화폐 단위부터 거슬러 준다'는 알고리즘을 사용하면 최적의 해를 보장할 수 있다. 그리디 알고리즘은 무조건 큰 경우, 작은 경우, 긴 경우, 짧은 경우와 같이 극단.. 2021. 1. 4. 이전 1 2 다음 반응형
