⭕️ 14503번 : 로봇 청소기 (골드5)문제 유형 : implement, simulation시간 복잡도 : O(nm)풀이 방식 :- 0은 북쪽, 1은 동쪽, 2는 남쪽, 3은 서쪽이기 때문에 왼쪽으로 방향을 돌리고 한 칸을 이동하는 과정을 현재 방향을 나타내는 인덱스에서 1을 빼고 4를 더한 뒤 4로 나눈 나머지를 구하는 방식으로 구현- 만약 4방향을 모두 둘러 봤을 때 이동할 곳이 없으면 벽이 아닌한 후진하여 이동하는데 이 경우 청소 구역 수를 증가시키지 않음- 더 이상 이동이 불가하면 총 청소 구역 수를 출력 ⭕️ 16236번 : 아기 상어 (골드3)문제 유형 : graph, bfs, implement, simulation시간 복잡도 : O(n^2)풀이 방식 :- 상어가 먹을 수 있는 물고기들을 ..

문자열❌ 9251번 : LCS (골드5)문제 유형 : dp, String시간 복잡도 : O(nm)풀이 방식 :- 두 문자열의 위치를 나타내는 2차원 int 배열 dp 선언(0으로 초기화, 인덱스는 i, j로 표현)- 각 문자열의 현재 문자가 같을 경우 dp[i][j] = dp[i-1][j-1]- 다를 경우 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) -> 현재까지 구한 LCS의 길이를 뜻함- dp의 마지막 값이 LCS의 길이를 뜻함 ⭕️ 9252번 : LCS2 (골드4)문제 유형 : dp, String시간 복잡도 : O(nm)풀이 방식 :- 9251번과 같은 방식으로 dp 배열을 구하고 마지막 값부터 시작하여 dp[i-1][j]와 dp[i][j-1] 중 dp[i][j]가..

