[알고리즘 공부] 구현

구현 (Implementation)

 

 <이코테>에서 제공하는 공부 방법에 따라서 이번에는 "구현"에 대해서 살펴보도록 하겠습니다. 먼저 "구현"이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이라고 정의되어 있습니다. 이 유형의 문제들은 일반적으로 알고리즘과 자료구조의 복잡한 이론보다는 문제의 조건을 코드로 어떻게 표현할지에 더 초점을 맞추고 있습니다. 즉, 이 유형을 풀기 위해서는 문제를 해결하기 위한 아이디어를 코드로 변환하는 과정에서 세심함과 정확성이 중요합니다. 

 

구현 문제의 유형

1. 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차근차근 직접 수행하는 경우. 예를 들어, 특정 규칙에 따라 문제를 변환하거나, 보드 게임의 규칙을 시뮬레이션하는 등의 문제가 이에 해당
2. 완전 탐색 : 가능한 모든 경우의 수를 일일이 검사하여 정답을 찾는 방식. 브루트 포스(Brute Fource)라고도 불리며, 문제의 규모가 크지 않을 때 사용

---

문제 : 상하 좌우

 

문제 : 여행가 A는 NxN 크기의 정사각형 공간에 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 그의 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 있다. 

= 계획서가 주어졌을 때, 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오. 

입력 조건 
- 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1<= N <= 100)
- 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다 (1<= 이동 횟수 <= 100)

출력 조건 
- 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다. 

입력 예시 
5
R R R U D D

출력 예시
3 4

 

 

---

문제 풀이

 

 오랜만에 보는 구현 문제였습니다. 상하좌우 이동하는 건 삼성 코딩 테스트에서 많이 보았던 문제였는 데 이제는 문제 구경은 그만하고 당당히 코테에 합격하고 싶습니다ㅠㅠ. 잡담은 여기까지하고! 코드를 보면서 어떻게 문제를 풀었는지 확인하도록 하겠습니다. 

 

# 공간의 크기 입력받기
space_size = int(input())
move_plan = input().split()
position_x, position_y = 1, 1

# 각 방향에 따른 x, y의 변화량
delta_x = [0, 0, -1, 1]
delta_y = [-1, 1, 0, 0]
directions = ['L', 'R', 'U', 'D']

# 이동 계획 확인
for plan in move_plan:
    # 이동 후 좌표 계산
    for i in range(len(directions)):
        if plan == directions[i]:
            next_x = position_x + delta_x[i]
            next_y = position_y + delta_y[i]
    # 공간을 벗어나는 경우 무시
    if next_x < 1 or next_y < 1 or next_x > space_size or next_y > space_size:
        continue
    # 이동 수행
    position_x, position_y = next_x, next_y

print(position_x, position_y)

 

1. 입력 받기 

• space_size = int(input()) 은 사용자로부터 공간의 크기를 나타내는 정수 N을 입력 받습니다. 
• move_plan = input().split() 은 사용자로부터 여행가 A의 이동 계획이 담긴 문자열을 입력받아 공백을 기준으로 분리한 후 리스트에 저장합니다. 

2. 초기 위치 설정

• position_x, position_y = 1, 1은 여행가 A의 시작 위치를 (1, 1)로 초기화합니다. 

3. 이동 방향 설정

• delta_x = [0 0 -1 1] 와 delta_y= [-1 1 0 0] 과 같은 배열은 여행가 A가 각 방향으로 이동할 때 x좌표와 y좌표가 어떻게 변화하는지 나타냅니다.
• directions = [L R U D]는 가능한 이동 방향을 나타내는 배열입니다. 여행가는 L, R, U D를 이동할 수 잇습니다. 

4. 이동 계획 수행 

• for plan in move_plan : 이동 계획서에 있는 각 계획 순회
• for 루프에서 directions 배열을 사용하여 현재 계획이 어떤 방향인지 확인하고 해당 방향으로 이동했을 때의 새로운 위치를 계산
• 이동 후의 새 위치가 공간의 범위를 벗어나지 않는지 확인 >> 범위를 벗어나지 않는 경우 새로운 위치로 업데이트

5. 최종 위치 출력

 

마무리

 여기까지 "구현" 문제 중 "시뮬레이션"의 유형을 풀어보았습니다. dx, dy를 이용한 문제는 정말 많이 출제되는 유형 중 하나이니 처음부터 차분하게 풀어보시는 것을 추천드립니다. 하루에 딱 2 문제만 풀기로 스스로 다짐해보았는 데... 아직까지 갈 길이 멀고 먼 것 같습니다. 하지만 포기하지 않고 꾸준하게 풀어보는 것이 정말 중요하겠지요? 이대로 가면서 이코테 한 바퀴를 돌리고 PCCE와 PCCP에 도전해봐야겠습니다. 그럼 오늘의 알고리즘 공부는 여기까지 마치도록 하겠습니다. 

 

 

 

참고

2023.12.08 - [IT/관련 정보] - [코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬

[코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