알고리즘 풀이(Problem Solving) 검색 결과

해당 글 150건

알고리즘 풀이 - 백준 13549(숨바꼭질3, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 0부터 100,000 중 수빈이가 걷거나 순간이동으로 매초 -1, 1, x2 만큼 움직일 수 있을 때, 동생의 위치에 도달하는 가장 빠른 시간의 경우의 시간 구하는 문제(x2 이동 시에는 0초 소요) 2. 풀이 이 문제는 이전의 문제(여기)와 비슷한데 x2로 이동 시에는 0초가 소요된다. 따라서, 이전과는 조금 다른 접근이 필요하다. 이 문제를 해결할 규칙은 다음과 같다. ① x2 이동을 하게 되는 경우가 0초가 소요되므로 + 방향으로 이동하는 다른 경우 보다는 무조건 우선해서 탐색 해야 한다. ② +1 이동..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 16. 20:02

알고리즘 풀이 - 백준 14226(이모티콘, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 이모티콘을 복사, 붙여넣기, 1개 삭제가 가능할 때, S개의 이모티콘이 화면에 나타나는데 필요한 최소 시간을 구하는 문제 2. 풀이 이모티콘이 화면에 N개가 주어지게 할 때 실행하는 연산의 최소 경우를 구하는 문제이다. 각 연산 마다 1초가 소요되므로 연산의 수는 시간과 동일하다. 이모티콘은 2가지의 경우가 있다. ① 화면에 출력된 이모티콘의 수 ② 클립보드에 복사된 이모티콘의 수 그러므로, 현재 상태값을 저장할 배열은 2차원으로 구성하여 화면 출력된 수와 복사된 이모티콘의 수를 저장하며 탐색을 수행하면 된다..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 16. 19:49

알고리즘 풀이 - 백준 13913(숨바꼭질 4, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 0부터 100,000 중 수빈이가 걷거나 순간이동으로 매초 -1, 1, x2 만큼 움직일 수 있을 때, 동생의 위치에 도달하는 가장 빠른 시간의 경우의 시간 구하는 문제 그리고 출력 시, 가장 빠르게 이동하는 경우의 이동 경로 또한 출력해야 하는 문제 2. 풀이 그래프 탐색(BFS) 방식으로 매우 간단하게 풀 수 있는 문제이다. BFS를 사용하는 이유는 가중치가 1일 때, 최소 비용(시간)의 경우를 보장하는 탐색 방식이기 때문이다. 현재 가중치는 시간이며, 모든 경우에 가중치는 1이 된다. 현재 정점에서 이동..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 16. 19:26

알고리즘 풀이 - 백준1697(숨바꼭질, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 0부터 100,000 중 수빈이가 걷거나 순간이동으로 매초 -1, 1, x2 만큼 움직일 수 있을 때, 동생의 위치에 도달하는 가장 빠른 시간의 경우의 시간 구하는 문제 2. 풀이 그래프 탐색(BFS) 방식으로 매우 간단하게 풀 수 있는 문제이다. BFS를 사용하는 이유는 가중치가 1일 때, 최소 비용(시간)의 경우를 보장하는 탐색 방식이기 때문이다. 현재 가중치는 시간이며, 모든 경우에 가중치는 1이 된다. 현재 정점에서 이동 가능한 경우인 +1, -1, x2의 경우를 모두 체크한 뒤 탐색을 시작하여 해당 ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 15. 21:21

알고리즘 풀이 - 백준 2146(다리 만들기, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 섬과 섬을 가장 짧은 다리로 잇는 경우 다리의 길이를 구하는 문제 2. 풀이 이 문제는 그래프 탐색 중 난이도가 좀 있는 문제이다. 일반적으로 가장 간단히 생각해볼 수 있는 해결책은 다음과 같다. ⑴ 각각의 섬을 다른 번호로 저장한다. ⑵ 각 섬의 모든 위치에서 BFS 탐색을 시작하여 다른 번호의 섬에 가장 먼저 도달하는 경우를 정답으로 한다. 그런데 위의 방법으로 하면 문제를 풀 수 없다. 왜냐하면, 지도의 크기가 최대 100이라고 할 때, 100x100=10,000의 크기의 지도가 될 수 있는데, 이 때 ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 15. 21:17

알고리즘 풀이 - 백준 16964(DFS 스페셜 저지, 그래프(DFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 주어진 순서가 DFS로 풀 수 있는 것인지 확인하는 문제 2. 풀이 이전 포스팅(여기) 에서 주어진 순서가 BFS로 탐색이 가능한지를 풀어보는 문제를 진행했었다. BFS에서는 2가지의 방법으로 풀었지만 여기서는 그 2가지 중 ②번 방법만 사용한다. DFS는 특성상 ①의 방법을 사용하기가 어렵다.(사실 가능한지조차 모르겠다.) 따라서 ②번 방법을 쓴다. ②번 방법은 현재 주어진 값을 기반으로 그래프를 정렬한 뒤 단순히 DFS 탐색을 수행하는 방법이다. 그래프 탐색은 기본적으로 현재 정점에 연결된 정점의 순서를 ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 15. 20:39

알고리즘 풀이 - 백준 16940(BFS 스페셜 저지, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 주어진 순서가 BFS로 탐색 가능한 순서인지 알아보는 문제 2. 풀이 주어진 순서가 BFS로 탐색 가능한 경우의 수인지 판단하는 방법은 2가지가 있다. ① 현재 탐색 중인 정점에 연결된 정점의 부모 정점을 현재 정점으로 두고 다음 탐색할 정점의 부모 정점이 현재 탐색 중인 정점인 경우에만 가능한 경우라고 판정 ② 주어진 순서를 기반으로 그래프에 정점을 저장 후, BFS 탐색 시, 같은 결과가 나오는 경우에만 가능한 경우로 판정 ①의 경우는 아래의 그림을 통해 이해해보자. 위 그림을 통해 이해할 수 있는 정보는..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 15. 20:28

알고리즘 풀이 - 백준 16947(서울 지하철 2호선, 그래프(DFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 순환선과 지선으로 이루어진 지하철 노선이 있을 때, 각 역에서 순환선 사이의 거리를 구하는 문제 2. 풀이 이 문제는 그래프의 탐색을 이용하여 순환(Cycle)이 발생하는 지를 인지하고 해당 순환(Cycle)이 발생하는 지점을 모두 찾은 후, 다른 정점들에서 해당 Cycle로의 거리를 구하는 문제이다. 기본적으로 지하철 역사간의 연결은 양방향으로 연결되기 때문에 사실상 무방향 그래프로 구현이 된다. 무방향 그래프의 경우에 순환(Cycle)을 찾은 뒤 거리를 계산하면 된다. 무방향 그래프에서 순환(Cycle)을..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 3. 15. 18:46