백엔드 개발자로 가는길

풀이 방법틀린 방식유니온 파인드를 통해 사이클 발생 여부 판단사이클 발생시 → 트리 없음 기록사이클 미 발생시, parent 배열을 통해 루트 노드 개수 카운팅틀린 이유사이클 발생 시, 해당 그래프만 트리가 아니고, 다른 그래프는 트리일 가능성 존재parent 배열이 최신 상태로 업데이트 되지 않은 경우, 루트 노드가 아닐 가능성이 존재한다.해결 방법사이클 발생 시 → 사이클 발생 노드 기록루트 노드를 parent 배열 말고, find()를 통해 찾기맞는 풀이유니온 파인드를 통해 사이클 발생 여부 판단사이클 발생시, 해당 노드에 사이클이라고 표시사이클 미 발생시, 루트 노드가 사이클인지 아닌지를 자식 노드 둘로 판단자식 노드 둘다 사이클이 아니라면 루트 노드도 사이클 아님find()를 통해 노드들의 루트..

https://www.acmicpc.net/problem/2169골드2풀이 방법단순 dfs로 하면 시간 초과 발생합니다. (시간 복잡도: O(3^(N * M))N, M(1≤N, M≤1,000)현재 문제는 “각 칸까지 올 수 있는 최적 해를 모아 두고, 그 위에서 다음 칸의 최적 해를 구한다”가 목표→ DP 생각하기이동 경로 가능 경로: 오른쪽, 왼쪽, 아래따라서 위에서 부터 오른쪽에서 왼쪽으로 갈 때 max값과 왼쪽에서 오른쪽으로 갈 때 max값을 구한 뒤두 값중 더 큰 값을 아래로 내려주면 된다.이때 시작은 0,0에서 하기 때문에 이 경우에는 왼쪽에서 오른쪽의 경우만 생각하면 된다.dp 시간 복잡도매 행마다 두 번의 선형 스윕을 수행하므로 O(N×M)코드import java.util.*;import j..