junior/알고리즘

구현(Implementation)

johh 2023. 1. 6. 08:07

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

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

 

문제1

  • 여행가 A는 N * N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 * 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동 할 계획이 적힌 계획서가 놓여 있다.
  • 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는 다음과 같다.
    • L: 왼쪽으로 한 칸 이동
    • R: 오른쪽으로 한 칸 이동
    • U: 위로 한 칸 이동
    • D: 아래로 한 칸 이동
  • 이때 여행가 A가 N * N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시된다.
walking_num = int(input())
directions = input().split()

x=1
y=1

while len(directions)>0:
     
    direct = directions.pop(0)
    if (y>1)&(direct=='L'):
        y-=1
    elif (y<100)&(direct=='R'):
        y+=1
    elif (x>1)&(direct=='U'):
        x-=1
    elif (x<100)&(direct=='D'):
        x+=1
    else:
        pass

print(x,y)

 

문제 2

  • 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하라. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.
    • 00시 00분 03초
    • 00시 13분 30초
  • 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.
    • 00시 02분 55초
    • 01시 27분 45초
max_hour = int(input())

# 3이 아닌경우
# 0~ 59 -> 5*9 = 45
i=0
for hour in range(max_hour+1):
    if str(hour)[-1]!='3':
        i+=1

print( (max_hour+1)*60*60  -  i*45*45)

 

문제 3

  • 행복 왕국의 왕실 정원은 체스판과 같은 8 * 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다.
  • 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다.
  • 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
    1.  수평으로 두 칸 이동한 뒤에 수직으로 한칸 이동하기
    2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기
  • 8 * 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하라. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.
    • a1에 있을 때 이동할 수 있는 경우의 수는 2가지이다.
position = input()

# 다음엔 ord() 이용해서 문자를 아스키코드로 바꾸는 방법 생각하자!
y_dic={'a':1,'b':2,'c':3,'d':4,'e':5,'f':6,'g':7,'h':8}

y = y_dic[position[0]]
x = int(position[1])

possible_position = [(x+1,y+2),(x+1,y-2),(x+2,y+1),(x+2,y-1),(x-1,y+2),(x-1,y-2),(x-2,y+1),(x-2,y-1)]


i=0
for position in possible_position:
    if (position[0]>0)&(position[0]<9)&(position[1]>0)&(position[1]<9):
        i+=1

print(i)

 

문제 4

  • 알파벳 대문자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다.
  • 예를 들어 K!KA5CB7이라는 값이 들어오면 ABCKK13을 출력한다.
string = input()


# isdigit이나 isalpha 함수를 사용하면 if & else 문으로 한큐에 처리할 수 있다.
sort_string=''
for alphabet in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
    re_string = string.replace(alphabet,'')
    num = len(string)-len(re_string)
    string = re_string

    sort_string += alphabet*num


if string!='':
    value=0
    for num in string:
        value+=int(num)

    sort_string+=str(value)

print(sort_string)

 

문제 출처 : https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2