⭕️ 1949번 : 우수 마을 (골드2)문제 유형 : dp, tree시간 복잡도 : O(n)풀이 방식 :- ArrayList를 이용해서 트리를 저장- 방문한 정점 체크용 visit배열 이용- 현재 노드를 선택했을 때의 경우와 선택하지 않았을 경우의 주민수를 저장하는 2차원 dp[n][2]를 이용- 현재 노드를 선택한 경우 -> 자식노드는 무조건 선택하지 않음- 현재 노드를 선택하지 않은 경우 -> 자식노드를 선택했을 경우와 자식노드를 선택하지 않았을 두 경우 중 더 큰 값 선택- 리프노드부터 루트노드(1)로 올라오며 각 경우의 주민수를 구한 후 루트노드에서 더 큰 경우를 채택하여 출력 ⭕️ 1135번 : 뉴스 전하기 (골드2)문제 유형 : greedy, sort, dp, tree시간 복잡도 : O(nlo..

그리디와 쌍두마차로 씽크빅 문제라고 생각한다. 그래도 개인적으로 그리디보다는 문제를 많이 풀면 쉬워진다는 느낌은 드는 편인다. ⭕️15681번 : 트리와 쿼리 (골드5)문제 유형 : dp, tree시간 복잡도 : O(n)풀이 방식 :- ArrayList를 이용해서 트리를 저장- 방문한 정점 체크용 visit배열 이용- 리프노드부터 루트 노드로 올라오며 각 서브트리별 정점의 갯수를 dp배열에 저장 ❌ 9251번 : LCS (골드5)*문제 유형 : dp, String시간 복잡도 : O(nm)풀이 방식 :- 두 문자열의 위치를 나타내는 2차원 int 배열 dp 선언(0으로 초기화, 인덱스는 i, j로 표현)- 각 문자열의 현재 문자가 같을 경우 dp[i][j] = dp[i-1][j-1]- 다를 경우 dp[i]..

그래프 탐색 이외의 그래프 이론을 활용해 풀어야하는 문제 모음이다. ⭕️ 2252번 : 줄 세우기 (골드3)문제 유형 : graph시간 복잡도 : O(V+E)풀이 방식 :- Queue, 각 노드의 선행 노드 개수를 의미하는 배열, 각 노드의 후위 노드를 저장하는 ArrayList를 이용- 선행 노드의 개수가 0인 노드를 Queue에 넣고, 하나씩 빼내어 출력, 후위 노드들의 각 선행 노드 개수를 줄인다- 만약 선행 노드의 개수가 0이 되면 Queue에 집어넣으며 이 과정을 Queue가 빌 때까지 반복 (만약 출력한 노드의 수와 총 노드의 수가 다르면 사이클 존재 -> 위상정렬 개념, 이 문제에는 해당 입력 case가 존재하지 않음) ⭕️ 1516번 : 게임 개발 (골드3)문제 유형 : dp, graph시..

🙋🏻 DFS를 사용하는 이유DFS는 미로 탐색과 같이 목표 노드가 멀리 떨어져 있다는 가정이 존재할 때, BFS보다 유리하다. 1. 메모리 사용량이 BFS보다 적다.한 경로의 탐색이 완전히 끝날 때까지 다른 경로상의 노드가 비교적 추가되지 않기 때문에같은 거리상의 모든 노드를 큐에 저장해두는 BFS보다 메모리 사용량이 비교적 적다. 2. 경로 탐색에 유리하다.BFS의 경우 같은 거리에 위치한 모든 경로를 점진적으로 탐색하지만,DFS의 경우 각 경로를 끝까지 탐색하다가 목표를 찾을 경우 즉시 종료하기 때문에멀리 떨어진 목표까지의 경로 탐색에 유리하다. ⭕️ 1240번 : 노드사이의 거리 (골드5)문제 유형 : tree, graph, dfs, bfs시간 복잡도 : O(n)풀이 방식 :- 트리 형태를 띄고..

⭕️ 16236번 : 아기 상어 (골드3)문제 유형 : graphs, bfs, implementation, simulation시간 복잡도 : O(n^2)풀이 방식 :- 상어가 먹을 수 있는 물고기들을 선택할 때 가장 가까운 거리에 위치한 물고기 중 선택해야하기 때문에 bfs를 이용- 거리가 같은 물고기일 경우 가장 왼쪽에 위치한 물고기, 왼쪽 거리도 같다면 가작 위쪽에 위치한 물고기를 선택해야하기 때문에 이에 맞게 우선순위큐의 compare 조건을 지정- 떨어진 거리가 물고기들만 우선순위 큐에 들어가야하기 때문에 현재 큐의 크기만큼만 빼내어 탐색- 거리 1당 시간이 1씩 걸리기 때문에 선택한 물고기로 이동할 때마다 떨어진 거리(물고기까지의 bfs시행 횟수)만큼 더하여 총 이동 시간을 구한다 ❌ 2206..

알고리즘 문제 중 그래프 탐색 문제, 그 중에서도 BFS 문제 풀이를 가장 좋아한다. 그래서 그런지 골드 문제 풀이 비중도 BFS가 가장 높고,나중에는 연속 문제풀이를 유지하기 위해 그래프 문제를 빠르게 해치웠었다. DFS로 풀 수 있는 문제도 항상 BFS로 풀어서 코멘트를 남긴 문제가 꽤 많기 때문에,골드4~5와 골드1~3으로 나눠서 정리해보겠다. 🙋🏻 BFS를 사용하는 이유최소거리, 최소시간 등을 구해야하는 문제에 사용한다.  Queue를 사용하여 구현하기 때문에 항상 거리(시간)이 똑같은 케이스들이 먼저 나온다는 점이 핵심이다. 이러한 특징 때문에 조건에 맞는 첫 케이스가 항상 최소 거리(시간)임을 확정할 수 있어 사용한다.  ⭕️ 7576번 : 토마토 (골드5)문제 유형 : graphs, bf..