유클리드 호제법#

처음 챕터인 함수와 갭체크에서 추천해준 완전탐색을 공부했는데
함수 부분에서 유클리드 호제법을 알아야 하는 최대공약수 문제가 나왔다.

1
n, m = map(int, input().split())
2

3
def gcd(a, b):
4
    while b != 0:
5
        a, b = b, a % b
6
    return a
7

8
print(gcd(n, m))

이게 알고나면 별거 아닌데, 이런 방법을 몰랐을 때 나는

각 숫자보다 작은 소수 리스트를 구해서 그 중에서 나누어떨어지는 애들로 소인수분해를 하고
두 숫자의 소인수분해 리스트를 만들어서 공통되는 부분으로 최대공약수를 만들었다..

사실 지금도 왜 저렇게 하면 최대공약수가 되는지 수학적으로 제대로 아는게 아니라서
유클리드 호제법이랑, 소수 관련해서는 에라토스테네스의 체를 언제 한번 공부해야겠다 생각은 하고 있었다.

근데 미루고 미루다보니 몇달째 공부 안했다는걸 오늘 느꼈음..
이번 주에는 무조건 관련해서 공부하고 포스팅해야겠다.

전역 변수, 지역 변수, 스코프#

뿐만 아니라 전역 변수와 지역 변수에서 내가 맨날 헷갈리던 내용이 다뤄서 좋았다.

개념 부분에 막 엄청 자세하게 설명되어있는건 아니었는데, 일단 주제가 던져지니까
코덱스한테 관련 개념 물어보고 옵시디언에 정리하는 흐름이 자연스럽게 생겼다.

탑다운 방식으로 생각하기#

1
def is_magic_number(n):
2
    return n % 3 != 0 and n % 5 == 0
3

4
cnt = 0
5
for i in range(1, 101):
6
    if is_magic_number(i):
7
        cnt += 1
8

9
print(cnt)
10

11
>> 14

어떤 조건을 만족하는 숫자들의 개수를 구하라는 문제다.

이런 문제를 풀 때
특별한 조건을 만족하면 1을 더하면 되겠네? 라는 전체 흐름을 먼저 생각하고
이런 식으로 특별한 조건 만족하는지 체크하면 되겠네? 라는 세부 구현을 생각하는게
탑다운 방식으로 생각하는거다.

당연히 평소에 어느 정도는 이런 식으로 하고 있을텐데
사고 방식에 대해 내가 인지적으로 의식할 수 있게 된 것 같다.

완전 탐색#

완전 탐색은 말 그대로 가능한 경우의 수를 전부 체크하는거다.

경우의 수를 체크할 때 brute force처럼 반복문을 무식하게 돌려볼 수도 있지만
재귀나 백트래킹 같은 방법을 써서 체계적으로 모든 경우의 수를 훑는 것도 완전 탐색이다.

그러니까 완전 탐색에서는 단순하게 전부 다 보면 되는구나 가 아니고
어떤 상황에서 완전 탐색할지, 어떤 도구를 써서 탐색할지를 판단하는 능력이 중요한거다.

이 문제의 경우, 경유 포인트가 2개로 정해졌기 때문에 이중 반복문으로 첫번째 경유 포인트를 찾고
그 찾은 시점에서 또 이중 반복문으로 두번째 경유 포인트를 찾으면 된다.

1
R, C = map(int, input().split())
2
grid = [list(input().split()) for _ in range(R)]
3

4
from collections import deque
5

6
# cx, cy에서 탐색 범위 : cx+1 to R-2 and cy+1 to C-2
7
# 가능한 점들 모두 후보 넣기
8

9
def search(cx, cy, jump):
10
    color = grid[cx][cy]
11
    nxts = []
12

13
    for x in range(cx+1, R-1):
14
        for y in range(cy+1, C-1):
15
            if grid[x][y] != color:
16
                nxts.append((x, y, jump+1))
17

18
    return nxts
19

20
q = deque([(0, 0, 0)])
21

22
final = grid[R-1][C-1]
23

24
ans = 0
25

26
while q:
27
    cx, cy, jump = q.popleft()
28
    if jump == 2:
29
        if grid[cx][cy] != final:
30
            ans += 1
31
        continue
32

33
    nxts = search(cx, cy, jump)
34

35
    for nxt in nxts:
36
        q.append((nxt))
37

38
print(ans)

나는 bfs로 될것 같아서 bfs로 풀었다.

만약에 경유지 개수에 제한이 없거나 4개 이상이라면 중첩 반복문보다는 bfs가 일반화하기 더 편하지 싶다.