흔히 구현 유형의 문제는 무엇일까?
풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭
1. 알고리즘은 간단하지만 코드가 지나칠 만큼 길어지는 문제
2. 실수 연산을 다루고, 특정 소수점자리까지 출력해야하는 문제
3. 문자열을 특정한 기준에 따라 끊어서 처리해야하는 문제
4. 적절한 라이브러리를 찾아 사용해야하는 문제
문제풀이 1 : 상하좌우
여행가 A는 NxM 크기의 정사각형 공간 위에 서 있다. 이공간은 1x1 크기의 정사각형으로 나눠져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 있으며, 계획서에는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D(왼쪽, 오른쪽, 위쪽, 아래쪽으로 한 칸 이동) 중 하나의 문자가 반복적으로 적혀있다.
n = int(input()) p = input().split() x, y = 1, 1 # 시작점 세팅 # L, R, U, D에 따른 방향 dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] move_type = ['L', 'R', 'U', 'D'] for plan in p: for i in range(len(move_type)): #이동 후 좌표 if plan == move_type[i]: nx = x +d[i] ny = y +d[i] if nx < 1 or nx >= n or ny < 1 or ny > n : continue x, y = nx, ny 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초
💡 문제해결 아이디어
- 이 문제는 가능한 모든 시각의 경우를 하나씩 모두 세서 풀 수 있는 문제
하루는 86,400초이므로, 00시00분00초부터 23시 59분 59초까지의 모든 경우의 수는 86,400가지이다. (24 60 60 = 86,400)- 따라서 단순히 시각을 1씩 증가시키며 3이 하나라도 포함 돼 있는지 확인하면 됨
- 이러한 유형은 완전탐색 (Brute Forcing)라고 불리며, 가능한 경우의 수를 모두 검사해보는 탐색방법
h = int(input()) # 시간 입력 cnt = 0 for i in range(h+1): for j in range(60): for k in range(60): # 3이 있을 때, cnt += 1 if '3' in str(i) + str(j) + str(k): cnt += 1 print(cnt)
문제풀이 3 : 왕실나이트
이처럼 8x8 평면상에서 나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 왕실의 정원에서 행 위치를 표현할 때, 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현
예를 들어 그림과 같이 c2에 있을 때, 이동할 수 있는 경우의 수는 6가지
n = input() # a1 row = int(n[1]) # 2 col = int(ord(n[0])) - int(ord('a')) + 1 # a? # 나이트 이동방향 8가지 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_col = col + step[1] if next_row >= 1 and next_row <= 8 and next_col >= 1 and next_col <= 8: result +=1 print(result)
문제풀이 4 : 문자열 재정렬
알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다. 예를 들어, K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력한다.
s = input() result = [] value = 0 for x in s : # 알파벳인 경우 결과를 result에 삽입 if x.isalpha(): result.append(x) #숫자는 따로 더함 else: value += int(x) result.sort() # 오름차순 # 숫자가 하나라도 존재하면, 가장 뒤에 삽입 if value != 0 result.append(str(value)) #리스트를 합쳐서, 문자열 변환하여 출력 print(''.join(result))
