Algorithm
-
[알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)Algorithm 2020. 12. 11. 19:13
너비 우선 탐색 (BFS, Breadth-First Search)는 그래프 탐색 방법 중 한 정점에서 시작하여 모든 정점을 탐색하기 위한 방법이다. 너비 우선 탐색은 현재 위치를 기준으로 사방으로 퍼져나가면서 탐색하는 방법으로, 인접한 정점들을 먼저 탐색한 후에 차례로 탐색을 진행한다. 장점 모든 가중치가 동일할 때, 시작 정점으로 부터 목표까지 최단 경로를 보장한다. 단점 정점의 수가 늘어날 수록 탐색에 불필요한 정점을 저장해야 하기 때문에 저장공간이 비교적 많이 필요하다. 주로 두 정점 사이의 최단 경로나 임의의 경로를 찾을 때 사용한다. 점점 탐색 범위를 확장하며 탐색하기 때문에 처음 발견하는 경로가 최단 경로가 된다. 주의할 점은 DFS와 마찬가지로 방문 체크가 필요하다. 그림으로 이해하면 쉽기 ..
-
[알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)Algorithm 2020. 12. 10. 18:48
깊이 우선 탐색 (DFS, Depth-First Search)는 그래프 탐색 방법 중 한 정점에서 시작하여 모든 정점을 탐색하기 위한 방법이다. 깊이 우선 탐색은 간단하게 "한쪽 방향으로 파고들어 탐색하는 방식"으로 미로에서 길을 찾는 것과 같다. 시작점으로부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다. 장점 현 경로상의 노드만 저장하면 되기 때문에 그래프 높이 만큼의 저장공간을 필요로 한다. 즉, 최대저장공간의 수요가 비교적 적다. 목표가 위한 깊이가 깊을 경우 해를 빠르게 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 수 있다. 목표에 이르는 경로가 다수인 경우, 목표에 닿으면 팀색을 끝내기 때문에 최적의 해가 아닐 수 있다. 주로 모든 경로를 탐색해야하거나, 경로 탐색에 조건이 ..
-
[백준 - JAVA] 치킨 배달Algorithm 2020. 12. 9. 17:37
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제를 풀기 시작하자마자 치킨이 먹고 싶어져서, 스터디원들과 30분만에 풀고 다같이 치맥을 먹으러 갔던 문제 ◝(⁰▿⁰)◜ M이 13이하의 수이기 때문에 기초적인 조합을 구현할 수 있다면 풀 수 있다! 풀이 방법 입력을 받으면서, 치킨집과 집의 좌표를 리스트에 각각 저장한다. 치킨집의 리스트로 dfs를 이용한 조합을 구현한다. boolean형 배열을 이용해서 중복 처리를 한다. 치킨집을 M개 골랐을 때 도시의 치킨거리를 구한다. M개의 치킨집..
-
[백준 3109 - JAVA] 빵집Algorithm 2020. 11. 26. 11:40
3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 스터디 과제로 나왔지만, 예전에 풀었던 문제라서 코드를 보면서 복기만 해봤다. dfs를 이용했고, 모든 시작점에서 출발하여 파이프를 연결할 수 있을 경우 계속 진행하는 백트래킹 방식으로 풀었다. 풀이 방법 행의 수 만큼 dfs를 시작한다. 오른쪽위, 오른쪽, 오른쪽 아래로 이동하며 범위안이며 건물이 아닐 경우에만 dfs를 진행한다. 열의 끝에 도달한 경우 ans를 증가시킨다. import java.io.*; import java.util.*; public class Main {..
-
[백준 13459 - JAVA] 구슬 탈출Algorithm 2020. 11. 17. 18:20
13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 보드를 기울이면 구슬이 끝까지 이동하는데, 구슬이 겹치는 상황에서 어떤 구슬이 앞쪽에 있는지만 신경쓰면 크게 어렵지 않은 문제! 풀이 방법 빨간 구슬의 위치와 파란 구슬의 위치를 갖고 있는 클래스를 구현한다. (1차원 배열로 해도 될것 같다.) 네 방향으로 기울여서 이동한 위치를 확인한다. move 메소드에서 처음 빨간 구슬의 위치가 앞인지 먼저 체크를 해준다. 빨간 구슬과 파란 구슬을 벽이 나올때까지 혹은 구멍에 ..
-
[백준 11062 - JAVA] 카드 게임Algorithm 2020. 11. 12. 18:32
11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 정말정말 DP는 풀 때마다 모르겠다! 결국 블로그를 참고해서 어떻게 푸는지 보고 풀었다. 최선의 전략으로 진행하는 것이기 때문에 모든 경우를 확인해야하고, DP를 이용해 각 턴마다 근우가 높은 점수를 얻는 경우와 명우가 낮은 점수를 얻는 경우를 저장해둔다. 그래서 DP배열은 [근우와 명우의 턴][시작 카드(왼쪽 끝)의 인덱스][마지막 카드(오른쪽 끝)의 인덱스]로 크기는 [2][N][N]으로 할당한다! 풀이 방법 DP배열의 초기값을 -1로 넣어준다. 턴은 근우부터 0..
-
[백준 4386 - JAVA] 별자리 만들기Algorithm 2020. 11. 12. 17:52
4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 기본적인 MST (최소스패닝트리) 문제! 나는 입력을 잘 못 받아두고 왜 안되냐고 고통받다가 나중에 발견했다 :( 프림이나 크루스칼 둘 중에 한가지를 사용해서 풀 수 있는데, 나는 프림을 사용해서 풀었다. 크루스칼은 union, findSet을 구현하기가 너무 귀찮았다 =(:з」∠)_ 풀이 방법 입력받은 좌표를 이용해 다른 별과의 거리를 구한다. 첫번째 별부터 시작! 다른 별들의 번호와 첫번째별과의 거리를 Edge 객체로 만들어 PQ에 넣는다. 방문한 별의 개수(..
-
[백준 1937 - JAVA] 욕심쟁이판다Algorithm 2020. 11. 9. 19:28
1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 현재 장소보다 대나무가 많은 지역으로만 이동할 수 있는 판다가 가장 오래 살아남는 기간을 구하는 문제! 단순하게 dfs로 풀었다가 시간초과를 받았다. DP라고해서 고민을 하다가 결국 블로그를 참조했다. 기간을 정해서 DP문제를 집중적으로 푸는 시간을 가져야 할 것 같다... ŏ̥̥̥̥םŏ̥̥̥̥ 풀이 방법 dfs를 통해 끝에 도달했을 때 그곳의 cnt(살아남은 날짜)는 1이 된다. * 더 이상 이동하지 못하기 때문에 그곳에서는 하루만 살 수 있다. 그리..