[0202 TIL]HUFS 겨울방학 코테대비 캠프

완전탐색

 

• 시간을 계산해보고 완전탐색을 사용할 수 있으면 사용해라!

| 문제

N * N 크기의 격자 정보가 주어집니다. 이때 해당 위치에 동전이 있다면 1, 없다면 0이 주어집니다. N * N 격자를 벗어나지 않도록 3 * 3 크기의 격자를 적절하게 잘 잡아서 해당 범위 안에 들어있는 동전의 개수를 최대로 하는 프로그램을 작성해보세요.

# 내 답
n = int(input())
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]

money = 0

def get(i, j):
    get_money = 0
    for i_ in range(i, i+3):
        for j_ in range(j, j+3):
            get_money += grid[i_][j_]
    return get_money

for i in range(0, n-2):
    for j in range(0, n-2):
        get_money = get(i, j)
        money = max(money, get_money)

print(money)
#############################################
# 더 나은 답

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

money = 0

def get(i, j):
    get_money = 0
    for i_ in range(i, i+3):
        for j_ in range(j, j+3):
            get_money += grid[i_][j_]
    return get_money

for i in range(n):
    for j in range(n):
        if i + 2 >= n or j + 2 >= n:
            continue
        get_money = get(i, j)
        money = max(money, get_money)

print(money)

• 저렇게 처음에 이중 for문을 돌 때 (0, n-2)로 하는 것 보다는 if 문을 두어서 continue 문을 두는 것이 실수를 줄일 수 있다.

https://www.codetree.ai/missions/2/problems/best-place-of-33/introduction

---

Immutable 과 mutable

• mutable(list, dict)를 통으로 바꿀 때는 함수 안에 global이라고 변수를 지정해주어야 통으로 바뀐다.
• 근데 이건 immutable의 값을 바꿀 때도 함수 안의 global이라고 지정해야한다.
• 그래서 차이점은 mutable에서는 a = [1], def 안의 b = a, b[0] = 5 를 해도 값이 바뀐다.

시간 복잡도 계산법

• 100일때는 n^4 까지!!
• 대충 계산한다.
• if 5 in arr:는 O(n)이고, 나머지 집합이면 O(n)이다.

로테이트를 for 문으로 구현한 것

for _ in range(t):
    temp = arr1[-1]
    for i in range(len(arr1)-1, 0, -1):
        arr1[i] = arr1[i - 1]
    arr1[0] = temp
cnt = 0

https://github.com/leehjhjhj/HUFSCodingTest