[코드트리챌린지] 늦었지만 09.05 ~ 09.11 공부 기록..!

목차

 

2023/09/05

실력 진단 결과 

진단을 시행하였는데, 시뮬레이션 문제 풀이 속도가 느렸고, 개념과 문제 5개를 추천받아 풀이함.

시뮬레이션II - dx,dy technique - 기본 개념

 

1. 방향에 맞춰 이동

풀이 전략

- 동서남북에 대한 dx, dy를 미리 선언해준 뒤, 움직이려는 방향에 움직일 거리를 곱해 더해준다

 

코드트리 해설 참고

- 시간복잡도 O(n)

- 공간복잡도 O(1)

 

풀이 코드

n = int(input())

moves = []
for _ in range(n):
    m,c = input().split()
    moves.append((m, int(c)))

x, y = 0, 0
directions = {'W':0, 'S':1, 'N':2, 'E': 3}
dx, dy = [-1, 0, 0, 1], [0, -1, 1, 0] # W S N E

for m,c in moves:
    x,y = x+dx[directions[m]]*c, \
        y+dy[directions[m]]*c

print(x,y)

 

2. 문자에 따른 명령 2

풀이 전략

- dx, dy를 왼쪽 시계 방향 순서로 만들어두고, L일 때는 i, R일 때는 3-i를 더하여 이동하게끔 한다

 

풀이 코드

- 아래 코드에서 +4 없이도 테스트 케이스는 통과하였으나, +4 를 안해주면 오작동할 수 있을 듯.

dirs = input()
x,y = 0,0
di = 3
dx,dy = [-1, 0, 1, 0], [0, -1, 0, 1] # L

for d in dirs:
    if d == 'L':
        di = (di+1)%4
    elif d == 'R':
        di = (di-1+4)%4 #(di-1)%4
    else:
        x,y = x+dx[di], y+dy[di]

print(x, y)

 

3. 1이 3개 이상 있는 위치

풀이 전략

- 상하좌우를 확인하며 3개 이상 1이면 카운트를 1 올리자.

 

풀이 코드

n = int(input())
dxs, dys = [1,-1,0,0], [0,0,1,-1]

maps = []
for _ in range(n):
    maps.append(list(map(int, input().split())))

counter = 0
for i in range(n):
    for j in range(n):
        sum_ = 0
        for dx,dy in zip(dxs,dys):
            nx,ny = i+dx, j+dy
            if nx<0 or nx>=n or ny<0 or ny>=n:
                continue
            else:
                sum_ += maps[nx][ny]
        if sum_ >= 3:
            counter += 1

print(counter)

 

4. 작은 구슬의 이동

풀이 전략

- 방향을 가진다. 1초에 한 칸을 움직인다. 부딪히면 반대로 움직인다.

- 방향은 한 번만 주어지므로, 좌우 또는 상하로만 움직인다.

- % 연산을 잘 사용하면, 시간복잡도를 줄일 수 있을 것으로 보이나 우선은 시뮬레이션 문제로 풀어보자.

 

풀이 코드

n,t = list(map(int, input().split()))
r,c,d = input().split()
r,c = int(r)-1, int(c)-1

dirs = {'L':0, 'R':1, 'U':2, 'D':3}
reverse_dirs = {'L':'R', 'R':'L', 'U':'D', 'D':'U'}
dx,dy = [-1,1,0,0], [0,0,-1,1]

for _ in range(t):
    nx,ny = c+dx[dirs[d]], r+dy[dirs[d]]
    if nx<0 or nx>=n or ny<0 or ny>=n:
        d = reverse_dirs[d]
    else:
        c,r=nx,ny

print(r+1,c+1)

 

5. 빙빙 돌며 숫자 사각형 채우기

풀이 전략

- 빙빙 돌 때는 R -> D -> L -> U 순서로 방향 전환

- 다음 칸이 -1이면 숫자를 채우고 아니면 방향을 전환

 

풀이 코드

- 변수로 x, y를 사용하니 인덱싱이 헷갈린다. 되도록 r,c를 사용하는 것이 좋을 듯!

n, m = list(map(int, input().split()))
maps = [[-1 for _ in range(m)] for _ in range(n)]

# 초기화
r,c = 0,0
di = 0
dr,dc = [0,1,0,-1], [1,0,-1,0] # RDLU

# 초기 세팅
maps[r][c] = 1
data = 2

# 범위를 벗어나면 False
def inrange(r,c):
    return c<0 or c>=m or r<0 or r>=n

