구현

Lee Sang Hyuk·2022년 1월 8일

Algorithm

목록 보기

2/6

구현

책에서는 '완전 탐색', '시뮬레이션' 유형에 대해서 모두 구현으로 구분하였습니다. '완전 탐색'은 모든 경우의 수를 계산하는 해결 방법이며, '시뮬레이션'은 문제에서 제시한 방법을 한 단계씩 차례대로 해결하는 방법입니다.

구현에서 중요시 해야 하는 것

메모리 제약에 대해서 확인해야 할 필요 있습니다. 자료형에 따른 변수 선언(int형, long형), 리스트 크기(파이썬에서 해당)에 대해서 고려해야 할 필요있다.

데이터의 개수	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

문제 및 풀이

문제 1. 상하좌우

n = int(input())
movement = input().split()

move_guide = ['L', 'R', 'U', 'D']
move_x = [0, 0, -1, 1]
move_y = [-1, 1, 0, 0]

x, y = 1, 1

for move in movement:
    for i in range(len(move_guide)):
        if(move == move_guide[i]):
            check_x = x + move_x[i]
            check_y = y + move_y[i]
    if(check_x < 1 or check_x > n or check_y < 1 or check_y > n):
        continue
    x, y = check_x, check_y

print(x, y)

const solution = (n, arr) => {
    // 좌, 우, 상, 하
    let dx = [-1, 1, 0, 0];
    let dy = [0, 0, -1, 1];
    let move = [1, 1];
    arr.forEach((m) => {
        let check = -1;
        switch (m) {
            case 'L':
                check = 0;
                break;
            case 'R':
                check = 1;
                break;
            case 'U':
                check = 2;
                break;
            case 'D':
                check = 3;
                break;
            default:
                break;
        }
        let cx = move[1] + dx[check];
        let cy = move[0] + dy[check];
        if (cx >= 1 && cy >= 1 && cx <= n && cy <= n) {
            move[1] = cx;
            move[0] = cy;
        }
    });
    return move.join(' ');
}

let arr = ['R', 'R', 'R', 'U', 'D', 'D'];
console.log(solution(5, arr));

sanghyuk-2i/Algorithm

Algorithm/avatar_1.js at main · sanghyuk-2i/Algorithm

문제 2. 시각

n = int(input())
count = 0

for i in range(n + 1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

const solution = (n) => {
    let count = 0;

    for (let i = 0; i <= n; i++) {
        for (let j = 0; j < 60; j++) {
            for (let k = 0; k < 60; k++) {
                let check = `${i}${j}${k}`;
                if (check.includes('3')) {
                    count++;
                }
            }
        }
    }

    return count;
}

console.log(solution(5));

sanghyuk-2i/Algorithm

Algorithm/avatar_2.js at main · sanghyuk-2i/Algorithm

문제 3. 왕실의 나이트

n = input()
col, row = int(ord(n[0]) - ord('a')) + 1, int(n[1])

movement = [(2, -1), (2, 1), (-2, -1), (-2, 1),
            (1, 2), (1, -2), (-1, 2), (-1, -2)]

count = 0

for move in movement:
    check_col = col + move[0]
    check_row = row + move[1]
    if(check_col < 1 or check_row < 1 or check_col > 8 or check_row > 8):
        continue
    count += 1

print(count)

const solution = (str) => {
    let one = str.charCodeAt(0) - 'a'.charCodeAt(0);
    let two = Number(str[1]) - 1;

    let movement = [[-2, 1], [-2, -1], [2, 1], [2, -1], [1, -2], [1, 2], [-1, -2], [-1, 2]];

    let count = 0;
    movement.forEach((move) => {
        let cx = one + move[0];
        let cy = two + move[1];
        if (cx >= 0 && cy >= 0 && cx <= 7 && cy <= 7) {
            count++;
        }
    });

    return count;
}

console.log(solution('c2'));

sanghyuk-2i/Algorithm

Algorithm/avatar_3.js at main · sanghyuk-2i/Algorithm

문제 4. 게임 개발

n, m = map(int, input().split())
a, b, d = map(int, input().split())

move = [[0] * m for _ in range(n)]
move[a][b] = 1

move_x = [-1, 0, 1, 0]
move_y = [0, 1, 0, -1]

map_state = list()
for i in range(m):
    map_state.append(list(map(int, input().split())))

for i in map_state:
    print(i)

def turn_left():
    global d
    d -= 1
    if(d == -1):
        d = 3

count, turn = 1, 0
while(True):
    turn_left()
    check_x = a + move_x[d]
    check_y = b + move_y[d]
    print(check_x, check_y, turn)
    if(move[check_x][check_y] == 0 and map_state[check_x][check_y] == 0):
        move[check_x][check_y] = 1
        a += check_x
        b += check_y
        count += 1
        turn = 0
        continue
    else:
        turn += 1
    if(turn == 4):
        check_x = a - move_x[d]
        check_y = b - move_y[d]
        if(map_state[check_x][check_y] == 0):
            a += check_x
            b += check_y
        else:
            break
        turn = 0

print(count)

const solution = (n, arr, arr2) => {
    // 북동남서
    let check_arr = Array.from({ length: n }, () => Array(n).fill(0));
    let move = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    const rotateLeft = () => {
        arr2[2]--;
        if (arr2[2] === -1) {
            arr2[2] = 3;
        }
    }
    let count = 1;
    let check_turn = 0;
    while (true) {
        rotateLeft();
        let nx = arr2[0] + move[arr2[2]][0];
        let ny = arr2[1] + move[arr2[2]][1];
        if (check_arr[nx][ny] === 0 && arr[nx][ny] === 0) {
            check_arr[nx][ny] = 1;
            arr2[0] = nx;
            arr2[1] = ny;
            count++;
            check_turn = 0;
            continue;
        } else {
            check_turn++;
        }

        if (check_turn === 4) {
            nx = arr2[0] - move[arr2[2]][0];
            ny = arr2[1] - move[arr2[2]][1];
            if (check_arr[nx][ny] === 0) {
                arr2[0] = nx;
                arr2[1] = ny;
            } else {
                break;
            }
            check_turn = 0;
        }
    }

    return count;
}

let arr2 = [1, 1, 0];
let arr = [
    [1, 1, 1, 1],
    [1, 0, 0, 1],
    [1, 1, 0, 1],
    [1, 1, 1, 1]
];
console.log(solution(4, arr, arr2));