SY DevLog

사용한 방법 : BFS, DFS 어려웠던 점 : 처음에는 graph를 나타낼때 인접행렬을 사용하여 나타냈었는데 계속 메모리 초과가 났다. 그래서 ArrayList graph=new ArrayList();로 바꾸어서 해결하였다. 평소에 bfs, dfs 문제를 풀 때는 인접행렬을 이용하여 풀었기 때문에 리스트를 이용한 풀이가 낯설었다. 인접행렬의 경우, 두 정점이 인접할 경우 1을 넣고, 인접하지 않은 경우 0을 넣는 방식이다. 리스트를 사용하면 0번째 리스트에서는 정점 1과 인접한 정점들의 번호가 들어가고, 1번째 리스트에서는 정점 2와 인접한 정점들의 번호가 들어가는 식이다. 리스트를 사용하면 인접한 정점들에 대한 정보만 들어가기 때문에 메모리가 더 적게 차지한다. 즉, 메모리면에서는 행렬보다는 리스트가..

사용한 방법 : DP 2차원 배열을 이용하여 lcs를 구하였다. 예를 들어 dp[i][j]이면, 첫번째 문자열에서 i번까지의 문자열과 두번째 문자열에서 j번까지의 문자열의 LCS를 구한 값이 들어가게 된다. 먼저 예시로 주어진 ACAYKP와 CAPCAK로 LCS를 구해보면 A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2 2 2 P 1 1 2 2 2 3 C 1 2 2 2 2 3 A 1 2 3 3 3 3 K 1 2 3 3 4 4 다음과 같이 표를 완성할 수 있다. 여기서 나타나는 규칙을 보면 같은 문자가 만나는 지점에서 값이 증가한다는 점이다. A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2 2 2 P 1 1 2 2 2 3 C 1 2 2 2 2 3 A 1 2 3 3 3 3 K..

사용한 방법 : BFS 빨간 구슬의 위치를 넣는 큐와 파란 구슬의 위치를 넣는 큐 이렇게 두 개의 큐를 생성한다. 각각의 큐에는 기울이기를 통해 움직이고 난 후의 빨간구슬의 위치와 파란구슬의 위치 정보가 들어있다. Queue redque = new LinkedList(); Queue blueque = new LinkedList(); Pos 클래스는 구슬의 위치(n, m)과 구슬이 해당 위치에 도달했을 때 총 움직인 횟수 move 가 들어간다. static class Pos { int n, m, move; Pos(int n, int m, int move) { this.n = n; this.m = m; this.move = move; } } 한 번 기울이면 구슬은 장애물(벽 혹은 다른 구슬)에 부딪힐 때까지..

사용한 방법 : BFS 어려웠던 점 : 하루가 지나면 익은 토마토 주변(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)의 익지 않은 토마토가 익게 되는데 문제는 "익은 토마토 주변의 익지 않은 토마토가 익어가는 행위는 하루 사이에 동시다발적으로 진행"된다는 점이었다. 처음에는 큐에서 poll할 때마다 하루가 지나는 것으로 카운트하였는데 그러면 예를 들어 처음에 5개의 익은 토마토가 있는 경우, 하루밖에 안지났는데 카운트가 5가 되어버린다. 해결 : 어떠한 익은 토마토가 n번째 날에 익었다면 그 주변의 익지 않은 토마토는 n+1번째 날에 익은 것이므로 큐에 새로운 익지 않은 토마토가 있는 위치를 넣어줄 때마다 +1을 해주었다. package num7569; import java.io.BufferedReader; i..