자율주행 미래를 위한 대학원생

지난 포스팅에서 그리디 알고리즘에 대해 간단히 살펴보고, 가벼운 문제를 살펴보았다. 이를 백준에서 유사한 문제를 가져와 풀어보았다. 거의 동일한 문제기에 이것외에도 추가적으로 풀어볼 계획이다. 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다. 출력 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오. ..

이번에는 저번 포스팅에서 DFS와 BFS를 간단하게 살펴보고 구현까지 해보았다. 그래서 이를 응용을 어떻게 하는지 살펴보기 위해 백준의 'DFS와 BFS' 문제(1260)를 풀어보았다. 구현은 재귀함수 형태로 구현을 했다. 우선 문제를 살펴보자. 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 ..

BFS/DFS 내년 상반기 현대자동차 코딩테스트 준비를 위해 알고리즘을 하나씩 공부해나갈 계획이다. 시작으로 데이터 구조론 수업에서 들었던 DFS와BFS를 알아보고 이를 구현하는 코드를 작성해보도록 하자. DFS(깊이 우선 탐색, Depth First Search)란? 깊이 우선 탐색이라는 말과 같이 상위 노드에서 왼쪽 부터 차례대로 점점 하위 노드로 내려가며 탐색하는 방법이다. 위 예시에서 쉽게 확인할 수 있듯이, 전체를 보기 보다는 깊이를 탐색한다고 볼 수 있다. 자점으로는 비교적 저장 공간에 대한 수요가 적다. BFS(너비 우선 탐색)에 비해 비교적 간단하지만, 속도면에서 느리다는 단점이 있다. 깊이가 매우 깊을 경우, 해를 찾을 수 없거나 Global Minima가 아닌 Local Minima를 ..