구름톤 2주차 PS

  • 2주차에서 가장 인상깊었던 문제는 백준에서의 1605문제 ( https://www.acmicpc.net/problem/1605 ) 랑 비슷한 유형의 문제였는데
  • 유형이 비슷할뿐이지 핀트가 약간 달라 문제를 설명하면 아래와 같았습니다
1) 오리진 문자열 "abcd" 가 있습니다
2) 오리진 문자열을 3개의 구간으로 쪼개는 모든 경우의 수는 아래처럼 총 3가지 입니다
a/b/cd
a/bc/d
ab/c/d
3) 쪼갠 문자열을 중복을 제거하고 사전순으로 정렬하면 아래처럼 6개의 원소를 갖게 됩니다.
a 
ab
b
bc
cd
c
4) 위 원소들의 인덱스를 구하는게 문제였습니다
  • 문제를 읽고 나니 솔직히 처음에는 단순히 구현문제인줄 알았습니다.
  • n 제한도 300이라 단순한 부르트포스가 가능하다고 판단하였고, 메인루프에서 n * (n-1) 가지 경우에 대해서 탐색을 허용한다면 브루트포스이고 이 문제의 최대 길이가 300 이기 때문에 최악의 경우 9만건정도만 계산한다면 답을 구할수 있다는 판단하에 구현을 시작했습니다.
  • 그냥 시키는데로 구현을 하고 코드를 제출했는데, 전체 20개중 5개정도의 TC 에서 Fail 이 발생하였습니다. 그리고 여기서부터 대삽질이 시작되는데요

삽질의 시작

  • 흠.. 어디보자.. 성능이 구려질만한곳이 있나.. 해서 성능개선 코드를 적용하였고 TC 에서 Fail 이 하나 줄어들었습니다
  • 하지만 여전이 4개의 TC 가 빨간 에러를 뿜뿜하고 있었고 저는 “아 이거 JVM 억까가 심하네” 라는 잘못된 생각을 했고 아무런 근거도 없는 이 잘못된 생각이 대삽질의 발단이 되었습니다.
  • JVM 언어가 문제니까 요즘 회사에서 스터디도 하면서 재미나게 배우고 있는 Go Lang 으로 코테문제를 박살내주겠어! 하는 생각으로, 코틀린으로 작성한 코드를 고랭으로 마이그레이션을 하기 시작했습니다.
readLine()!!.toInt()
val inputString = readLine()!!
val pointMapper: Map<String, Int> = getPointMapper(inputString);
var maxi = -1;

for (first in 1 until stringSize) {
    for (second in first + 1 until stringSize) {
        val section1: String = inputString.substring(0, first)
        val section2: String = inputString.substring(first, second)
        val section3: String = inputString.substring(second, stringSize)
        maxi = Math.max(
            pointMapper[section1]!! + pointMapper[section2]!! + pointMapper[section3]!!,
            maxi
        )
    }
}

이랫던 코틀린 메인코드를

var n int
fmt.Scan(&n)

var inputString string
fmt.Scan(&inputString)

pointMapper := getPointMapper(inputString)
maxi := -1
stringSize := len(inputString)

for first := 1; first < stringSize; first++ {
    for second := first + 1; second < stringSize; second++ {
        section1 := inputString[0:first]
        section2 := inputString[first:second]
        section3 := inputString[second:stringSize]
        maxi = max(pointMapper[section1] + pointMapper[section2] + pointMapper[section3], maxi)
    }
}

이렇게 고랭으로 변환했습니다

  • 그렇게 고랭으로 변환해서 제출하니 아니 똑같은 TC 에서 Fail 이 발생하였습니다.
  • 지나고 나니 이쯤에서 “언어는 문제가 아니야 알고리즘이 문제야!” 라는 생각을 했어야 했습니다.
  • 하지만 “코끼리를 생각하지마” 하면 코끼리만 생각하는게 인간인지라
  • 아 이게 역시 “메모리를 관리해주는 매니지드 언어의 한계구나 ㅋㅋ C++로 짜야겠어” 라는 뇌절 2탄을 찍으며 또 열심히 C++로 또 다시 마이그레이션을 했습니다.
  • 근데 C++은 코로나 전, 삼성코테 준비할때나 쓰던거라 기억도 가물가물하고 이쯤 되니 벌써 새벽 2시에 근접한 시간이라 그냥 포기하고 잠들었습니다.

