Implementation Algorithm
구현이란, 머릿속에 Algorithm을 소스코드로 바꾸는 과정을 의미한다.
대표적으로 아래와 같은 문제들이 구현 문제에 속한다.
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
Example
일반적인 Algorithm 문제의 2차원 공간은 행렬(Matrix)을 의미한다.
for (let i = 0; i < 5; i++) {
for (let j = 0; j < 5; j++) {
console.log(`(${i}, ${j})`);
}
}특히 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간의 방향 벡터가 자주 활용된다.
// 동, 북, 서, 남
const dx = [0,-1,0,1];
const dy = [1,0,-1,0];
// 현재 위치
let x = 2;
let y = 2;
for (let i = 0; i < 4; i++) {
let nx = 0;
let ny = 0;
// 다음 위치
nx = x + dx[i]
ny = y + dy[i]
console.log(nx, ny);
}Problem 1, 상하좌우
여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다.
이 공간은 1 X 1 크기의 정사각형으로 나누어져 있으며, 가장 왼쪽 위 좌표는 (1, 1), 가장 오른쪽 아래 좌표는 (N, N)에 해당한다.
여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있을 때 시작 좌표는 항상 (1, 1)이다.
계획서는 여행가 A가 이동할 계획이며, 계획서 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다.
각 문자의 의미는 다음과 같다.
L: 왼쪽으로 한 칸 이동
R: 오른쪽으로 한 칸 이동
U: 위로 한 칸 이동
D: 아래로 한 칸 이동
이때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.
예를 들어
(1, 1)의 위치에서L혹은U를 만나면 무시한다.
Explanation
// N 입력
const N = 5;
const cmd = ['R', 'R', 'R', 'U', 'D', 'D'];
let x = 1;
let y = 1;
// L, R, U, D에 따른 이동 방향
const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];
const moveTypes = ['L', 'R', 'U', 'D'];
// 이동 계획 확인
for (let i = 0; i < cmd.length; i++) {
let nx = -1;
let ny = -1;
// 이동 후 좌표
for (let j = 0; j < moveTypes.length; j++) {
if (cmd[i] === moveTypes[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(x, y);Problem 2, 시각
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.
예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.
- 00시 00분 03초
- 00시 13분 30초
Explanation
이러한 유형은 완전 탐색(Brute Forcing) 문제 유형이라고 하며, 이는 가능한 모든 경우의 수를 검사하는 탐색 방법을 의미한다.
// N, count 입력
const N = 1;
let count = 0;
function check(h, m, s) {
// 문자열에 특정 문자열이 포함되어있는지 확인
if (h % 10 === 3 || m / 10 === 3 || m % 10 === 3 || s / 10 === 3 || s % 10 === 3) {
return true;
}
return false;
}
for (let i = 0; i <= N; i++) {
for (let j = 0; j < 60; j++) {
for (let k = 0; k < 60; k++) {
// 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
if (check(i, j, k)) count++;
}
}
}
console.log(count);Problem 3, 왕실의 나이트
행복 왕국의 왕실 정원은 체스판과 같은 8 X 8 좌표 평면이다.
왕실 정원의 특정한 한 칸에 나이트가 서 있고, 해당 나이트는 말을 타고 있기 때문에 이동할 때는 L자 형태로만 이동할 수 있다.
단, 정원 밖으로는 이동할 수 없다.
나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동
왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.
Explanation
// 현재 나이트의 위치 입력
const input = ['a', 1];
const row = input[1];
const col = input[0].charCodeAt(0) - 96;
// 나이트가 이동할 수 있는 8가지 방향 정의
const step = [[-2, -1], [-1, -2], [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1]];
let count = 0;
// 가지 방향에 대하여 각 위치로 이동이 가능한지 확인
for (let i = 0; i < step.length; i++) {
// 이동하고자 하는 위치 확인
const [stepRow, stepCol] = step[i];
const nextRow = row + stepRow;
const nextCol = col + stepCol;
// 해당 위치로 이동이 가능하다면 카운트 증가
if ((nextRow >= 1 && nextRow <= 8) && (nextCol >= 1 && nextCol <= 8)) {
count++;
}
}
console.log(count);Problem 4, 문자열 재정렬
알파벳 대문자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어진다.
이 때 모든 알파벳을 오름차순으로 정렬한 뒤 모든 숫자를 더한 값을 이어서 출력한다.
리스트에 저장된 알파벳을 정렬해 출력하고, 합계를 뒤에 붙여 출력하면 정답
Explanation
// 입력 받기
const input = 'K1KA5CB7';
let str = [];
let sum = 0;
let result = '';
// 문자를 하나씩 확인
for (let i = 0; i < input.length; i++) {
if (input[i].charCodeAt(0) >= 65 && input[i].charCodeAt(0) <= 90) {
// 알파벳인 경우 결과 리스트에 삽입
str.push(input[i]);
} else {
// 숫자는 따로 더하기
sum += (+input[i]);
}
}
// 알파벳을 오름차순으로 정렬한 뒤 숫자 합계를 추가
result += (str.sort().join('') + sum);
console.log(result);참고 자료
