문제 파악https://www.acmicpc.net/problem/1197풀이제목에서도 알 수 있지만 최소 신장 트리 MST 문제이다(Minimum Spanning Tree)BFS, DFS에서는 방문 여부 체크하는 visited 배열을 쓰다가 사이클을 신경 쓰는 문제를 오랜만에 풀어 흥미로웠다..본론으로 돌아가자면 기본적으로 부모(루트) 노드에 대한 접근이 필요하다.부모 노드에 대한 정보를 저장하기 위해 부모 노드의 인덱스를 값으로 가지는 일차원 배열(parent[])을 선언하여 사용해 주도록 하자.여기서 부모 노드가 되는 조건은 parent[i] = i일 때가 된다.또한 부모 노드가 같은 정점이라면, 같은 트리에 속해있다고도 이해할 수 있다.위 조건을 염두에 두고 핵심적인 두 가지 기능을 구현하도록 하..

문제 파악https://www.acmicpc.net/problem/12180어쩌다 영어 문제를 풀게 되었다..풀이본문에 따르자면 "우아한" 경로의 수를 출력한다.우아한 경로를 만들기 위한 조건은 다음과 같다.진행 방향을 그대로 유지하는 방법, 진행 방향에서 오른쪽으로 90도 회전하여 진행하는 방법이다.만일 위 두 가지 경로가 이미 방문한 경로이거나, 범위를 벗어난 경우 그 자리에서 멈추고 종료한다.보통은 시작점과 끝점이 동일한 문제가 많이 주어졌으나, 해당 문제는 우아한 경로를 만들지 않는 경우에는 종료하는 형태를 띄어 진행할 때마다 방문 정보를 가지고 있어야 한다.문제에서 주어지는 행/열의 범위는 10으로 적은 편에 속하며, 직진/우회전이라는 2가지 경우의 수를 갖고 있기에 재귀를 선택하여 풀이했다.물..

문제 파악https://www.acmicpc.net/problem/12865풀이DP 문제의 정석으로 보인다.. 항상 어떤 데이터를 중점으로 배열을 구성할 지 정하도록 하자.문제에서 주어진 데이터는 가방의 개수 N, 무게 W, 가치 V이다.그 중 변동이 적어 보이는 무게 W를 기준으로 잡아 최대 가치 V를 구하는 방향을 택하였다.그러기 위해 배열 DP[W]를 선언해 주도록 한다.이 문제는 입력을 받으며 DP 배열을 업데이트 해 주었다.새로운 물건에 대한 입력(wVal - 무게, vVal - 가치) 을 받을 때wVal : 만일 기존의 DP[wVal] 보다 높다면 업데이트wVal + 1 ~ maxWeight : DP[maxWeight-wVal] + vVal, DP[maxWeight-wVal]와 비교하여 ..

문제 파악https://www.acmicpc.net/problem/1025N, M 이 적은 점을 참고하면 모든 해에 대해 탐색하며 업데이트하는 방향으로 진행하였다.풀이행/열에 해당하는 row/col을 순환하며 arr[row][col]부터 시작하는 등차수열을 만들어 제곱근일 경우 최댓값을 업데이트해 준다.또한 row, col을 시작으로 하는 등차수열을 만들어준다. 이때, 등차는 [-8,8]을 선정해도 무리는 없을 듯 하나, 나 같은 경우 총 행/열 중 큰 값으로 진행했다.등차는 열, 행에 개별로 적용하자열에 해당하는 등차는 oc, 행에 해당하는 등차는 or로 선언하고 풀이했다.그림으로 보자면 다음과 같을 것이다.물론 등차에 해당하는 oc, or를 더했을 시 범위를 벗어나는지 체크해야 한다.열 등차, 행 ..

문제 파악https://www.acmicpc.net/problem/1351풀이점화식 : DP[N] = DP[N/P] + DP[N/Q] 배열🚫, 반복문🚫메모리 이슈로 배열을 N 크기(최대 10^12)만큼 선언해 두고 사용할 수 없다 😅또한 피보나치를 풀이할 때처럼 DP[N] 계산 시 모든  [1, N]에 대해 값을 채워야 하므로, 연산량이 매우 커진다불필요한 값(사용되지 않는 DP 배열의 부분)까지 계산해야 하므로 비효율적이다.Map⭕️, 재귀 ⭕️따라서 Map을 사용하는 방향을 선택했다.해당 시간 복잡도는 O(1)이기 때문에 배열 접근과 차이가 나지 않을 것이다.이를 탑다운식의 재귀로 풀이해보도록 하자N = 100, P = 50,  Q = 30 를 예로 들어보자.100번째 수 ➡️ [2번째 수 +..

문제 파악진실을 아는 자들이 진실을 퍼트린다고 생각하면 좋다.진실이 다 퍼졌을 때에도 진실을 아는 이가 없는 파티가 있다면, 그 파티에서 지민이는 거짓말을 할 수 있다.풀이큐를 사용하여 풀었으며, 풀이 순서는 다음과 같다.입력으로 주어지는 진실을 아는 사람들을 큐에 넣어준다.큐에서 사람들을 꺼내며, 진실을 아는 사람임을 체크해 준다.진실을 아는 사람들이 참가한 파티를 역추적한다.진실을 아는 사람들이 참가한 파티는 지민이가 거짓말을 할 수 없으므로 답에서 제외한다.해당 파티에 참가한 참석자들을 큐에 다시 넣어준다.이 때, 이미 진실을 아는 사람은 큐에 추가할 필요가 없다. (단계 2에서 체크 했으므로)그렇게 되면 무한으로 사람들을 추가하게 될 것코드import java.io.BufferedReader;im..