(알고리즘) Implement, 구현

오늘은 구현에 대해서 정리 해 보겠습니다.

 

구현

쉽게 말해 머릿속의 코드를 소스코드로 변환하는 과정입니다.

프로그래밍 처음 접하시는분들 이게 참 어렵죠..

소스코드를 떠나서, 머릿속에 어렴풋이 떠오르는 방법을 논리적으로 명시한다는게 쉽지는 않은데요,

구현에 대한 연습은 간단합니다.

요새는 대학교에가면, 전공자가 아니더라도 알고리즘을 배운다고 하던데.. 저는 예전에 이렇게 공부했습니다.

방법 설계 -> 플로우차트 -> NS차트 -> 소스 구현

NS차트까지도 굳이 필요할까 싶습니다.

초보자분들도 체계적으로 플로우차트 그리는 연습을 하다 보면, 금방 숙달이 될거에요.

 

그럼 책에 나온 몇가지 문제 풀이를 공유하겠습니다.

 

상하좌우

 

여행가 A는 N x N 크기의 정사각형 공간 위에 서있다. 이곳은 1X1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이고, 가장 오른쪽 아래 좌표는(N,N)이다.

L 왼쪽
R 오른쪽
U 위로
D 아래로

도착할 지점의 좌표를 출력해라.

입력
5
R R R U D D
출력
3 4

 

func implement1(size: Int, wayString: String) -> String {
    var x = 0
    var y = 0
    for way in wayString.split(separator: " ") {
        switch way {
        case "L":
            if y > 0 { y -= 1 }
        case "R":
            if y < size { y += 1 }
        case "U":
            if x > 0 { x -= 1 }
        case "D":
            if x < size { x += 1 }
        default: fatalError("way Error")
        }
    }
    
    return "\(x + 1) \(y + 1)"
}

(어차피 실제로 채점을 한게 아니라서 입력값은 무시하도록 합니다)

 

공간의 크기와, 방향을 입력받고, 그대로 옮겨주면 됩니다.

다만 공간을 벗어나는 경우에는 움직이지 않아야 하는데요,

저는 굳이 배열이 필요하지 않다고 생각해서, 배열없이 풀었습니다.

N의 사이즈가 오게 되면, 공간의 크기는 1~N이니까, 1보다 크고, N보다 작을때만 좌표를 움직여주면 됩니다.

아주 간단하게 풀리는 문제죠.

하지만 case 밑에 if는 조건문 -> 조건문 형식이라 코드가 썩 깔끔해보이지 않습니다.

따라서 다음과 같이 변경을 해 주었습니다.

func implement1(size: Int, wayString: String) -> String {
    var x = 0
    var y = 0
    for way in wayString.split(separator: " ") {
        switch way {
        case "L" where y > 0: y -= 1
        case "R" where y < size: y += 1
        case "U" where x > 0: x -= 1
        case "D" where x < size: x += 1
        default: break
        }
    }
    
    return "\(x + 1) \(y + 1)"
}

case 옆에 where로 조건을 정해줍니다.

다만 조건에 맞지 않을 때, default로 넘어가게 되는데, 그냥 무시해주도록 변경 해 주었습니다.

그리고 마지막 반환이 +1인 이유는, 1이 아닌 0부터 시작하기 때문입니다.

 

시각

 

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 N이 하나라도 포함되는 모든 경우의 수를 구하라

입력
5
출력
11475

 

5가 입력 된다면, 00:00:00 ~ 05:59:59 까지의 초단위의 값들을 나열해서, 거기에 "5"가 포함되는 모든 경우를 카운팅하는 문제입니다.

예시 답안을 Swift로 출력했을때는 이렇습니다.

func implement2(number: Int) -> Int {
    var count = 0
    for h in 0 ... number {
        for m in 0 ..< 60 {
            for s in 0 ..< 60 {
                if String(format:"%02i:%02i:%02i", h, m, s).contains("\(number)") { count += 1 }
            }
        }
    }
    
    return count // M1 기준 경과 시간: 0.05초
}

하지만 저는 이렇게 풀지 않았습니다.

처음에는 DateFormatter를 이용하여, 이렇게 풀었습니다.

