[알고리즘] 구현(Implementation)

구현(Implementation)이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제이다.

• 알고리즘은 간단한데 코드가 지나치게 길어지는 문제
• 특정 소수점 자리까지 출력해야 하는 문제
• 문자열이 주어졌을 때 파싱 해야 하는 문제

구현 시 고려해야 할 메모리 제약 사항

• 변수의 표현 범위
• 리스트(배열) 크기

 

완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 

 

---

구현 알고리즘 문제

상하좌우

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

L: 왼쪽으로 한 칸 이동
R: 오른쪽으로 한 칸 이동
U: 위로 한 칸 이동
D: 아래로 한 칸 이동

각 문자의 의미가 위와 같을 때 L, R, U, D 문자들을 입력받아 A가 최종적으로 도착하는 좌표를 출력하는 프로그램을 작성하시오.
(단, N x N 정사각형 공간을 벗어나는 움직임은 무시된다.)

 

var n = Int(readLine()!)!
var plans = readLine()!.split(separator: " ").map{String($0)}

var x = 1, y = 1
var new_x = 0, new_y = 0

let dx = [0, 0, -1, 1]
let dy = [-1, 1, 0, 0]
let move_type = ["L", "R", "U", "D"]

for plan in plans{
    for i in 0..<move_type.count{
        if plan == move_type[i]{
            new_x = x + dx[i]
            new_y = y + dy[i]
        }
        
        if new_x < 1 || new_y < 1 || new_x > n || new_y > n{
            continue
        }
        x = new_x
        y = new_y
    }
}

print("\(x) \(y)")

---

왕실의 나이트

행복 왕국의 왕실 정원은 체스판과 같은  8 x 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에는 나이트가 서있다.
나이트는 L자 형태로만 이동할 수 있으며, 정원 밖으로는 나갈 수 없다. 나이트는 다음과 같은 2가지 경우로 이동할 수 있다.

1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동할 뒤에 수평으로 한 칸 이동하기

나이트의 처음 위치를 입력받아 나이트가 이동할 수 있는 경우의 수를 계산하는 프로그램을 작성하시오.

var input = readLine()!.map{String($0)}
var row = Int(input[1])!
var column = Int(exactly: Character(input[0]).asciiValue!)! - Int(Character("a").asciiValue!) + 1

let steps = [[-2, -1], [-1 , -2], [1 , -2], [2, -1], [2 , 1], [1, 2], [-1, -2], [-2, 1]]

var re = 0
var next_row = 0
var next_column = 0

for step in steps{
     next_row = row + step[0]
    next_column = column + step[1]
    
    if next_row >= 1 && next_row <= 8 && next_column >= 1 && next_column <= 8{
        re += 1
    }
}

print(re)

---

게임 개발

현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1x1 크기의 정사각형으로 이루어진 NxM 크기의 직사각형으로, 각 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.

맵의 각 칸은 (a, b)로 나타낼 수 있고, a는 북쪽으로부터 떨어진 칸의 개수, b는 서쪽으로부터 떨어진 칸의 개수이다.
캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어있는 공간은 갈 수 없다. 캐릭터 움직임 매뉴얼을 다음과 같다.
   
1. 현재 위치에서 형재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행 후 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가봤거나 바다라면, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다.
    3-1 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

매뉴얼에 따라 캐릭터를 이동시킨 뒤, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

var input = readLine()!.split(separator: " ").map{Int(String($0))!}
var n = input[0]
var m = input[1]

//방문한 위치를 저장하기 위한 맵을 생성
var d: [[Int]] = Array(repeating: Array(repeating: 0, count: m), count: n)

input = readLine()!.split(separator: " ").map{Int(String($0))!}
var x = input[0]
var y = input[1]
var direction = input[2]

//전체 맴 정보 입력받기
var arr: [[Int]] = Array(repeating: Array(repeating: 0, count: 0), count: n)
for i in 0..<n{
    arr[i].append(contentsOf: readLine()!.split(separator: " ").map{Int(String($0))!})
}


var dx = [-1, 0, 1, 0]
var dy = [0, 1, 0, -1]

//왼쪽으로 회전
func turn_left(){
    direction -= 1
    if direction == -1{
        direction = 3
    }
}

//시뮬레이션 시작
var count = 0
var turn_time = 0
var nx: Int = 0
var ny: Int = 0

while true{
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    
    //회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
    if d[nx][ny] == 0 && arr[nx][ny] == 0{
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    }else{
        turn_time += 1
    }
    
    //네 방향 모두 갈 수 없는 경우
    if turn_time == 4{
        nx = x - dx[direction]
        ny = y - dy[direction]
        
        //뒤로 갈 수 있다면 이동
        if arr[nx][ny] == 0{
            x = nx
            y = ny
        }
        //뒤가 바다로 막혀있는 경우
        else{
            break
        }
        turn_time = 0
    }
}

print(count)