[기출 풀이: 2024 KAKAO WINTER INTERNSHIP] 주사위 고르기

[MUKER-WON]

11/6(수)

주사위 고르기

[MUKER-WON]

• 약 40분 풀었을 땐 대충 어떻게 풀어야겠다 생각만 하고 코드는 안나옴..좌절 + 풀기 싫음
• 다시 백트래킹을 다시 되짚어가며 풀이를 마저 완성했지만 시간초과로 실패
• 시간복잡도를 먼저 인지해보고 풀이를 들어가기로 했지만, 시간복잡도 구하는게 감이 안잡힘. 그래서 먼저 풀고 AI한테 물어봄
  답변:
  n이 10일 경우의 최대 연산 횟수:
  252 (조합) × 7,776 (A의 합) × 7,776 (B의 합)
  = 252 × 60,466,176
  ≈ 15,237,476,352

이러니 시간초과가 날 수 밖에..없었음
머리 식히고 다시 풀어 보겠음

case19번 부터 시간초과 된 코드

import Foundation

func solution(_ dice:[[Int]]) -> [Int] {
    let eachCount = dice.count / 2
    var ans = [Int]()
    var maxWin = 0
    
    // A와 B가 가질 수 있는 주사위의 경우의 수 구하기
    var diceCases = [(A: [Int], B: [Int])]()
    
    func diceCase(current: Int, a: [Int]) {
        if a.count == eachCount {
            // Set으로 초기화를 시켜주면 contains 시간복잡도가 무려 O(1)
            let b = (0..<dice.count).filter { !Set(a).contains($0) }
            diceCases += [(a, b)]
            return
        }
        for i in current..<dice.count {
            diceCase(current: i+1, a: a+[i])
        }
    }
    diceCase(current: 0, a: [])
    
    func Allsum(index: [Int]) -> [Int] {
        // 주사위 갯수에 따른 주사위의 경우의 수를 합해서 배열로 반환
        func calculate(current: Int, sum: Int) -> [Int] {
            if current == index.count {
                return [sum]
            }
            var result = [Int]()
            
            for i in dice[index[current]] {
                result += calculate(current: current + 1, sum: sum + i)
            }
            return result
        }
        return calculate(current: 0, sum: 0)
    }
    
    for (A, B) in diceCases {
        let sumA = Allsum(index: A)
        let sumB = Allsum(index: B)
        
        // 모든 경우의 수를 또 모든 경우의 수로 비교.. 경우의 수 지옥
        // A가 이긴 경기에 따라 maxWin과 ans 최신화
        var win = 0
        for a in sumA {
            for b in sumB {
                if a > b {
                    win += 1
                }
            }
        }
        
        if win > maxWin {
            maxWin = win
            ans = A.map { $0 + 1 }
        }
    }
    
    return ans
}

[shippingpark]

크크 일단 손에 잡은 순간부터 문제를 하나 발견했어. 그건 바로 내가 시간복잡도를 계산할 줄 모른다는 것 .
n 범위가 10일 때 부터 대충 엄청 오래걸리는 문제겠구나 느끼긴 했지만 시간복잡도 이정도 쯤 되겠네, 이렇게 바로 연산 불가.

시간복잡도에 대해서 공부하는 시간을 가졌고... 챗지피티한테 물어보니까 더 어려웠음
그래서 차근차근 경우의 수부터 구해봄!

1. 일단 주사위 n개 중에 n/2개 선택 경우의 수
2. 최대 5개의 주사위는 눈을 6개 가지고, 6개중 한 개를 5번 던지는 일이니 6^5 경우의 수 존재
3. 상대방 조합 또한 6^5
4. 6^5 * 6^5 * nCn/2
5. 일단 주사위를 뽑고, 주사위를 굴려서 나오는 합산을 구하는 건 줄이는 방법 생각 X
6. 마지막 곱셈인 6^5, 즉 상대방과의 비교를 최대한 적은 연산으로 진행하여 해결하자 // ⭐️
7. 나와 상대의 합산 배열을 정렬하고, 나의 값에 대하여 최대로 작은 지점을 발견하면 그 위치로부터 0까지의 갯수가 곧 이기는 수 (이진탐색?)
8. 7번 과정을 이루기에 포인터로 대입하던 알고리즘 (기억안남) 도 좋을듯

시간복잡도) 시간복잡도에 너무 약해서 뒤적뒤적

• 알고리즘의 속도는 문제를 풀기까지 걸리는 절차의 수
• 분석을 빠르게, 해결방법 선택 용이
• Big O는 대략적인 어떻게 함수가 작동하는 지, input Size에 대한 절차의 수

inputSize에 대한 절차의 수! 라는 표현 좋다

1. O(1) 상수시간: N이 얼마나 크든 상관없이 늘 일정한 시간 복잡도를 가짐. (ex_ 배열의 첫번째 요소)
   2.O(N) : 인풋이 증가하면 아웃풋도 증가함
   2.O(N^2) :3217 ...

입력이 제한되어 있기 때문에 브루트 포스 (완전탐색) 형태로 구현하면 어떨까 생각