코딩 테스트 준비 기록 - Day 3

구현 Algorithm

구현이란?

머릿 속에 있는 문제 해결 알고리즘을 소스코드로 바꾸는 과정.

• 예시 : 문자열 처리, 알고리즘은 간단한데 코드가 길어지는 문제, 실수 표현 문제
• 문제를 찬찬히 읽어가며 요구사항에 맞게 구현하면 되는 문제이므로 난이도가 그리 높지는 않은 편임.
• 구현 파트 내에 시뮬레이션, 완전 탐색 문제가 포함됨.
• 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 문제 해결이 많이 요구되는데 이 때 방향 벡터가 주로 사용됨.
  - ex) dx = [0, -1, 0, 1], dy = [1, 0 .-1. 0]

💡 문제 1. 상하좌우

• 사용자로부터 커맨드를 입력 받아 최종 위치 좌표를 출력하는 문제
• 방향 벡터를 활용하여 문제 해결
• 문제 해결 코드

def main():
    matrix_size = int(input())
    commands = input().split()

    # x, y 초기화
    x, y = 0, 0
    # x, y 좌표 변화 리스트
    #     좌 우 상 하
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    command_types = ['L', 'R', 'U', 'D']

    for command in commands:
        for i in range(len(command_types)):
            if command == command_types[i]:
                nx = x + dx[i]
                ny = y + dy[i]

        if nx < 0 or ny < 0 or nx >= matrix_size or ny >= matrix_size:
            # out of range error
            continue
        # 실제 이동 수행
        x, y = nx, ny

    print(x,y)

if __name__ == "__main__":
    main()

https://github.com/ybkim-dev/algorithms/blob/master/구현/상하좌우%20without%20mem%20cache.py

💡 문제 2. 시각

• 0 ~ N시 59분 59초까지의 시각 중 3이 들어간 경우의 수를 구하는 문제
• 모든 시각을 3중 for문을 돌며 문자열 처리를 통해 '3'을 찾아 해결 (Brute forcing)
• 참고 : python은 1초에 대략 2000만 번의 연산 수행 가능하고 24 x 60 x 60 = 86400 이므로 연산 가능
• 문제 해결 코드

def main():
    # 3이 하나라도 포함되는 경우의 수 구하기
    n = int(input())

    count = 0
    # 0 ~ N 시 59분 59초까지 3이 포함되는 경우.
    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)

if __name__ == "__main__":
    main()

https://github.com/ybkim-dev/algorithms/blob/master/구현/시각.py

💡 문제 3. 왕실의 나이트

• 체스게임의 나이트가 주어진 위치에서 이동할 수 있는 경우의 수 구하는 문제
• dx, dy 방향 벡터를 만들어서 해결하거나 이를 합쳐 2차원 배열을 생성하여 문제 해결
• 'a1' 문자열을 입력받아 'a'를 1로 파악하는 int(ord(character)) - int(ord('a') + 1을 생각해내야 함.
• 참고 : ord() : 문자를 아스키 코드 값으로 반환 <==> chr()
• 문제 해결 코드

def main():
    # 나이트의 이동 가능 경우의 수 구하기
    knight_point = input()
    row = int(ord(knight_point[0])) - int(ord('a')) + 1
    col = int(knight_point[1])

    # 나이트의 이동 가능 row, col 좌표
    d_row = [2, 1, -1, -2, -2, -1, 1, 2]
    d_col = [1, 2, 2, 1, -1, -2, -2, -1]
    count = 0
    for i in range(len(d_row)):
        nx = row + d_row[i]
        ny = col + d_col[i]
        # out of range error.
        if nx <= 0 or nx > 8 or ny <= 0 or ny > 8:
            continue
        else:
            count += 1
    print(count)

if __name__ == "__main__":
    main()

https://github.com/ybkim-dev/algorithms/blob/master/구현/왕실의%20나이트.py

💡 문제 4. 문자열 재정렬

• 알파벳, 숫자를 입력받아 알파벳은 알파벳 순으로 정렬하고 숫자는 합계를 구하는 문제
• 알파벳과 숫자를 분류하여 각각 연산하여 해결
• 문제 해결 코드

s = input()

string_list = []
number_list = []
for i in range(len(s)):
    # 문자열이면 문자열 리스트에 담기
    if s[i].isalpha():
        string_list.append(s[i])
    # 숫자면 숫자 리스트에 담기
    else:
        number_list.append(s[i])

# 문자열 정렬
string_list.sort()
# 숫자 합
sum = 0
for number in number_list:
    sum += int(number)

for i in range(len(string_list)):
    print(string_list[i], end='')
print(sum)

https://github.com/ybkim-dev/algorithms/blob/master/구현/문자열%20재정렬.py