func implement2_1(number: Int) -> Int {
    let timeLength = 3600 * (number + 1)
    
    let formatter = DateComponentsFormatter()
    formatter.allowedUnits = [.hour, .minute, .second]
    formatter.unitsStyle = .positional
    
    var count = 0
    
    for time in 0 ..< timeLength {
        count += formatter.string(from: TimeInterval(time))!.contains("\(number)") ? 1 : 0
    }
    
    return count // M1 기준 경과 시간: 0.91
}

 

1시간은 3600초이니, 5가 들어오면 18000 - 1개의 경우의 수겠죠?

시, 분, 초로.. 그리고 예시와 비슷한 스타일로 포매팅 시키게끔 처리 했습니다.

(포매터의 스타일은 여기를 참고하시면 됩니다.)

 

그리고 경우의수만큼 반복하여, 해당 숫자가 들어있을 시 카운팅을 하는 방법이었습니다.

M1맥으로 했을 때 0.9초가 나왔는데.. 인텔 맥으로 해보니 2초가 넘게 걸리더라구요 ㅠ.ㅠ

 

역시 이래서 되도록 알고리즘에 String은 쓰지 않는게 좋습니다.

String 연산 자체가 느리다기보다는.. Int연산은 감산이 전부이기때문에 훨씬 빠르게 처리가 가능하죠.

 

그래서 다른 방법을 강구 해 보았습니다.

 

func implement2_2(number: Int) -> Int {
    var count = 0
    for hour in 0 ... number {
        for minute in 0 ..< 60 {
            for second in 0 ..< 60 {
                if hour / 10 == number || hour % 10 == number || hour == number ||
                    minute / 10 == number || minute % 10 == number || minute == number ||
                    second / 10 == number || second % 10 == number || second == number
                {
                    count += 1
                }
            }
        }
    }
    
    return count // M1 기준 경과 시간: 0.007
}

if 조건이 조금 복잡한데요.. 풀이해보면 이렇습니다.

시|분|초 별로 분리해서 생각합니다.

최대 두자릿수입니다.

해당값의 앞이 N인지.

해당값의 뒤가 N인지.

해당값 자체가 N인지.

51의 경우 앞이 5입니다.

number/10 -> 5가 나옵니다.

15의 경우 뒤가 5죠? 그럼

number % 10 -> 5가 나옵니다.

그냥 5가 나왔을 시 

number == 5 -> 5가 나오죠.

 

이런식으로 18000번 반복하여 시, 분, 초의 값중 N이 포함된 값을 모두 처리하는겁니다.

여기서 생각을 한번 더 꼬아 보았습니다.

 

func implement2_3(number: Int) -> Int {
    var count = 0
    
    for hour in 0 ... number {
        if hour / 10 == number || hour % 10 == number || hour == number {
            count += 3600
            continue
        }
        for minute in 0 ..< 60 {
            if minute / 10 == number || minute % 10 == number || minute == number {
                count += 60
                continue
            }
            for second in 0 ..< 60 {
                if second / 10 == number || second % 10 == number || minute == number {
                    count += 1
                }
            }
        }
    }
    
    return count // M1 기준 경과 시간: 0.004
}

반복문 자체는 비슷하지만, 조건은 N이 들어가는 숫자만큼 카운팅이 아니라,

N이 하나라도 들어가있을 때 카운팅입니다.

즉 N:00:00 ~ N:59:59는 모두 카운팅이 될수밖에 없는 구조이고.

00:N:00 ~ 23:N:59 또한 모두 카운팅이 될수밖에 없는 구조입니다.

따라서 시간단위에서 카운팅이 된다면, 1시간은 3600초이니 3600을 한번에 더해주고 반복문을 건너 뜁니다.

분단위에서 카운팅이 된다면 60을 한번에 더해주고 반복문을 건너 뜁니다.

 

반복을 줄이니 그만큼 시간도 빨라졌습니다.

 

왕실의 나이트

왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다.나이트가 특정한 한 칸에 서 있을 때 나이트가 이동할 수 있는 경우의 수를 구하라
나이트는 L자 형태로만 이동할 수 있으며, 정원(map) 밖으로 벗어날 수 없다.
1. 수평 두 칸 이동 후 수직 한 칸 이동
2. 수직 두 칸 이동 후 수평 한 칸 이동

입력
나이트가 현재 위치한 곳의 좌표, 두 문자로 구성
a1

출력
2

