구현

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 의 책과 강의를 보고 정리한 글입니다.
강의 출처 : https://www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw

구현: 시뮬레이션과 완전 탐색

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

• problem - thinking - solution

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 말한다.

구현 유형의 예시

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제 - 모든 순열과 모든 조합을 구하는 문제

구현(Implementation)

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

예를 들어 2차원 맵의 한 좌표에 존재하는 캐릭터가 반복적으로 어떤 위치로 이동한다고 했을 때 적절히 해결하기 위해 행렬에 대한 개념이 필요하다.

• 행렬 : 2차원 데이터를 일종의 표와 같은 캐릭터로 쉽게 나타낼 수 있게 하는 수학적 개념. (파이썬에서는 2차원 리스트)

시뮬레이션 및 완전 탐색 문제에서는 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)

    # 2 3 동
    # 1 2 북
    # 2 1 서
    # 3 2 남

상하좌우 문제

여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다.
<이동 계획서>
하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다.

입력 조건

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

출력 조건

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

# 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)

시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)

출력 조건

• 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

<해결 아이디어>
가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제
하루는 86,400초이므로, 00시 00분 00초부터 23시 59분 59초까지이 모든 경우는 86,400가지 이다. 따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지를 확인하면 된다.

• 이러한 유형은 완전 탐색(Brute Forcing) 문제 유형이라고 불린다. 가능한 경우의 수를 모두 검사해보는 탐색 방법이다.

N = int(input(""))

count = 0

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

print(count)

왕실의 나이트

왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다. 나이트는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다.

나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동 가능하다.
1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하시오.

입력 조건

• 첫째 줄에 현재 나이트 위치 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다.

출력 조건

• 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력한다.

point = input("")

points = [point[0], point[1]]

dx = [2, 2, -2, -2, 1, -1, 1, -1]
dy = [1, -1, 1, -1, 2, 2, -2, -2]

x, y = (ord(points[0])-ord('a') + 1), int(points[1])

count = 0

for i in range(8):
    nx = x + dx[i]
    ny = y + dy[i]
    if nx < 1 or ny < 1 or nx > 8 or ny > 8:
        continue
    count += 1

print(count)

문자열 재정렬

알파벳 대분자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모듣ㄴ 숫자를 더한 값을 일어서 출력한다.

ex) K1KA5CB7 -> ABCKK13

입력 조건

• 첫째 줄에 하나의 문자열 S가 주어진다. (1<=S의 길이<=10,000)

a = list(input(""))

b = []
sum = 0

for i in a:
    if 65 <= ord(i) <= 90:  # i.isalpha()
        b.append(i)
    elif 48 <= ord(i) <= 57:
        sum += int(i)

# b.sort()
# for i in b:
#     print(i, end="")
# print(sum)

b.sort()
if sum != 0:
    b.append(str(sum))

print(''.join(b))