[알고리즘] 구현

이번에 알아 볼 알고리즘은 구현이다.

구현 알고리즘이란?

- 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 알고리즘 문제를 풀이할 때 구현은 매우 필요하다.

모든 문제를 구현이라고 생각 할 수 있으나, 그 중 구현이 어렵거나 구현에 초점을 맞추는 문제들이 있다.

즉, 풀이를 떠올리기는 쉽지만 소스코드로 옮기기 어려운 문제라고 생각하면 된다.

 

예시

• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제
• 알고리즘은 간단한데, 코드가 길어지는 문제
• 시뮬레이션 문제
• 완전 탐색

완전탐색

- 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

 

시뮬레이션

- 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제

 

예제

https://www.acmicpc.net/problem/4396

4396번: 지뢰 찾기

지뢰 찾기 문제이다.

 

package baekjoon

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

/**
 * 아이디어 : 대각선까지, 지뢰가 놓여져 있는 갯수를 표시한다. 만약 지뢰가 있는 곳이 x라면, 지뢰가 있는 모든 칸이 *로 표시되어야 한다.
 * */
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val order = br.readLine().toInt()
    val array = Array(order) { CharArray(order) }    //맵
    val answer = Array(order) { CharArray(order) }   //결과값

    val dx = arrayOf(-1, -1, -1, 0, 0, 1, 1, 1)
    val dy = arrayOf(-1, 0, 1, 1, -1, 1, 0, -1)

    repeat(order) {
        array[it] = br.readLine().toCharArray()
    }

    repeat(order) {
        answer[it] = br.readLine().toCharArray()
    }

    var flag = false
    for(y in 0 until order){
        for(x in 0 until order){
            var count = 0
            if(answer[y][x] == 'x') {
                if(array[y][x] == '*'){
                    flag = true
                } else {
                    repeat(8) {
                        try {
                            if (array[y + dy[it]][x + dx[it]] == '*') {
                                count++
                            }
                        } catch (_: Exception) {
                        }
                    }
                    answer[y][x] = count.toChar() + '0'.code
                }
            }
        }
    }

    if(flag){
        for(y in 0 until order) {
            for (x in 0 until order) {
                if(array[y][x] == '*'){
                    answer[y][x] = '*'
                }
            }
        }
    }

        answer.forEach {
            it.forEach {c->
                bw.write("$c")
            }
            bw.write("\n")
        }
    bw.flush()
    bw.close()
}

 

문제 이해를 잘못해서 계속 틀렸었으나, 문제 이해에 도움을 주자면.

1. x위치에 지뢰가 없다면, 주변에 지뢰가 얼마나 있는지 판단한다.

2. x위치에 지뢰가 있다면, 지뢰가 있는 모든 곳들을 *로 표시한다. (숫자로 되어있는 곳들은 그대로 출력한다.)

 

이렇게 두 가지만 생각하고 풀면 될 것 같다.

2번을 잘 이해를 못 해서, 지뢰가 있으면 전체를 다 *과 .으로 바꾸는 헛짓을 했었다.

예제 추가

https://www.acmicpc.net/workbook/view/6783

문제집: 구현 (수정 : 2021-05-06) (tony9402)

구현 문제들을 모아둔 문제집이다.

참고하면 좋을 것 같다.

 

코드

https://github.com/Grusie/Solved

GitHub - Grusie/Solved: Solved Algorithm problems

후기

사실 구현 문제는 문제를 잘 이해하고, 풀어나가면 된다. 따로 준비 할 필요가 있는 부분은 아니고, 다른 문제들을 풀어보면서 익힌 기술들을 바탕으로 풀어나가면 될 것이다. 만약 문법을 잘 알지 못한다면, 문법 공부를 다시하고 진행해야 할 것이다.