[구현 - 시뮬레이션과 완전 탐색] 개요

2-2. [구현 - 시뮬레이션과 완전 탐색] 개요

 

• 구현: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

• 모든 알고리즘이 구현을 해야하는 문제이지만 보통 알고리즘 문제에서 구현 문제라고 한다면 어렵거나 구현에 초점을 맞춰진 유형이 있다고 보면 된다.

• 흔히 알고리즘 대회에서 구현 유형의 문제란 무엇을 의미할까?

• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

• 구현 유형의 예시

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 -> 이것은 자신이 사용하는 언어에 따라 달라질 수 있음

• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제

• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제

• 적절한 라이브러리를 찾아서 사용해야 하는 문제

 

• 이 강의에서는 구현 문제를 시뮬레이션과 완전탐색에 중점을 두고 다루고 있다

---

• 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다.

  

 

• 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

 

• 여기서 x = 세로축 y = 가로축
• 동의 경우 x=0, y=1 / 서의 경우 x=0, y=-1 / 남의 경우 x=1, y=0/ 북의 경우 x=-1, y=0 인 것이다.

---

<문제> 상하좌우

문제 설명

• 여행가 A는 N x N 크기의 정사각형 공간위에 있음. 이 공간은 1x1 크기의 정사각형으로 나누어져 있음. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당함. 여행가 A는 상,하,좌,우 방향으로 이동할 수 있으며, 시작 좌표는 항상(1,1)임. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있음.
• 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L,R,U,D 중 하나의 문자가 반복적으로 적혀있음. 각 문자의 의미는 다음과 같음
• L : 왼쪽으로 한 칸 이동
• R : 오른쪽으로 한 칸 이동
• U : 위로 한 칸 이동
• D : 아래로 한 칸 이동
• 이때 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시됨. 예를 들어 (1,1)의 위치에서 L 혹은 U을 만나면 무시됨. 다음은 N=5인 지도와 계획서임.

문제 해결 아이디어

• 이 문제는 요구사항대로 충실히 구현하면 되는 문제임
• 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션(Simulation)유형으로도 분류되며 구현이 중요한 대표적인 문제 유형임.
• 다만, 알고리즘 교재나 문제풀이 사이트에 따라서 다르게 일컬을 수도 있으므로, 코딩 테스트에서의 시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많다는 정도로만 기억

 

내가 작성한 코드 (자바스크립트)

const n = prompt("N: ");

const plans=[];

for(let i = 0; i < 100; i++){

  const plan = prompt("L,R,U,D중 하나를 적어주세요. (종료:e)");

  if(plan === 'e'){

    break;

  }

  plans.push(plan);

}

const dx = [0,0,-1,1]; // dx = 세로  LRUD서동북남 0,0,-1,1

const dy = [-1,1,0,0]; //dy = 가로  LRUD서동북남 -1,1,0,0

const move_types = ['L','R','U','D']



let x = 1;

let y = 1; //시작 지점

let nx,ny; //다음 지점

for(let i = 0; i < plans.length; i++){

    for(let j = 0; j < move_types.length; j++){

        if(plans[i] === move_types[j]){

            nx = x + dx[j];

            ny = y + dy[j];

            if(nx < 1 | ny < 1 | nx > n | ny > n)

                continue;

            

            x = nx;

            y = ny;

        }

    }

    

    console.log(`${i+1}번째: ${plans[i]}, ( x: ${x} , y: ${y} )`);

}



console.log(`${nx} ${ny}`);

 

 

또 다른 풀이법

const n = prompt("N: ");
const plans=[];
for(let i = 0; i < 100; i++){
  const plan = prompt("L,R,U,D중 하나를 적어주세요. (종료:e)");
  if(plan === 'e'){
    break;
  }
  plans.push(plan);
}
const move_types = ['L','R','U','D']
const move_calc = [[0,-1],[0,1],[-1,0],[1,0]]; // 순서대로 L,R,U,D

let x = 1;
let y = 1; //시작 지점
let nx,ny; //다음 지점
for(let i = 0; i < plans.length; i++){
    for(let j = 0; j < move_types.length; j++){
        if(plans[i] === move_types[j]){
            nx = x + move_calc[j][0];
            ny = y + move_calc[j][1];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= n)
                {
                    x = nx;
                    y = ny;
                }
            
            
        }
    }
    
    console.log(`${i+1}번째: ${plans[i]}, ( x: ${x} , y: ${y} )`);
}

console.log(`${nx} ${ny}`);

위의 풀이랑 다른 점?

- 원래는 dx와 dy로 배열을 각각 두개를 만들어서 방향에 따른 좌표 움직임을 만들었다면 그냥 2차원배열로 한꺼번에 move_calc 배열을 만들었다. L R U D와 인덱스가 똑같게 배열하는 것이다.
(row,col)이라 했을때 L의 경우 행은 그대로, 열은 -1 이므로 (0,-1)이라고 표기한 것이다.

- 원래는 1보다 작아지거나 n을 넘어갔을 때 반복문을 continue했다면 아래 코드는 nx와 ny의 범위가 1~n일때에만

nx와 ny의 값을 x,y로 반영해주어서 다음 반복문에서 x,y 값이 바뀌어있으니까 누적될 수 있는 것이다.

(nx,ny의 값이 어떤 값으로 나왔던 x,y에 반영해주지 않으면 다음 반복문에서 이전과 똑같이 나온다.)