백준

🔒 문제 🧠 아이디어 반드시 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해서 지워버리고 새로나온 타워 높이와 같거나 큰 애의 타워 번호를 정답으로 입력한다. 위..

🔒 문제 💭 생각의 흐름 라이브러리에서 CircularQueue 를 제공하거나 이미 구현해놓은 코드가 있다면 CircularQueue 안에서 iterator를 쓰면 좋겠다고 생각은 했지만 java, kotlin 에서 CircularQueue를 제공하지 않으므로 그냥 사이즈의 최대 크기를 넘어가는 시점에는 mod(%) 연산으로 index를 조정하는 방식을 택했다. 출력 결과에 '

문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해결 방법 행렬에 1로 되어있는 영역 (Graph) 갯수를 구하는 문제 BFS로 풀이한다. 노드간 연결을 수행할 때 양방향으로 해야하는지 단방향으로 해도 되는지 판단한다. 연결 대상 탐색은 우-하방향으로 하고 연결은 양방향 (우-좌, 하-상) 다 수행한다. 구현 [OrganicCabbage.kt] [main.kt]