그렇게 자고 일어나서, 제한시간의 90%가 흘러 마감까지 4시간 남았을때

  • 포기할까 하다가 아침에 눈도 빨리 떠지고 해서 출근전 회사 앞 카페에서 문제를 풀고 가기로 했습니다.
  • 출근길 전철에서 전날 풀다가 포기한 문제들과 제 코드를 보다 보니 여기저기 의심스러운 부분들이 보이기 시작했습니다.
  • MainLoop 의 시간복잡도만 생각할께 아니라, 부분문자열을 구하거나, 인덱스를 구하는 부분에서의 시간복잡도도 의심이 들기 시작했고, 출근하기 전 회사 앞 카페에서 진짜 문제를 발견하게 됩니다.

시간복잡도에 문제가 있는 코드

fun getSubStringRecursive(
    beginIndex: Int,
    inputString: String,
    subStrings: MutableSet<String>
) {
    if (beginIndex > inputString.length) {
        return
    }
    for (step in 1 until inputString.length - 1) {
        if ((beginIndex + step) > inputString.length) {
            return
        }
        subStrings.add(inputString.substring(beginIndex, beginIndex + step))
        getSubStringRecursive(beginIndex + step, inputString, subStrings)
    }
}
  • 먼저 시간복잡도에 문제가 발생한 부분입니다. 재귀함수를 돌려 모든 부분문자열을 탐색하는데, 이 코드는 너무 비효율적이라는 문제가 있었습니다.
  • 비효율적인 원인은 아래와 같습니다.

재귀의치명적임

  • 결론적으로 위 재귀코드로 부분문자열을 구하면 빅오표현법으로, 2^n 으로, n이 27만 넘어가도 탐색대상이 1억이 넘어가는 현실적으로 사용이 어려운 알고리즘이였습니다.

시간복잡도 문제를 해결한 코드

  • 위 코드의 비효율성을 해결하고자 탐색방식을 오리진 문자열의 인덱스 별로 모두 탐색 » 부분 문자열 길이 기준으로 탐색 을 변경한 코드로 변경했습니다.
  • 변경한 코드도 n^2 의 시간복잡도를 갖지만 n 제한이 300 이라 최대 9만번 루프를 도는데는 문제가 없었습니다. (just for 모든 부분문자열 구하는 로직)
fun getSubStringV2(beginIndex22: Int, inputString: String, subStrings: MutableSet<String>) {
    for (length in 1 until inputString.length - 1) {
        for (startPoint in inputString.indices) {
            if ((startPoint + length) > inputString.length) {
                continue
            }
            subStrings.add(inputString.substring(startPoint, startPoint + length))
        }
    }
}
  • 그리고.. 출근시간 20분 전에 아슬아슬하게 모든 TC 를 통과하고 기분좋게 출근할수 있었습니다.

교훈

  • 근거도 없이 JVM 언어라서 문제다! 라고 덮어놓고 생각한게 실책인거같습니다.
  • 처음 잘못된 판단을 하고 이를 풀어내는 과정에서 충분히 “그 원인이 아니다” 라는 실마리는 충분히 주어졌지만, 확증편향효과로 인해 캐치하지 못했습니다
  • 무의식적으로 대부분의 경우에, 특히나 쉬운 PS 를 할때는 아래의 논리구조로 문제를 해결하는거같습니다 
    이슈or증상 >> 가설 >> 시도 & 재시도 >> 운좋으면 해결 / 운나쁘면 삽질
  • 그런데, 생각해보면 꽤나 마구잡이식입니다. 컴퓨터를 만든 선생님께서도 “고장난 시계도 하루에 두번은 맞는다” 라고 하셨더랬죠..
  • 그래서 앞으로는 아래의 순서로 이슈에 접근하는 노력을 해보려고 합니다 
    이슈or증상 >> 원인분석 >> 근거확보 >> 문제해결
  • 네.. 그렇습니다 그래도 뭐 풀었으니까요… 이만 줄이겠습니다