Algorithm

비트마스킹 기법을 사용하기 위해 익혀야할 비트연산자를 정리해보자. 1. 길이 N을 갖는 이진수를 모두 1 (flag on) 상태로 만들기 표현식 $$ (2 11111 // 십진수로는 2 ^ N - 1 로 표현가능하다. // 2 ^ 6 - 1 == 63 val num = (1 shl (5 + 1)) - 1 println("=============") println("All flag on") println(toDecimalString(num)) println(toBinaryString(num)) println("=============") } 결과 2. 특정 index flag bit 키기 표현식 $$ num\; or \; (1 11111 // 십진수로는 2 ^ N - 1 로 표현가능하다. // 2 ^ 6 ..

🔒 문제 ⚠️ 실수 노트 1번 ~ 6번에 대해 전개도가 있으므로 동서남북 이동시 오게되는 윗 칸을 저장하는 6개 면을 의미하는 객체 생성 각 객체는 값을 가지고 객체별로 동서남북으로 주사위 방향이 이동했을 때 표현하는 객체 값을 고정해둠. 총 6개 면에 대해 동서남북 주사위 굴리기시 표현되는 윗칸을 '고정'하면 안된다. 굴리면서 보는 각도가 달라질 수 있기 때문이다. // 전개도의 각 면에대해 data class 를 미리 만들고 초기화 // ⚠️ 틀린 접근 방법 data class DiceSquare(var curVal: Int = 0, var east: DiceSquare?, var west: DiceSquare?, var south: DiceSquare?, var north: DiceSquare?, ..

🔒 문제 🧠 아이디어 가로 6, 세로 12를 갖는 테트리스 판의 일종이다 우선 4개 이상의 뿌요 조각이 인접해있을 때만 '.'으로 대치한다. + '.'으로 대치된 조각이 있으면 아래로 뿌요조각을 당겨야한다. 뿌요 조각을 당기는 아이디어가 핵심이다. 세로 막대를 의미하는 LinkedList 를 미리 6개 생성해두고 '.'만을 모두 제거해 남은 뿌요 조각을 뿌요판에 붙여넣는다. 또, 판 크기 자체가 12 * 6 == 72회로 작으므로 전체 판을 매번 긁어도 시간 초과하지 않겠다는 직관을 가지고 풀이했다. 하나의 뿌요조각이 다음 단계로 이어지려면 매번 4조각씩 해도 총 18라운드가 최대다. 72 * 72 * 18 => 약 10만 으로 절대 시간초과가 나지않는다. 🔑 Kotlin Code import java...

🔒 문제 🧠 아이디어 "()"을 모두 '*'로 미리 대치한다. 🔑 풀이 1. Kotlin Code ')' 을 만날 때마다 이전 '(' 까지 pop 하며 *의 개수를 카운팅하는 무식한 방법으로 풀이했다. import java.io.BufferedReader import java.io.InputStreamReader import java.util.* fun main() { val bufferedReader = BufferedReader(InputStreamReader(System.`in`)) val str = bufferedReader.readLine().replace("()", "*") val stack = Stack() var answer = 0 for (char in str) { when (char) ..

🔒 문제 🧠 아이디어 문제를 읽자마자 뵈는 키워드는 '모든 집에서 치킨 집 까지의 최단 거리'다. 집의 개수가 최대 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 는 한..