while data <= n*m:
    nr, nc = r+dr[di], c+dc[di]
    if inrange(nr, nc):
        di = (di+1)%4
    elif maps[nr][nc] == -1:
        maps[nr][nc] = data
        data += 1
        r,c = nr,nc
    else:
        di = (di+1)%4

for i in range(n):
    for j in range(m):
        print(maps[i][j], end=' ')
    print()

 

---

2023/09/06

1. 되돌아오기

풀이 전략

- 평범한 시뮬레이션 문제.

풀이 코드

# 입력 받기
n = int(input())

commands = []
for _ in range(n):
    dir_, dis = input().split()
    commands.append((dir_, int(dis)))

# 방향 선언
dx,dy = [0, -1, 1, 0], [-1, 0, 0, 1] # WSNE
dir_to_idx = {'W':0, 'S':1, 'N':2, 'E':3}

x,y = 0,0
time = 0
for dir_, dis in commands:
    idx = dir_to_idx[dir_]
    for d in range(dis):
        x,y = x+dx[idx], y+dy[idx]
        time += 1
        if x==0 and y==0:
            print(time)
            break
    if x==0 and y==0:
        break
else:
    print(-1)

 

2. 되돌아오기 2

풀이전략

되돌아오기와 방향만 반대!

풀이 코드

# 입력 받기
dirs = list(input())

# 방향 선언
dr,dc = [1,0,-1,0], [0,1,0,-1] # NESW

r,c = 0,0
d_idx = 0

for i,d in enumerate(dirs):
    if d == 'R':
        d_idx = (d_idx+1)%4
    elif d == 'L':
        d_idx = (d_idx-1+4)%4
    else:
        r,c = r+dr[d_idx], c+dc[d_idx]
    
    if r==0 and c==0:
        print(i+1)
        break
else:
    print(-1)

 

 

3. 격자 위의 편안한 상태

풀이 전략

- 색칠을 하면서 안정한 상태인지, 상하좌우 중 3개가 색칠되어 있는지 확인

풀이 코드

# 입력 받기
n,m = list(map(int, input().split()))

locations = []
for _ in range(m):
    locations.append(list(map(int, input().split())))

def outrange(r,c):
    return r<0 or r>=n or c<0 or c>=n

maps = [[0 for _ in range(n)] for _ in range(n)]
for r,c in locations:
    maps[r-1][c-1] = 1
    sum_ = 0
    for dr,dc in zip([0,0,1,-1], [1,-1,0,0]):
        nr,nc = r+dr-1, c+dc-1
        if outrange(nr,nc): continue
        sum_ += maps[nr][nc]
    if sum_ == 3:
        print(1)
    else:
        print(0)

 

---

2023/09/08

1. 거울에 레이저 쏘기 2 (쪼끔 어려웠다..휴)

풀이 전략

- k-1을 n으로 나눈 몫이 방향을 결정, 나머지가 시작 위치를 결정해야 함. 단 이 때, 방향에 따라 r 또는 c에서 시작해야 함.

- dx,dy 정의 시, (하, 좌, 상, 우) 방향으로 정의해야 하며, 하는 (+1,0), 좌는 (0,-1) 상은 (-1,0), 우는 (0, 1)로 정의해야 함.

- 상하좌우의 방향과 \\ /의 방향에 따라 경우의 수가 8개 생긴다.

- \\ => 하->우, 상->좌, 좌->상, 우->하

- / -> 하->좌, 상-> 우...

- 위 정보를 딕셔너리를 이용해 정리한 뒤, 기본 dx,dy 문제들처럼 풀어낸다.

- 다만, 경로를 벗어나면 무시가 아니라, 종료되어야 함.

 

n=3, k=2

2: 1//3 = 0, 1%3=1

9: 8//3 = 2, 8%3=2

 

풀이 코드

# 입력 받기
n = int(input())
maps = []
for _ in range(n):
    maps.append(list(input()))
k = int(input())-1

dr,dc = [1,0,-1,0],[0,-1,0,1] # 하좌상우
direction = k//n
slash_dict = {0:1, 1:0, 2:3, 3:2}
slash_op_dict = {0:3, 1:2, 2:1, 3:0}

if direction==0:
    r,c = 0, k%n
elif direction==1:
    r,c = k%n, n-1
elif direction==2:
    r,c = n-1, n-1-k%n
else:
    r,c = n-1-k%n, 0

