요새 매일 1시간 반 정도 코테 스터디를 진행하고 있다.
하는 이유는 코딩 테스트 감각을 잃지 않기 위함이다. 현재 가장 중요한 우선순위는 데이터 분석을 위한 SQL 학습, AI 신기술 (LLM 스터디), ADP (데이터 분석) 이므로 코딩 테스트의 경우 1시간에서 1시간 반 정도의 시간만을 투자해 감각을 잃지 않으려고 한다.
✅ Coding Test
🎈 1699 제곱수의 합
자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 일례로 11 = 3^2 + 1 + 1 3개의 숫자로 나타낼 수 있다.
문제에서 요구하는 것은 주어진 자연수 N을 최소 숫자만을 이용해 나타내려고 할때 사용되는 숫자의 개수를 구하는 것.
import sys
input = sys.stdin.readline
n = int(input())
dp = [i for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, i):
if j**2 > i:
break
if dp[i] > dp[i-j**2] + 1:
dp[i] = dp[i-j**2] + 1
print(dp[n])< 코드 해설 >
- 입력값으로 n을 변수로 저장하고 DP테이블을 숫자 1로 만들 수 있는 경우의 수로 둔다. (점차 작아지는 방법으로 갱신하기 위해.)
(만일 dp테이블 내 값이 1인 리스트를 만든다면 조건을 걸어줄 방법이 더 복잡하다.)- 숫자 N이 1부터 100000까지 이므로 for 문으로 1부터 n+1까지 범위를 i로 두고 j를 1부터 i까지로 둔다.
- i가 10인 경우 j는 [1,9]인데 만일 j가 4인 경우 부터는 제곱수로 10을 만들 수 없기 때문에 j**2이 i보다 크다면 다음 i번호로 넘어간다.
- 현재 dp[i] 값이 dp[i-j**2] + 1보다 클 수 밖에 없기에 해당 방법으로 갱신해준다.
i = 2인 경우 j는 1인데 dp[2]는 dp[1] + 1이다.
i = 3인 경우 j는 1, 2인데 2의 제곱인 4는 3보다 크기에 break하고 dp[2] + 1로 갱신
i = 4인 경우 j는 1,2,3인데, 3의 경우 break, dp[4-2**2]는 dp[0] + 1이므로 1로 갱신
위 방법을 반복하면 결국 앞서 갱신된 DP테이블 + 1의 방법을 따르며 제곱수의 경우 무조건 dp[0] + 1이라는 결과가 나오게 된다.
🎈 8911 거북이
구현 문제
2차원 평면 위에 거북이가 이동할 수 있는 명령은 다음과 같은 4가지다.
- F : 한 눔금 앞으로
- B : 한 눈금 뒤로
- L : 왼쪽으로 90도 회전
- R : 오른쪽으로 90도 회전
최종적으로 테스트케이스 T가 주어지고 각 테케별로 명렬이 주어질때 거북이가 지나간 영역을 모두 포함하는 직사각형의 넓이를 구하는 문제 (현재 거북이는 (0,0)에 있고 북쪽을 쳐다보고 있다)
import sys
input = sys.stdin.readline
T = int(input())
# 북동남서 방향 지정
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
for _ in range(T):
command = input().rstrip()
direction = 0 # 북동남서 0123 순서, 초기 방향 정립, 직사각형 가로 세로 minmax로 매번 결정
x, y = 0, 0
min_x, max_x, min_y, max_y = 0, 0, 0, 0
for com in command:
if com == 'F':
x += dx[direction]
y += dy[direction]
elif com == 'B':
x -= dx[direction]
y -= dy[direction]
elif com == 'L':
if direction == 0:
direction = 3
else:
direction -= 1
elif com == 'R':
if direction == 3:
direction = 0
else:
direction += 1
min_x = min(min_x, x)
max_x = max(max_x, x)
min_y = min(min_y, y)
max_y = max(max_y, y)
print(abs(max_x-min_x) * abs(max_y-min_y))< 코드 해설 >
거북이가 이동하지 않고 회전만 하는 L, R이 존재하므로 초기 dx, dy 설정에 있어 상하좌우가 아닌 북동남서와 같이 방향을 지정해주는 것이 중요하다.
그래야만, L, R 명령어가 등장할 때 초기에 북쪽(0)을 바라보는 상황에서 +1이든 -1이든 방향을 움직여 줄 수 있기 때문이다.따라서 dx, dy를 북동남서와 같은 방향으로 지정해주고 테케만큼 반복 (T)로 for문을 돌린다.
이후 F, B 의 경우 현재 위치 (x,y)에 dx/dy[direction]만큼 더하거나 빼주고 L, R의 경우 direction값에 변화를 주고 이동은 시키지 않는다.
각 반복을 진행한 이후 거북이가 이동한 영역의 직사각형 넓이를 알 수 있게 min_x, min_y와 max_x, max_y를 이동할 때마다 갱신해주며 최종적으로 T번 만큼 print로 넓이를 출력해준다.
