Algorithm14 [백준]1504. 특정한 최단 경로 1504. 특정한 최단 경로 개요 - 이 문제는 가중치가 있는 그래프의 최소 경로를 찾는 문제로 다익스트라 알고리즘을 이용하는 문제이다. - 다만 특이하게 반드시 거쳐야할 정점의 번호가 주어진다. 어렵게 생각하지않고 각 정점을 들르면서 목적지까지 갈 경로들의 가중치 중에서 최소값을 구하는 방법으로 문제를 해결했다. 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 .. 2022. 3. 18. [백준]13549. 숨바꼭질3 13549. 숨바꼭질3 개요 - 이 문제는 가중치가 있는 그래프의 최소 경로를 찾는 문제로 다익스트라 알고리즘을 이용하여 해결했다. - 우선순위 큐를 사용해서 알고리즘을 구현했고, 이 과정에서 Comparable Interface를 활용하는 방법을 공부했다. 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후.. 2022. 3. 17. [기본 개념] 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘(Dijkstra Algorithm) 개요 - 최소 경로를 찾는 다익스트라 알고리즘의 개념을 알아본다. - 사용하는 경우와 사용하지 못하는 경우를 알아보고, 최소 경로 결과를 도출하는 과정을 살펴본다. 기본 개념 - 그래프의 간선에 가중치가 주어졌을때 출발 노드에서 목적지 노드까지 도달하는 최소비용을 찾는 알고리즘이다. - 다익스트라 알고리즘을 이용하면 출발지에서 모든 노드까지의 최소 도달 비용을 알 수 있다. 따라서 목적지까지의 최소비용도 함께 알 수 있다. - 다음은 다익스트라 알고리즘으로 최소 비용을 찾는 과정이다. 최소 비용을 찾는 과정( 다익스트라 알고리즘 이용 ) 0. 모든 노드의 최소 가중치를 찾기 위해서 다음과 같이 세 변수가 필요하다. - 각 노드의 방문 여부 (모든 노.. 2022. 3. 12. [백준]5446. 용량 부족 5446. 용량 부족 개요 - 이 문제는 트라이 자료구조에 단어들(삭제해야할 단어)를 넣어서 활용하는 문제이다. - 기본적인 트라이 구조에서 삭제하면 안되는 단어 표시 구분자를 추가하여 문제를 해결했다. 문제 팀포2 덕후 연수는 팀포2를 다운받던 도중 하드 용량이 부족하다는 것을 알았다. 이때는 침착하게 팀포2를 하지 말거나 하드를 새로 사면 되지만 불가능했고, 결국 하드에서 쓸모없는 파일을 지워야만 한다. 연수는 또한 턱스 덕후여서 리눅스를 사용중이다. 리눅스에서 현재 디렉토리의 특정 파일을 지우려면 "rm 파일명"의 형식을 갖춰 명령하면 된다. 그러나 파일 개수가 너무 많을 경우 일일이 다 칠 수 없기에, 와일드카드 '*'를 사용할 수도 있다. "rm 문자열*" 형식으로 명령하면 현재 디렉토리에서 파.. 2022. 3. 10. 이전 1 2 3 4 다음