counter = 0
while r>=0 and r<n and c>=0 and c<n:
    if maps[r][c] == '/':
        direction = slash_dict[direction]
    else:
        direction = slash_op_dict[direction]
    r,c = r+dr[direction], c+dc[direction]
    counter += 1

print(counter)

 

 

2. 빙빙 돌며 숫자 사각형 채우기 2

 

풀이 전략

- 카운트를 하나씩 키우면서, 하좌상우 방향을 순환하며 값을 채운다. 미리 -1을 채워두고, -1을 만나거나, n 범위를 벗어나면 방향을 전환한다. 카운트가 넘어서면 중단한다.

n, m = list(map(int, input().split()))
dr,dc = [1, 0, -1, 0], [0, 1, 0, -1]
maps = [[0 for _ in range(m)] for _ in range(n)]
r,c = 0,0
maps[r][c] = 1
direction = 0
counter = 2

while counter <= n*m:
    # 다음 위치
    nr,nc = r+dr[direction], c+dc[direction]

    # 다음 위치가 영역을 벗어나거나 이미 채워져있으면 방향을 틀기
    if nr<0 or nr>=n or nc<0 or nc>=m or maps[nr][nc]!=0:
        direction = (direction+1)%4
        nr,nc = r+dr[direction], c+dc[direction]
    
    r,c = nr,nc
    maps[r][c] = counter
    counter += 1

for i in range(n):
    for j in range(m):
        print(maps[i][j], end=' ')
    print()

---

2023/09/10

1. 빙빙 돌며 사각형 채우기

풀이 전략

- A 부터 Z까지 빙빙 돌며 채워야 하므로, 26으로 나눈 나머지로 알파벳을 인덱싱하며 채운다.

 

풀이 코드

from string import ascii_uppercase
n,m = list(map(int, input().split()))

dr,dc = [0,1,0,-1], [1,0,-1,0]
r,c = 0,0
direction = 0
maps = [[0 for _ in range(m)] for _ in range(n)]
maps[0][0] = 'A'
c_idx = 1
idx = 1

while idx<n*m:
    nr,nc = r+dr[direction], c+dc[direction]
    if nr<0 or nr>=n or nc<0 or nc>=m or maps[nr][nc]!=0:
        direction = (direction+1)%4
        nr,nc = r+dr[direction], c+dc[direction]
    r,c = nr, nc
    maps[r][c] = ascii_uppercase[c_idx]
    idx += 1
    c_idx = (c_idx+1)%26

for i in range(n):
    for j in range(m):
        print(maps[i][j], end=' ')
    print()

 

2. 가운데에서 시작하여 빙빙 돌기

진짜 가운데부터 시작해서 빙빙돈다..!

n = int(input())

dr,dc = [0,-1,0,1],[1,0,-1,0]
r,c = n//2, n//2
maps = [[0 for _ in range(n)] for _ in range(n)]
maps[r][c] = 1
value = 2
d = -1

while value<=n*n:
    nd = (d+1)%4
    nr,nc = r+dr[nd], c+dc[nd]
    if nr<0 or nr>=n or nc<0 or nc>=n:
        break
    if maps[nr][nc]!=0:
        r,c = r+dr[d], c+dc[d]
    else:
        r,c = nr,nc
        d = nd
    maps[r][c] = value
    value += 1
    
for i in range(n):
    for j in range(n):
        print(maps[i][j], end=' ')
    print()

 

3. 이동경로 상 모든 숫자 더하기

n, t = list(map(int, input().split()))
commands = list(input())
maps = []
for _ in range(n):
    maps.append(list(map(int, input().split())))

d=0
r,c=n//2, n//2
dr,dc = [-1, 0, 1, 0],[0, -1, 0, 1]
d_dict = {'L':1, 'R':-1}
value = maps[r][c]

def outrange(nr, nc):
    return nr<0 or nr>=n or nc<0 or nc>=n

for command in commands:
    if command == 'F':
        if outrange(r+dr[d], c+dc[d]):
            continue
        r,c = r+dr[d], c+dc[d]
        value += maps[r][c]
    else:
        d = (d+d_dict[command])%4

print(value)

---

마무리

백준, 프로그래머스는 이상적인 코드를 엿볼 수 있고 유사한 유형의 문제를 여러 개 풀어볼 수는 있지만, 명쾌한 해설이 같이 제공되지 않아서 입문자에게는 조금 어렵다. 근데 코드트리를 통해서는 약한 유형을 파악하고, 해설까지 확인할 수 있어서 좋은 듯..!!