14~15강 :: 구현 유형 개요 및 문제 풀이

Python/이것이코딩테스트다with파이썬

14~15강 :: 구현 유형 개요 및 문제 풀이

묘걍 2023. 11. 15. 19:58

👉🏻 구현 (Implementation)

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

- 아무리 알고리즘을 잘 세워도 실제로 코드로 작성해서 프로그램으로 만들지 않으면 알고리즘이 실제로 동작하지 않는다

- 알고리즘 문제를 푸는 과정에서 구현은 반드시 필요한 과정

- 그래서 모든 문제가 구현 유형이라고 할 수 있긴 하다

- 하지만 특별히 '구현 유형'이라고 부르는 것은 문제에서 요구하는 내용이 구현에 맞춰져 있거나 구현이 어려운 문제

흔히 알고리즘 대회에서 구현 유형의 문제란 무엇을 의미할까?
- 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭
구현 유형의 예시
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야하는 문제
- 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야하는 문제

- 적절한 라이브러리를 알지 못할 경우 하나하나 다 구현해야해서 난이도가 높아짐

- 대표적으로 모든 순열, 모든 조합을 찾는 문제

- 파이썬에서는 itertools라이브러리

- 많은 연습이 필요

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

- 2D 게임 개발 등에서 이차원 공간을 행렬 같은 형태로 표현해 내부적으로 처리

- 코테에서도 다양한 시뮬레이션 문제에서 2차원 공간을 가정하는 상황 많이 등장

- Ex. 2차원 맵(map) 상 한 좌표에 존재하는 캐릭터가 반복적으로 어떤 위치로 이동한다

- 행렬(Matrix): 2차원 데이터를 일종의 표와 같은 형태로 쉽게 나타내줄 수 있는 수학 개념 중 하나

- 2차원 배열과 동일

- 2차원 리스트와 동일

- 왼쪽 위((0,0))부터

오른쪽으로 갈 수록 열 위치(인덱스)가 증가

아래로 갈 수록 행 인덱스가 증가

- 완전탐색, 시뮬레이션 문제를 접할 때 문제에서 정의하는 내용을 확인해보면 가장 왼쪽 위 위치를 (0,0)으로 부르는 경우가 많다

- 옛날에 배웠던 x축, y축 개념과 다를 수 있음

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

- 특정 캐릭터나 사물 등이 특정 위치에 존재했다가 상하좌우로 이동할 수 있다는 등의 문제상황

- 특정 위치에서 위로 이동한다면 행 데이터가 1만큼 감소한다

- 동북서남 각각의 방향 벡터를 정할 수 있음

- x는 세로축(행), y는 가로축(열)

- 동: 행은 가만히, 열을 오른쪽으로 한 칸 이동

- 북: 행을 한칸 위로 이동, 열은 가만히

- 서: 행은 가만히, 열을 왼쪽으로 한 칸 이동

- 남: 행을 한 칸 아래로, 열은 가만히

👉🏻 문제1: 상하좌우

🧩 문제 설명

- 문제에서 가장 왼쪽 위가 (1,1)이라고 명시했다면

- 첫 번째 인덱스는 사용하지 않는 방식을 택하거나

- (1,1)을 (0,0)인 것 처럼 처리하도록 소스코드를 작성하거나

🧩 문제 조건

💡 스스로 풀어보기

N = int(input())
move = list(input().split())
map_ = [(N, N), " "]
x = 1
y = 1
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
nx = 0
ny = 0

for i in move:
    if i == "R":
        nx = x + dx[0]
        ny = y + dy[0]
        if nx > N or ny > N:
            continue
        else:
            x += dx[0]
            y += dy[0]
    elif i == "U":
        nx = x + dx[1]
        ny = y + dy[1]
        if nx > N or ny > N:
            continue
        else:
            x += dx[1]
            y += dy[1]
    elif i == "L":
        nx = x + dx[2]
        ny = y + dy[2]
        if nx > N or ny > N:
            continue
        else:
            x += dx[2]
            y += dy[2]
    else:
        nx = x + dx[3]
        ny = y + dy[3]
        if nx > N or ny > N:
            continue
        else:
            x += dx[3]
            y += dy[3]

print(x, y)

- 반복되는 부분은 함수로 뺄 수 있으면 빼야겠다

- 일단 답이 안 나왔다

🧩 문제 해결 아이디어

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

💡 예시 답안

- 현재 위치를 의미하는 x, y 초기화 및 주어지는 N과 계획 입력 받기

- 방향 벡터 설정

- 이동 가능한 문자는 정해져있기 때문에이것들을 리스트로 만들어준다

- 계획서 내의 이동 계획을 하나씩 확인하며

- 이동 가능한 문자 리스트 내에 일치하는 것의 인덱스를 활용해 이동 후 좌표 구하기

- 다음 위치가 범위를 벗어나지 않는다면 이동을 수행한다

* C++ ver

* Java ver

https://github.com/ndb796/python-for-coding-test/blob/master/4/1.java