SH

BOJ Linkhttps://www.acmicpc.net/problem/17136 개요처음에 depth가 엄청 깊어질 거라 생각해서 그리디하게 풀 수 있나 생각했다. 반례로 안된다고 확정지었다.완탐으로 구현했는데, 역시나  1의 개수가 많아질수록 복잡도가 팩토리얼 단위로 늘어나므로 IDE에서도 오래걸렸다.(정확한 시간 복잡도 계산은 까다로웠다.)풀이 과정이중 for문을 사용해 탐색하며 3가지 최적화를 했다. (그럼에도 통과하지 못했다.) 1. 매 dfs 탐색 마다 map이 전부 0인지 세기 -> 붙이기/떼기 동작에서 같이 세기map이 10*10이라 그냥 매 탐색마다 셌었는데 바꿨다. 2. size 1 to 5탐색 -> size 5 to 1로 바꾸기가지치기에 현재 cnt가 ans 이상이면 return하는 ..

BOJ Link https://www.acmicpc.net/problem/1389 개요정점간 최단 경로를 찾는 문제이다.(정확히는 다른 모든 정점까지의  최단 경로 가중치 합이 가장 작은 노드를 찾는)그러므로, 플로이드-워셜이나 다익스트라 N번 반복으로 답을 찾을 수 있다.간선별 가중치가 동일하며, 시작 노드로부터 다른 모든 노드에 도달 가능하므로 일반적인 bfs 풀이도 가능하다.삽질 이후 이를 깨닫고 제출하여 통과했다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;import java.u..

BOJ Link https://www.acmicpc.net/problem/18137 개요처음 기록하는 알고리즘 문제이다. 누군가 내 글로 해답을 찾는데 도움되게 쓰기보단, 내 사고의 흐름만 기록하는 방식으로 작성하려 한다. 시간제한 0.5초 구현+애드 혹 문제이다. 애드 혹이란 정해진 방법 없이 개인의 아이디어로 푸는 문제 분류이다. (알고리즘 기법 자체가 아니다.) 풀이 과정1. x칸 y칸은 각각 왼쪽/아래에서 몇번 째 칸인지 의미한다. 따라서 x>0, y>0일 때만 탐색한다. 이때,주어진 식에서 엣지 케이스 (분자가 int범위를 초과할 때) 나 익셉션이 발생할 경우 (예를 들면 division by zero)는 없다고 생각했다.전자는 확신하려면 k=2^31 - 1일 때로 증명해야 해서 일단 가정했다...