[이코테] 4. 구현(Implementation) 유형 설명 및 예제 문제(상하좌우)

 

 

 

 

 

 

구현(Implementation)이란?

---

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

• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭
• 구현 유형의 예시
  • 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
    • 이 부분은 프로그래밍 언어를 어떤 것을 사용하느냐에 따라 달라짐.
  • 실수 연산을 다루고, 특정 소수점 자리까지 출력해야하는 문제
  • 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
  • 적절한 라이브러리를 찾아서 사용해야 하는 문제
    • 모든 순열과 조합을 찾는 문제를 파이썬에서는 itertools 라이브러리를 이용해서 매우 간결히 작성 가능.

 

 

 

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

여기서 유의할 점은 행과 열의 축방향, (0, 0)의 위치이다.

• 열 : 오른쪽 이동 = 열 index 증가
• 행 : 아래쪽 이동  = 행 index 증가
• (0, 0) 위치 : 왼쪽 위

 

 

 

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

dx = 행(세로 축), dy = 열(가로 축)

 

 

 

 

 

예제) 상하좌우 문제

---

 

 

 

 

 

 

문제 해결 아이디어

---

 

 

 

 

 

 

정답

---

# N 입력 받기
n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인하기
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    x, y = nx, ny

print(x, y)

'''output
10
R R D D R R R D D D
6 6
'''

사람, 사물이 있고 이동하는 경우의 문제는

2차원 행렬로 해결하며,

아래 code가 baseline이라고 할 수 있겠다.

 

 

 

 

 

 

 

 

 

이코테 2021 시리즈 씹어먹기 by 조랭이떡

시리즈 목차

1. 코딩테스트 출제 경향 및 알고리즘 성능 평가
2. 파이썬 문법 부수기
   1. 수, 리스트 자료형
   2. 문자열, 튜플, 사전, 집합 자료형
   3. 기본 입출력
   4. 조건문
   5. 반복문
   6. 함수와 람다 표현식
   7. 자주 사용되는 표준 라이브러리
3. 그리디
   1. 그리디 알고리즘이란?
   2. 거스름돈
   3. 1이 될 때 까지
   4. 곱하기 혹은 더하기
   5. 모험가 길드
4. 구현
5. DFS & BFS (추후링크)
6. 정렬 알고리즘 (추후링크)
7. 이진 탐색 (추후링크)
8. 다이나믹 프로그래밍 (추후링크)
9. 최단 경로 알고리즘 (추후링크)
10. 기타 그래프 이론 (추후링크)
11. 코딩 테스트에서 자주 출제되는 기타 알고리즘 (추후링크)
12. 개발형 코딩 테스트 (추후링크)