8 * 8이라는 고정되어 있는 공간에서 위치가 주어 졌을 때, 저 방법대로 이동을 하면, 이동할수 있는 경우의 수를 계산하는건데요.

가로는 a~h까지로 되어있습니다.

(자세한 내용은 책을 참고하시길..)

이것도 예시를 먼저 보게 되면..

func implement3(_ startPoint: String) -> Int {
    var result = 0
    
    let row = Int(Array(startPoint)[0].asciiValue! - 96)
    let column = Int(Array(startPoint)[1].wholeNumberValue!)
    
    let steps = [(-2, -1), (-2, +1), (-1, +2),  (+1,+2),  (+2, +1),  (+2, -1),  (+1, -2),  (-1, +2)]

    for step in steps {
        let next_row = step.0 + row
        let next_column = step.0 + column
        
        if 1 ... 8 ~= next_row && 1 ... 8 ~= next_column {
            result += 1
        }
    }
    
    return result
}

a~h의 변환은 ascii 코드 값으로 숫자로 변환 해 줍니다.

그리고 steps 배열을 미리 만들어 놓고, 대입을 하는데요.

 

결국 ±2와 ±1을 대입했을 때, 1~8의 범위에 안착하느냐 안하느냐에 대한 카운트입니다.

 

이동후의 위치가 0보다 작거나, 8보다 크면 그곳은 갈수 없는 범위가 되니깐요.

 

저는 이렇게 풀이했습니다.

 

func implement3(_ startPoint: String) -> Int {
    var count = 8
    let startPointCharArray = Array(startPoint) // 입력받은 문자열을 배열 캐릭터로 나눔.
    var points = [Int]()
    
    let max = 7
    
    for point in startPointCharArray {
        // x와 y의 조건이 같기때문에, x, y의 구분은 필요하지 않음. 따라서 2칸의 배열로 처리.
        // 1~8 / A~H 의 좌표계로 되어있지만, 로직은 가로 세로 둘다 0~7을 이용.
        // 해당 캐릭터가 숫자인지 확인 후 숫자라면 숫자로 변환, 아니라면 문자로 변환.
        // 그런데 소문자 a의 아스키코드값은 97이므로, 97을 빼준다. 따라서 a는 0, h는 7이됨.
        points.append(
            point.isWholeNumber ? Int(point.wholeNumberValue!) - 1 : Int(point.asciiValue!) - 97
        )
    }
    
    // 핵심 로직은 이렇게 접근함.
    // "2칸 전진 후 좌우 확인."
    // 2칸 전진이 되지 않는다면, 좌우확인도 되지 않는다. 따라서 좌, 우 1개의 경우의수를 놓치기 때문에, 2칸 전진이 되지 않는다면 2개의 경우의수가 날아간다.
    // 2칸전진이 되는데, 좌측 혹은 우측으로 진입이 되지 않는다면 1개의 경우의수가 날아간다.
    // 4방향이기때문에, 모든 경우의수는 8가지다. 그래서 count를 8에서 빼가는 역계산을 하는 것.
    // 아래 로직은, 주석에 있는 방법을 반복문으로 변환한것이다.
    // if x - 2 < 0 { count -= 2 }
    // if x + 2 > 7 { count -= 2 }
    // if x - 1 < 0 { count -= 1 }
    // if x + 1 > 7 { count -= 1 }
    // if y - 2 < 0 { count -= 2 }
    // .
    // .
    // .
    // if y + 1 > 7 { count -= 1 }
    // 위 코드를 x, y가 아닌 2개의 좌표배열, 그리고 반복문으로 실행하면 이런 로직이 완성된다.
    for point in points {
        for value in 1 ... 2 where point - value < 0 || point + value > max {
            count -= value
        }
    }
    
    return count
}

어차피 네방향이므로 최대 경우의수는 8입니다.

 

카운트를 8에서부터 감산을 하는데, 핵심 로직은 이것입니다.

 

(1 ~ 8이 아닌, 0 ~ 7로 봤을 때)
x - 2 < 0 or x + 2 > 7 -> 경우의수 몇개가 사라질까요?
x - 1 < 0 or x + 1 > 7 -> 경우의수 몇개가 사라질까요?

이것을 잘 생각 후, N씩 감소시킵니다.

 

4번째 문제는, 개인적으로 헷갈려서 많이 어려웠습니다.

 

그것은 다음 포스팅에 따로 설명 하겠습니다.