구현 알고리즘 2 : 기본 실전문제 풀어보기

화승이·2023년 3월 29일
0
  • 오늘은 저번에 했던 구현 알고리즘에 대해서 응용 문제를 2개 정도 풀어볼 것이다. 다 기업에서 코딩테스트에서 나오는 실제 기출 문제들을 위주로 공부해볼 것이고, 주로 이 유형들이 자주 나온다고 하니, 자주 들어와서 복습하면서 공부하도록 해보겠다.

1. 시각

  1. 문제설명
    정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성해라.
  • 입력조건
    • 첫째 줄에 정수 N이 입력된다. ( 0 <= N <= 23)
  • 출력조건
    • 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.
    • 입력예시 : 5 -> 출력 예시 : 11475
  1. 문제 풀이
  • 단순하다. 하나씩 모든 경우의 수를 세면 된다. 즉, 반복문을 활용해도 되는데, 그 이유는 하루는 86,400 초로 모든 경우가 100,000개도 되지 않기 때문에 시간 복잡도로 계산해볼때 많은 연산이 아니기 때문이다. 즉, 3중 반복문으로 풀어보도록 하겠다.
    ( 파이썬에서 계산시 100,000개 이내에 있는 연산은 2초 정도의 제한 시간 내에 풀 수 있다. )
    h = int(input())
    count = 0

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

print(count)


2. 왕실의 나이트

  1. 문제설명
  • 행복 왕국의 왕실 정원은 체스판과 같은 8X8의 좌표평면이다. 나이트는 말을 타고 있기 때문에 총 L 자 형태로만 움직일 수 있다.

    1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
    2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

    나이트가 있는 위치를 입력받으면 이동할 수 있는 경우의 수를 모두 구하여라.

  • 입력조건

    • 첫째 줄에 8 X 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1 처럼 열과 행으로 이뤄진다.
  • 출력조건

    • 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.
    • 입력예시 : a1 -> 출력예시 : 2
  1. 문제 풀이
  • 저번에 풀이했던 '상하좌우' 의 문제 유형과 같다. 즉, 이런식으로 좌표를 주면 그 내에서 움직이면서 계산하는 유형이 자주 나온다는 것을 확인할 수 있을 것 같다. 나이트의 경로는 2칸 한 방향으로 가면 다른 한 칸으로 수직 or 수평으로 이동하는 것이다. 즉, steps 라는 변수에 움직일 수 있는 위치를 기준으로 값을 넣으면 반복문으로 처리 할 수 있다. 코드는 다음과 같다.
    input_data = input()
    row = int(input_data[1])
    column = int(ord(input_data[0])) - int(ord('a')) + 1

steps = [
(-2, -1), (-1, -2), (1, -2), (2, -1)
(2, 1), (1, 2), (-1, 2), (-2, 1)
]

result = 0
for step in steps:
next_row = row + step[0]
next_column = column + step[1]
if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
result += 1

print(result)ㄷ


profile
이제부터 하고싶은것만 하면서 살거야

0개의 댓글