문제https://www.acmicpc.net/problem/10159 여담거리가 사용되지 않아도 "플로이드 와셜 알고리즘 == 무조건 길이 사용" 이라는 생각때문에 거리를 계산하면서 문제를 풀었다. 문제를 다 풀고 다른 풀이를 참고했는데 그냥 boolean 배열을 사용해서 연결 여부만 확인하면 된다는 것을 알게 되었다..! 틀에 박힌 생각 제발 버리자 풀이입력으로 주어지는 측정된 물건의 쌍은 그래프로 표현할 수 있다. 물건들의 비교 결과를 알 수 없다는 것은 서로 연결되어 있지 않다는 것을 의미한다. 따라서 측정된 물건의 쌍을 단방향 그래프로 표현한 뒤, 물건이 서로 연결되어 있는지 확인하면 된다. 모든 물건에 대해서 연결되어 있는지 확인해야 하므로 플로이드 와셜 알고리즘을 사용하면 된다. 이때, 물..

문제https://www.acmicpc.net/problem/1967 여담리프 노드에서 BFS 탐색을 반복하고, 거기서 나오는 최대 길이가 원의 지름일 것이라고 생각했다. 그렇게 계속 풀이를 했지만 계속해서 메모리 초과를 맞이했다. 이게 맞는 풀이인 것 같은데 대체 왜 문제가 있지..? 싶어서 괜히 연결된 노드의 정보를 저장하는 방법만 변경해서 실행했다.결국 풀이를 참고했고, 내가 접근한 방법이 틀렸다는 것을 알게 되었다 ㅎㅎ... 문제를 풀다가 막히면 다른 방법도 떠올려보는 습관을 가지도록 노력해야겠다. 풀이해당 문제는 BFS 탐색을 통해 풀 수 있다. 트리의 지름은 "트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이"를 뜻하므로 노드 간의 길이 중 최대 길이를 구하면 된다.  따라서 풀이 순서는..

문제https://www.acmicpc.net/problem/11660 여담저번에 풀었던 문제임에도 불구하고 까먹어서 결국 풀이를 참고했다. 그때도 완전히 익히지 않고 넘어갔다는 뜻이겠지..? 이런식으로 설렁설렁 넘어간게 대체 몇 개인지🤦🏻‍♀️ 이번에는 좀 익히자.. 풀이2차원 테이블을 사용해서 누적합을 구하면 되는 문제이다.  우선 배열의 값들을 입력받은 후, 아래의 점화식을 이용해 dp 테이블을 채워야 한다.dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j] 누적합을 이용해 dp 테이블을 채운 후, 이제 원하는 영역의 누적합을 구해야 한다. 이를 위해 다음 그림과 같이 각 구간의 누적합을 더하고 빼주면 된다. 코드import java.i..

문제https://www.acmicpc.net/problem/10844 여담저번에 풀려고 시도했다가 풀지 못해서 그냥 나뒀던 문제였다.. 그치만 계속 외면할 수는 없어서 풀이를 참고해서 풀었다.표를 그려서 풀었다면 규칙을 찾아낼 수 있었을텐데 계속 다른 방식으로 삽질해서 아쉬웠다😂 DP 오랜만에 푸니까 너무 어렵다..!! 풀이이 문제는 규칙만 찾아내면 쉽게 풀이할 수 있다. 참고한 블로그의 표를 보고 쉽게 이해했으므로, 나도 표를 이용해서 설명하려고 한다.해당 문제는 인접한 모든 자리의 차이가 1이다. 따라서 0에서 9까지의 숫자 뒤에 올 수 있는 숫자들의 특징은 다음과 같다.앞의 자리가 0 ⇒ 다음 자리는 무조건 1앞의 자리가 9 ⇒ 다음 자리는 무조건 8앞의 자리가 1 ⇒ 다음 자리는 0 또는 2앞..