Algorithm/Algorithm (문제풀이)

🔒 문제 🧠 아이디어 문제를 읽자마자 뵈는 키워드는 '모든 집에서 치킨 집 까지의 최단 거리'다. 집의 개수가 최대 100개, 치킨집 개수가 최대 13개, 한 집에서 치킨 집까지의 거리 최대 연산량은 100 따라서 100 * 13 => 1,300으로 백트래킹 풀이가 충분히 가능하겠다는 생각이 들었다. 결국 조합이다. $$ _{13}C_{M} $$ (최대 13개 숫자 중 치킨 집 수 M개를 중복 없이 선택해야한다.) 치킨집의 좌표 List keep 모든 집의 좌표 keep 1과 2를 모두 돌면서 집 사이의 거리 (가로 좌표 차이 + 세로 좌표 차이) 각 치킨 집 좌표별 집과의 거리 keep 13개중 M 개를 고른 치킨집 좌표쌍까지의 거리를 모든 집에서부터 구한다. 모든 집은 모든 치킨 까지의 거리를 구하고..

🔒 문제 🧠 아이디어 반드시 2개의 정점을 경유해서 가야하므로 Way point (경유지) 1, 2 가 존재할 때 선택할 수 있는 경로는 다음 2가지로 좁혀진다. 출발 노드 -> 경유지 1 -> 경유지 2 -> 목적지 출발 노드 -> 경유지 2 -> 경유지 1 -> 목적지 여기서 구해야 할 값은 다음 5가지다. 출발 노드 -> 경유지 1의 최단경로 출발 노드 -> 경유지 2의 최단경로 경유지 1 -> 목적지의 최단경로 경유지 2 -> 목적지의 최단경로 경유지 1 - 경유지2 의 최단경로 양방향 그래프기 때문에 경유지 1-> 경유지 2, 경유지 2-> 경유지1는 서로 거리가 같기 때문에 한 번만 구하면 된다. 최단 경로를 구해야하므로 Dijkstra 알고리즘 사용한다. 출발 노드 -> 경유지 1,2 는 한..

🔒 문제 🧠 아이디어 스티커를 포함한 모든 모눈 종이는 결국 직사각형 형태다. 바탕이 될 노트북 모눈종이판을 'noteBookTable' 스티커 조각들을 'sticker' 라고하면 1. 스티커 붙이기 가능 불가능 여부 판별법 다음 4가지 케이스가 존재한다. ✔️noteBookTable 에서는 0 (비어있고) sticker 에서는 1 (스티커) ✔️noteBookTable 에서는 1 (이미 다른 스티커가 붙어있고) sticker 에서는 0 (공백) ✔️noteBookTable 도 0 (비어있고) sticker 에서도 0 ❌noteBookTable 에서 1 (이미 다른 스티커가 붙어있고) sticker 에서도 1 (스티커) 위 케이스중 1,2,3 번만 스티커 붙이기가 가능한 케이스다. noteBookTabl..

🔒 문제 🧠 아이디어 경우의수 - Backtracking 가능 여부 모든 CCTV가 동서남북 90도로만 회전 가능하다. CCTV 종류별로 다른 감시 영역을 갖도록하는 회전 횟수는 다음과 같다. 1번 : 4회 2번: 2회 3번: 4회 4번: 4회 5번: 1회 최대 CCTV 개수가 8개로 제한되어 있으므로 가장 경우의수가 많은 4회 기준 $$ 4^8\;=2^{16}\ $$ 약 6만 4천회므로 Backtracking 으로 모든 경우의 수를 따져보면 되겠다. 전체 킹우의 수를 어떻게 표현해야할까 모든 배열에 대한 조합이 필요하다. 이게 좀 빡치는데.. 각 CCTV 설치 지점으로부터의 방향 쌍에대한 모든 조합을 미리 keep 해둬서 구현했다. 2차원 배열에서 모든 배열의 쌍에 대한 조합을 구하는 코드가 Geeks..

🔒 문제 🧠 아이디어 N 이 50만개므로 $$ O(N^2) $$ 으로 풀었다간 무조건 시간초과다. 50만 * 50만 => 2,500억 회 로 거진 10초가 소요된다. O(N) 에 가까운 풀이를 생각해한다. == 높이를 앞에서부터 오른쪽으로 순회하며 한 번에 답을 구할 수 있어야한다. 가장 먼저 신호를 받을 타워는 높이가 내 왼쪽에 있는 것중 최신의 것이므로 새로운 타워에서 신호를 보낼 때마다 다음을 검사한다. 새로 나온 타워가 현재 stack top 보다 낮거나 같으면 stack top 타워의 번호를 정답으로 입력하고 새로 나온 타워가 현재 stack top 보다 크면 새로 나온 타워 높이보다 낮은 모든 애들을 pop해서 지워버리고 새로나온 타워 높이와 같거나 큰 애의 타워 번호를 정답으로 입력한다. 위..

🔒 문제 💡 아이디어 로프를 최대 중량 순으로 선택해야 감당 가능한 최대 무게를 구할 수 있다. 총 로프 선택 개수를 1 부터 N개 모두 해보고 최대 중량을 계산해야한다. 그럼에도 로프 중량을 큰 것 순으로 내림차순 하는게 좋은데 하나의 루프를 돌면서 index + 1 번째 로프가 현재 index + 1 개를 선택한 로프중 가장 작은 로프가 되기 때문이다. 로프를 k개 선택했을 때 들 수 있는 $$ 최대 중량값 = 가장\, 작은\, 로프\, 중량\: *\: k개 $$ 여기서 가장 작은 로프 중량 을 루프 안에서 매번 바로 선택할 수 있다. 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader import kotlin.ma..