💡 학습 일기
규칙 찾기 문제는 재미있다. - Day18
코드로 모든 경우의 수를 찾아 들어가는 것보다, 공통된 규칙을 찾고 그걸 바탕으로 알고리즘을 구현하는 게 더 재미있다.
완전 탐색...? 너무 힘들다.
그런데 동적 프로그래밍이 뭘까 - Day18
Day18의 '중첩 점' 문제는 '동적 프로그래밍과 시뮬레이션 문제를 혼합한 문제'라고 한다.
동적 프로그래밍이란 뭘까...
'복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법'
하위 문제의 수가 기하급수적으로 증가할 때 유용하다. (중복 계산 제거)
최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다.
(출처: https://ko.wikipedia.org/wiki/동적_계획법)
아직 완벽히 이해하지는 못했는데다가, 동적 프로그래밍이 모든 경우의 수를 탐색하는 것과 마찬가지라고 해서 놀랐다.
이전에 풀었던 문제보다 이 문제가 더 재밌었던 이유는 뭘까...? 그냥 쉬웠나.
마지막은 타임어택 성공 - Day 20
요즘 계속해서 정해코드 확인 후 뒤늦게 풀어봤는데, 마지막인만큼 24시간 안에 풀어봤다.
완전탐색 코드는 계속해서 이전 내용들을 참고하고 있지만 ㅠㅠ
계속 작성해보면서 직접 코딩해볼 수 있도록 해야지...
💡 코드 공부
Day 18 : 중첩 점
- map을 활용해서 한꺼번에 int로 바꾸는 동시에 각각 -1 을 해주고 싶었지만, 방법을 찾지 못했다...
- 나는 시작점부터 -1 방향으로 가도록 range를 작성했는데, 어차피 범위만 같으면 되므로, 정해코드에서는 종료점을 y+1, x+1로 지정했더라.
for _ in range(M): y, x, d = input().split() y = int(y) -1 x = int(x) -1 if d == "U": for i in range(y, -1, -1): square[i][x][0] += 1 elif d == "D": for i in range(y, N): square[i][x][0] += 1 elif d == "L": for i in range(x, -1, -1): square[y][i][1] += 1 elif d == "R": for i in range(x, N): square[y][i][1] += 1
Day 19 : 대체 경로
- 이 문제는 최단 경로를 확인하는 방식을 알아야 한다.
- 여러 경로 중에 최단인 것을 찾아 내는 것은 불필요한 과정이다...
- BFS 최단경로
출처: https://nulls.co.kr/graph/141
어느 경로로 가든 상관없이 최단 경로의 탐색 횟수를 확인하는 것은 간단하다.
몇 단계까지 내려갔을 때 탐색 대상 변수를 찾았는지 확인하면 된다.def bfs(S, off): if S == off: # 시작 위치 공사중이면 -1 리턴 return -1 visited = [0 for _ in range(N+1)] q = deque([S]) visited[S] = 1 step = 1 # 시작지점 또한 단계 계산에 포함시킨다 while q: step += 1 # 다음 단계 시작 = 1단계 위치를 기반으로 **2단계 위치들 탐색** # for문 다 돌아가야 다음 step for _ in range(len(q)): now = q.popleft() # 현재 위치에서 도달할 수 있는 모든 점에 대해 탐색 for to in city[now]: if visited[to] or to == off: continue # 도착지점에 도달했다면 step 리턴 if to == E: return step # 아니라면 방문 기록 & 큐에 추가 visited[to] = 1 q.append(to) # 마지막까지 e로 가지 못했다면 -1 리턴 return -1
Day 20 : 연결 요소 제거하기
- 이번 문제는 for문이 한 번 돌아갈 때마다 연결된 요소가 K개 이상인지 확인해야 한다.
- bfs로 동일한 문자로 연결된 위치를 담는 리스트를 만들고, 이 리스트의 길이가 K개 이상이 되면 해당 위치를 '.'으로 바꾸는 과정을 거쳤다.
- 큐는 계속해서 빠져나와야 해서 리스트를 따로 만들었다.
- 방문기록은 필요 없는데, conli에서 계속 append하기 때문이다.
from collections import deque def bfs(y, x): global connected, conli dy = [-1, 1, 0, 0] dx = [0, 0, -1, 1] q = deque([(y, x)]) conli = [(y, x)] while q: ny, nx = q.popleft() for k in range(4): my, mx = ny + dy[k], nx + dx[k] if my in (0, N+1) or mx in (0, N+1) or (my, mx) in conli: continue if board[my][mx] == d: q.append((my, mx)) conli.append((my, mx))
