Algorithm

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

알고리즘 문제에 간간히 등장하는 행렬 회전 로직, N * N 정사각형은 물론 N * M 직사각형 행렬에도 활용 가능한 코드를 미리 작성해보자. 📝 규칙 요점 정리 90도 회전함수 원본 행렬을 90도 회전시켜서 회전된 행렬을 반환한다. fun rotate(originalArray: Array) : Array { val originalRowSize = originalArray.size val originalColSize = originalArray.first().size // 행 열 크기 전환 val rotatedArray = Array(originalColSize){IntArray(originalRowSize)} for (row in originalArray.indices) { for (col in ori..

🔒 문제 🧠 아이디어 경우의수 - 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..

🔒 문제 🧠 아이디어 그래프상 간선과 정점이 주어지고 시작점 - 목적지 - 간선비용을 입력받는 전형적인 최소 비용 경로 문제. 단 경로 과정을 모두 킵해야 하므로 다익스트라 알고리즘 상에서 특정 지점에 도착하기 직전 지점을 배열에 담아 보관하고 시작점에 도달하기 까지 목적지로부터 거꾸로 출력해내기만 하면 되겠다. 🔑 Kotlin Code import java.io.BufferedReader import java.io.InputStreamReader import java.lang.StringBuilder import java.util.* import kotlin.collections.ArrayList fun dijkstra(startVertexNum: Int, distances: Array, preVert..