https://www.acmicpc.net/problem/20166 난이도 : 골드 4 알고리즘 유형 : DP, DFS, 문자열 풀이 시간 : 35분 문제 풀이 알파벳 소문자가 들어간 격자의 정보와 k개의 문자열이 주어졌을 때, 각 문자열마다 만들 수 있는 경우의 수를 출력하는 문제이다. 문제를 풀기에 앞서 제약 사항들이 주어진다. - 상하좌우 대각선 방향으로 한 칸씩 이동하여 문자열을 이어붙일 수 있다.- 이미 지나왔던 칸들을 다시 방문할 수 있다.- 격자의 좌표를 벗어난 경우, 반대편으로 이동한다. (ex. (1, 1)에서 위로 이동하면 (n, 1))- 중복된 문자열이 입력으로 주어질 수 있다. 해당 문제를 대략적으로 살펴봤을 땐, DFS 알고리즘을 사용해 가능한 경우의 수를 모두 찾아보는 방법이 있..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : DFS 풀이 시간 : 28분 문제 풀이 서로 다른 번호가 매겨진 등대 `n`개가 존재한다. 또한, 등대와 등대 사이를 오가는 뱃길이 `n - 1`개 존재하여 모든 등대는 서로 연결되어있다. 등대와 등대 사이를 오가는 뱃길을 밝히기 위해 양 등대 중 적어도 하나는 켜져있도록 등대를 켜 두어야 한다. 켜 두어야 하는 등대 개수의 최솟값을 return하자.문제에서 가장 중요시 되는 부분은 "두 정점 중 적어도 하나는 켜져있어야 된다"라는 점이다.위 예제를 살펴보면, 불이 켜진 노드에는 여러 자식노드가 있음을 확인할 수 ..

https://school.programmers.co.kr/learn/courses/30/lessons/92343  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : DFS, BFS 풀이 시간 : 43분 문제 풀이 이진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여있다. 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 한다. 만약 늑대를 만나면 늑대가 양을 따라다니게 되고, 늑대의 수가 양의 수보다 같거나 큰 경우 모든 양을 잡아먹는다. 최대한 많은 양을 모으자. 문제는 이진 트리 형식으로 되있고, DFS와 BFS 모두 사용가능하다. 다만, 이..

https://www.acmicpc.net/problem/1520 난이도 : 골드 3 알고리즘 유형 : DFS, DP 풀이 시간 : 33분 문제 풀이 $(0, 0)$ 부터 $(N - 1, M - 1)$까지 가기 위한 경우의 수를 구하자. 단, 이동 시에는 이전 높이보다 항상 낮은 곳으로만 이동해야 한다. 문제의 조건을 살펴본다면, $N, M ≤ 500$으로 주어졌고, 상하좌우로 이동이 가능하기 때문에, 모든 경우에 대해 살펴본다면 $O(4^{500})$으로 시간초과가 나게 된다. 따라서 우리는 DP 테이블을 활용하여 이전에 왔던 경우의수에 대해서 저장해주어야 한다. 먼저 grid 상에서 이동은 dfs 알고리즘을 사용해 진행하였다. 기본적인 틀은 4방향에 대해 탐색하면서, 현재 위치보다 새로운 위치가 낮은..

https://school.programmers.co.kr/learn/courses/30/lessons/150365# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : DFS, BFS 풀이 시간 : 32분 문제 풀이 총 k번 이동하여 미로를 탈출할 수 있는 문자열 경로 중 사전 순으로 가장 빠른 경로를 출력하는 문제이다. 문제의 조건 중 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. 라는 조건이 있다. 이를 통해 같은 격자를 중복해서 방문해도 된다는 것으로 확인할 수 있다. 우리는 최단경로를 찾기 위해 DFS, BFS ..