2023년 8월 19일 알고리즘 문제풀이
문제 1 백준 1158
1차 시도
나의 생각
요세푸스 문제. deque을 사용해 왼쪽에서 하나씩 꺼내면서 K번째에는 다시 오른쪽으로 넣어주지 않고 정답을 위한 배열에 추가했다. 몇번째인지는 loop가 반복될 떄마다 1씩 더해주고 K로 나눈 나머지를 통해 표시했다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys
from collections import deque
n,k = map(int,sys.stdin.readline().split())
arr = deque()
for i in range(1,n+1):
arr.append(str(i))
ans = []
cnt = 0
while arr:
tmp = arr.popleft()
cnt += 1
if cnt%k:
arr.append(tmp)
else:
ans.append(tmp)
ans = ', '.join(ans)
print('<',ans,'>',sep='')
문제 2 백준 13116
1차 시도
나의 생각
형제 노드의 부모는 자신을 2로 나누었을 때의 몫을 부모로 가진다. 예를 들어, 12와 13은 2로 나누면 몫이 6이므로 부모가 6이다. 이를 이용해서 자신의 값을 2로 나눌때 나타나는 몫들을 배열에 저장한 후 두 배열 모두 들어있는 값들 중 최댓값을 출력하면 된다. 없다면 루트노드인 1일테니 10을 출력하였다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
t = int(sys.stdin.readline())
for _ in range(t):
a, b = map(int, sys.stdin.readline().split())
def main(x):
arr = []
while x > 1:
arr.append(x)
x //= 2
return arr
arr_a = main(a)
arr_b = main(b)
ans = []
for x in arr_a:
if x in arr_b:
ans.append(x)
if ans:
print(10*max(ans))
else:
print(10)
문제 3 백준 10026
1차 시도
나의 생각
BFS를 정의하여 처음 인자로 받은 좌표의 색깔을 기준으로 같은 색깔을 방문처리를 위해 0으로 변경해주었다. BFS가 호출될 때마다 근처의 같은 색깔 구역이 방문처리되므로 1씩 갯수를 세주었다. 적록색약을 위해서는 빨강과 초록을 구분 못하므로 G를 모두 R로 바꾸어서 같은 방법을 사용하였다.
꽤 어려워서 오래 걸렸는데 그 이유를 아래에 추가해놨으니 꼭 읽어보길 권한다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import sys
from collections import deque
n = int(sys.stdin.readline())
board = []
board_d = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(n):
word = list(sys.stdin.readline().rstrip())
board.append(word)
for i in range(n):
for j in range(n):
if board[i][j] == 'G':
board_d[i][j] = 'R'
else:
board_d[i][j] = board[i][j]
def bfs(a, b, graph):
if graph[a][b] == 0:
return False
da = [1, 0, -1, 0]
db = [0, 1, 0, -1]
arr = deque()
color = graph[a][b]
graph[a][b] = 0
arr.append([a, b])
while arr:
p, q = arr.popleft()
for i in range(4):
na = p + da[i]
nb = q + db[i]
if na < 0 or na >= n or nb < 0 or nb >= n:
continue
if graph[na][nb] == color:
graph[na][nb] = 0
arr.append([na, nb])
return True
ans = [0, 0]
for i in range(n):
for j in range(n):
if bfs(i, j, board):
ans[0] += 1
for i in range(n):
for j in range(n):
if bfs(i, j, board_d):
ans[1] += 1
print(*ans)
어려웠던 부분
다음 코드는 틀린 이유를 못찾아서 15분 가까이 고민했던 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import sys
from collections import deque
n = int(sys.stdin.readline())
board = []
board_d = []
for _ in range(n):
word = list(sys.stdin.readline().rstrip())
board.append(word)
board_d.append(word)
def bfs(a, b, graph):
if graph[a][b] == 0:
return False
da = [1, 0, -1, 0]
db = [0, 1, 0, -1]
arr = deque()
color = graph[a][b]
graph[a][b] = 0
arr.append([a, b])
while arr:
p, q = arr.popleft()
for i in range(4):
na = p + da[i]
nb = q + db[i]
if na < 0 or na >= n or nb < 0 or nb >= n:
continue
if graph[na][nb] == color:
graph[na][nb] = 0
arr.append([na, nb])
return True
ans = [0, 0]
for i in range(n):
for j in range(n):
if bfs(i, j, board):
ans[0] += 1
for i in range(n):
for j in range(n):
if board_d[i][j] == 'G':
board_d[i][j] = 'R'
for i in range(n):
for j in range(n):
if bfs(i, j, board_d):
ans[1] += 1
처음에는 board와 board_d를 모두 빈 배열로 설정한 뒤 색깔에 대한 입력값을 받은후 board와 board_d 모두에 append 해주었다. 이후 반복문을 통해 board_d배열에서 ‘G’값을 ‘R’로 바꿨다. 이후 코드는 지금 코드와 동일한데, 오답처리 되었다.
디버깅하는 과정에서 발견한 것은 board배열만 BFS를 호출해주었는데도 board_d의 원소들도 모두 0으로 수정되어 있었다. 38번 행에 print(board_d)를 추가했더니 배열의 원소가 모두 0이였다.
고쳐서 답은 맞췄지만 이유를 알고싶어 찾아보았다. 7~9번 행에서 board와 board_d는 서로 다른 변수 이름을 갖고 있지만, 실제로는 동일한 메모리 위치를 참조하게 된다. 그 결과, board를 변경하면 board_d도 동시에 변경되었던 것이다.
혹시 몰라 board_d를 새롭게 만들어줬더니 정답처리 되었던 이유가 있었다!
