강의 : https://www.youtube.com/watch?v=2zjoKjt97vQ&t=702s
코드 : https://github.com/soy53/Algorithm/tree/main/test/Implement
2. 구현
- 구현이란? 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 특히 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다.
- 종류
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제 (ex. 모든 순열, 조합 구하기)
- 유형
- 완전 탐색 : 모든 경우의 수를 다 계산하는 해결 방법
- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법
- 2차원 공간 - 행렬(Matrix)
for i in range(5):
for j in range(5):
print('(', i, ',', j, ')', end=' ')
print()- 2차원 공간에서의 방향벡터
dx = [0, -1, 0, 1] # 오, 위, 왼, 아래(함수 아님. 방향 주의!)
dy = [1, 0, -1, 0]
x, y = 2, 2 # 현재 위치
for i in range(4): # 다음 위치
nx = x + dx[i]
ny = y + dy[i]
print(nx, ny)문제 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를 만나면 무시된다.
계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 ≤ N ≤ 100)
- 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 ≤ 이동 횟수 ≤ 100)
출력 조건
- 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.
입력 예시 : 5 | R R R U D D // 출력 예시 : 3 4
해결방법
- U, D, R, L에 해당하는 리스트 만들기
- 리스트 인덱싱 통해서 값 업데이트
- 공간 벗어나면 적용될 수 없도록 만들기
정답
n = int(input())
plans = list(input().split())
x, y = 1, 1
dx = [-1, 1, 0, 0] # 위, 아래, 왼, 오
dy = [0, 0, -1, 1] # 위, 아래, 왼, 오
move_types = ['U', 'D', 'L', 'R']
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
x, y = nx, ny
print(x, y)문제 2. 시각(완전탐색 유형)
문제
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 정수 N이 입력된다. (0 ≤ N ≤ 23)
출력 조건
- 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.
입력 예시 : 5 // 출력 예시 : 11475
해결 방법
- 00시 00분 00초부터 23시 59분 59초까지 모든 경우를 고려하는 3중 반복문을 이용한다.
- 시, 분, 초를 문자열로 바꾼 뒤 합쳐 그 문자열 안에 '3'이라는 문자열이 있는지 확인한다.
정답
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)문제 3.
문제
왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
- 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
- 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기
이처럼 8 x 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.
입력 조건
- 첫째 줄에 8 x 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1 처럼 열과 행으로 이뤄진다.
출력 조건
- 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.
입력 예시 : a1 // 출력 예시 : 2
해결 방법
- a1 등 입력 문자를 행과 열 순서의 숫자로 바꾼다.
- 나이트가 이동할 수 있는 방향벡터를 만들어준 뒤, 나이트가 위치한 곳에서 방향벡터를 적용한다.
- 방향벡터 적용 후 위치(행과 열)가 1 ~ 8 사이라면 경우의 수에 추가한다.
정답
n = input()
row = int(n[1])
column = int(ord(n[0])) - int(ord('a')) + 1
# 나이트 이동 방향벡터
steps = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
count = 0
for step in steps:
next_row = row + step[0]
next_column = column + step[1]
if 1 <= next_row <= 8 and 1 <= next_column <= 8:
count += 1
print(count)- ord('문자') : 하나의 문자를 인자로 받고 해당 문자에 해당하는 유니코드 정수를 반환한다.
문제 4.
문제
알파벳 대문자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다. 예를 들어 K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력한다.
입력 조건
- 첫째 줄에 하나의 문자열 S가 주어진다. (1 ≤ S의 길이 ≤ 10,000)
출력 조건
- 첫째 줄에 문제에서 요구하는 정답을 출력한다.
입력 예시 : AJKDLSI412K4JSJ9D // 출력 예시 : ADDIJJJKKLSS20
해결 방법
- for문을 사용하여 문자는 리스트에 넣고, 숫자는 더한다.
- 문자 리스트를 오름차순으로 정렬한다.
- 리스트를 문자열로 다시 뽑아내고, 더한 숫자가 0이 아니라면 문자열 뒤에 붙인다.
정답
data = input()
result = []
value = 0
for i in data:
if i.isalpha():
result.append(i)
else:
value += i
result.sort()
if value != 0:
print(''.join(result) + str(value))