본문 바로가기

Algorithm283

[그래프 탐색] DFS와 BFS의 차이점 기본적으로 DFS와 BFS의 개념을 알고, 코딩이 가능하다는 전제하에 작성한 내용입니다. 면접 때 "DFS와 BFS의 차이점에 대해 말씀해주세요"라는 질문을 받은 적이 있습니다. 어떻게 동작하는지 알고, 코딩도 가능한데 막상 어떻게 말할 지 준비하지 않으면 대답하기 어려운 질문입니다. 그러니 얕게, 깊게 탐색한다는 말은 제외하고 어떻게 말하면 좋을 지 생각해보았습니다. 링크: www.notion.so/DFS-BFS-7fda36b13f594ac89d5687eea96c8daa 잘못된 내용이 있거나 더 나은 표현이 있다면 피드백 주시면 감사하겠습니다. :) 2020. 7. 31.
[코딩테스트 연습] 여행 경로 문제: https://programmers.co.kr/learn/courses/30/lessons/43164 DFS 문제입니다. DDijkstra님의 풀이를 통해 해결했습니다. (https://devje8.tistory.com/) 사전순으로 가장 빠른 경로를 리턴하기 위해 티켓을 '도착지' 기준으로 오름차순 정렬합니다. 티켓을 오름차순 정렬 했으므로 ticketList[N]과 ticketList[N+1]의 출발점 공항이 동일하면 ticketList[N]의 도착지 공항이 ticketList[N+1] 도착지 공항보다 알파벳 순서가 앞섭니다. 그러므로 for (int index = 0; index < ticketList.size; ++index) 으로 DFS 탐색해도 사전순 탐색이 보장됩니다. 주어진 티켓을 .. 2020. 7. 31.
[BOJ]9019번: DSLR 문제: https://www.acmicpc.net/problem/9019 BFS 문제입니다. 숫자로 처리하지 않고 문자열로 처리하다가 시간초과가 났습니다. 숫자 처리하는 방법은 jaimemin님 블로그 포스팅을 참고하였습니다. (https://jaimemin.tistory.com/654) 시간초과가 난다면, 문자열로 처리하는 부분을 숫자로 바꿔주면 될 것입니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ9019.cc 2020. 7. 30.
[BOJ]1162번: 도로포장 문제: https://www.acmicpc.net/problem/1162 JusticeHui님이 푸신 솔루션을 참고하여 해결하였습니다. (출처: https://justicehui.github.io/usaco/2019/07/12/BOJ1162/) 도로 포장에 대한 정보를 어떻게 나타내느냐가 중요한 문제입니다. 이 문제의 경우 다익스트라의 결과값인 dist[N]을 다음과 같이 응용해서 정의할 수 있습니다. dist[N][K]: 출발점 1번 도시에서 N번 도시까지 갈 때, K개의 도로를 포장해서 가는 최단거리. 이 때 저희가 원하는 정답 값은 아래와 같습니다. answer = min(dist[N][0],dist[N][1],dist[N][2],dist[N][3],dist[N][4],...,dist[N][K]) .. 2020. 7. 29.

티스토리툴바