나동빈님의 책과 유튜브 강의인 '이것이 코딩 테스트다'를 바탕으로 스스로 공부한 내용을 정리한 글입니다.
참고한 영상의 링크는 아래와 같습니다.
구현
- 머릿속에 잇는 알고리즘을 소스코드로 바꾸는 과정이다.
- 이 강의에서는 아래 2가지 개념과 구현을 하나의 강의에서 동시에 설명하고 있다.
완전탐색
- 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션
- 문제에서 제시한 알고르짐을 한 계단씩 차례대로 직접 수행해야하는 문제 유형
상하좌우 문제
- 첫째 줄에 공간의 크기를 나타내는 N이 주어진자. (1<=<=100)
- 둘째 줄에 여행가A가 이동할 계호기서 내용이 주어진다. (1<=이동회수<=100)
- 첫번째 출바공간이 (1,1) 좌측하단이 (N,N) 공간 밖의 공간으로 이동은 무시한다는 가정하에 여행가A가 출발공간에서 이동을 시작해서 도착할 지점의 좌표 (X,Y)를 공백으로 구분해서 출력하세요.
n = int(input())
directions = list(input().split(" "))
x, y = 1, 1
dx = [0,0,-1,1]
dy = [1,-1,0,0]
move_types = ['R','L','U','D']
for direction in directions:
for i in range(len(move_types)):
if direction == 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)이문제의 핵심사항을 정리해보면 다음과 같다.
- 시뮬레이션 문제로 이동가가 이동할 수 있는 방향을 방향벡터로 설정해주기.
(시뮬레이션의 큰 그림을 간단히 표현할 수 잇는 것을 구현시키는 방법을 빠르게 찾는게 point로 보여짐) - 문제의 조건에 따라 좌표 공간을 벗어나는 경우 'continue'를 사용해서 loop문 통과시켜주기.
시뮬레이션 문제의 전반적인 큰 그림을 배우기 가장 좋은 문제라고 생각이 든다.
시각 문제
- 정수 N이 입력되면 00시 00분부터 00초부터 N시 59분 59초까지 모든 시각 중에서 3이 하나라도 포함하는 모든 겨웅의 수를 구하는 프로그램을 작성하시오.
내가 처음에 찬 코드이다.
n = int(input())
count = 0
only_second_3 = 15 * 60
only_minutes_3 = 45 * 15
for i in range(0, n + 1):
if i % 3 != 0 or i == 0:
count += (only_second_3 + only_minutes_3)
else:
count += 3600
print(count)- 분을 기준으로 2가지로 나누어서 문제를 푼다.
- 분에 숫자 3이 없는 경우, 초에 반드시 3이 있어야함
- 분에 숫자 3이 있는 경우.
- 이후, 다시 시를 숫자 3이 있는 경우와 없는 경우로 나누어서 푼다.
하지만 이는 완전탐색으로 문제를 푸는게 아니었다.
n = int(input())
count = 0
for h in range(0, 1 + n):
for j in range(0, 60):
for k in range(0, 60):
if '3' in str(h) + str(j) + str(k):
count += 1
print(count)- 완전탐색으로 문제를 푸는 방법은 1-h시간동안 모든 j,k를 탐색하도록 string 시각을 선언한 후 이 때 3이 있는지 검색하는 식으로 코드가 작성되었다. (일종의 테크닉인듯...)
왕실의 나이트
- 8x8 체스판에서 행은 1..8, 열은 a..h로 표현된다.
- 첫째 입력에 현재 나이트가 위치한 곳의 좌표가 입력된다. (eg., a1)
- 나이트는 수직/수평 이동 2칸 이후 수평/수직 이동 1칸만이 가능하다.
- 첫째 줄에 나이트가 이동할 수 있는 모든 경우의 수를 구하시오.
x = input()
row = int(x[1])
column = int(ord(x[0])) - int(ord('a')) + 1
count = 0
directions = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2),(1, 2)]
for dx, dy in directions:
nx = row + dx
ny = column + dy
if nx > 0 and nx <= 8 and ny > 0 and ny <= 8:
count += 1
print(count)이 문제가 개인적으로 가장 헷갈리는 요인들이 많았는데 정리해보면 다음과 같다.
- 행,열이 다른 문자열로 표현되어있는데 아스키 코드를 활용해서 int형으로 바꿔주면 보다 수월한 문제풀이가 가능하다는 것을 늦게 떠올렸다. (+ ord(a)-ord(a)0임으로 행과 맞춰주기 위해서는 +1도 생각하기)
- 입력은 열/행 순으로 주어졌는데, 다른 문제들의 경우 방향벡터에서 step이 (행,열)로 되어있는 경우가 많아서 위에서 선언한 걸 그대로 사용했을 경우 오답이 산출될 수도 있다.
- 역시 다른 시뮬레이션&완선탐색과 마찬가지록 가능한 모든 이동경로를 방향벡터로 선언한다는 아이디어를 빠르게 생각해내는게 관건으로 보인다.
