컴공 공부

집중 안해서 풀었더니 점수 하락...

사실 지난 한 주 동안 한 문제밖에 풀지 않아서 오를 점수도 없긴 하지만,

버스랑 지하철에서 급하게 푸느라 점수가 떨어졌다.

풀었던 문제인데도 집중해서 풀지 못하는 상황에 놓이니 못 풀었다.

지난 한 주 동안 게임도 하고 공부도 하고 놀러다니느라 불성실하게 살았던 것 같다.

다음주는 좀 더 열심히 살아야겠다! 

합쳐지는 구슬들 

문제 링크: https://www.codetree.ai/missions/2/problems/merge-marbles?&utm_source=clipboard&utm_medium=text

이 문제는 33분 48초만에 쉽게 푼 문제다.

보통 난이도라 그렇기도 하고 해당 유형의 공부를 많이 해서 잘 풀렸다.

아래는 내가 작성한 테스트케이스가 모두 통과된 코드이다.

n, m, t = map(int, input().split())
grid = [
    [[] for _ in range(n)]
    for _ in range(n)
]
for num in range(1, m + 1):
    r, c, d, w = input().split()
    i, j, w = int(r) - 1, int(c) - 1, int(w)
    grid[i][j] = [num, d, w]


def in_range(i, j):
    return i >= 0 and i < n and j >= 0 and j < n


dtoN = {'U': 0, 'D': 1, 'L': 2, 'R': 3}
dis, djs = [-1, 1, 0, 0], [0, 0, -1, 1]
for _ in range(t):
    tmp_grid = [
        [[] for _ in range(n)]
        for _ in range(n)
    ]
    for i in range(n):
        for j in range(n):
            if grid[i][j] != []:
                dNum = dtoN[grid[i][j][1]]
                new_i, new_j = i + dis[dNum], j + djs[dNum]
                if not in_range(new_i, new_j):
                    d = grid[i][j][1]
                    if d == "L":
                        d = "R"
                    elif d == "R":
                        d = "L"
                    elif d == "U":
                        d = "D"
                    else:
                        d = "U"
                    grid[i][j][1] = d
                    new_i, new_j = i, j
                # 충돌 처리
                if tmp_grid[new_i][new_j] != []:  # 충돌하면
                    grid[i][j][2] += tmp_grid[new_i][new_j][2]
                    if grid[i][j][0] < tmp_grid[new_i][new_j][0]:
                        grid[i][j][0] = tmp_grid[new_i][new_j][0]
                        grid[i][j][1] = tmp_grid[new_i][new_j][1]
                # 임시 격자에 저장
                tmp_grid[new_i][new_j] = grid[i][j]
    grid = tmp_grid

cnt = 0
max_w = 1
for i in range(n):
    for j in range(n):
        if grid[i][j] != []:
            cnt += 1
            if grid[i][j][2] > max_w:
                max_w = grid[i][j][2]

print(cnt, max_w)

한 달 반만에 300점 향상!!

대략 한 달 반 동안 매일매일 꾸준히 코딩테스트 문제를 한 문제 이상 풀었다.

(방학이라 시간을 내서 풀 수 있었다. 이제 개학해서 아마 일주일에 한 문제 정도 풀 것 같다..ㅎㅎ) 

실력 진단 테스트를 통해 실력이 얼마나 향상됐는지 확인할 수 있을뿐만 아니라,

내가 잘하는 부분과 부족한 부분을 알 수 있어서 좋았다.

실력 진단 당시 완전탐색은 2문제 빼고 다 푼 상태이고 dfs, bfs는 50%가량 푼 상태였는데,

그래서였는지 완전탐색은 잘 풀어나갔고 dfs, bfs 부분에서는 막혔다.

  사실 이번에 실력 진단을 하기 전까지는 50%가량만 풀어도 충분하지 않을까?라고 생각했었는데,

최소 90% 이상은 풀어야 체화할 수 있는 것 같다.

코드트리 학습 커리큘럼의 문제수가 딱 적절하게 구성되어 있었던 것이다..!

벽이 없는 충돌 실험

문제 링크: https://www.codetree.ai/missions/2/problems/collision-experiment-without-wall?&utm_source=clipboard&utm_medium=text

이 문제는 내가 유일하게 일주일동안 끙끙 싸맸던 문제다.

보통 다른 문제는 그래도 2일 안에는 풀렸는데, 일주일이나 걸린 문제는 처음이다.

메모리 초과로 인해서 테스트케이스를 통과하지 못했는데,

원인과 이를 해결한 방법에 대해 얘기해보겠다.

COORD_SIZE = 4000
BLANK = -1

T = int(input())  # 테스트 케이스 수
dtoN = {'U': 0, 'D': 1, 'L': 2, 'R': 3}
dis, djs = [-1, 1, 0, 0], [0, 0, -1, 1]

next_marble_index = [
    [BLANK for _ in range(COORD_SIZE + 1)]
    for _ in range(COORD_SIZE + 1)
]

for _ in range(T):
    marbles = []
    N = int(input())  # 구슬 개수
    for num in range(1, N+1):
        x, y, w, d = tuple(input().split())
        i, j, w, dNum = (-int(y)) * 2 + 2000, int(x) * \
            2 + 2000, int(w), dtoN[d]
        marbles.append((num, i, j, w, dNum))

    colT = -1

    def in_range(i, j):
        return i >= 0 and i < COORD_SIZE + 1 and j >= 0 and j < COORD_SIZE + 1

    for t in range(1, COORD_SIZE + 1):
        next_marbles = []
        # 이동
        for marble in marbles:
            num, i, j, w, dNum = marble
            new_i, new_j = i + dis[dNum], j + djs[dNum]
            if in_range(new_i, new_j):
                if next_marble_index[new_i][new_j] == BLANK:
                    next_marbles.append((num, new_i, new_j, w, dNum))
                    next_marble_index[new_i][new_j] = len(next_marbles) - 1
                else:
                    colT = t
                    # 무게가 크면
                    if next_marbles[next_marble_index[new_i][new_j]][3] < w:
                        next_marbles[next_marble_index[new_i][new_j]] = (
                            num, new_i, new_j, w, dNum)
                    # 무게가 같고 번호가 크면
                    elif next_marbles[next_marble_index[new_i][new_j]][3] == w and next_marbles[next_marble_index[new_i][new_j]][0] < num:
                        next_marbles[next_marble_index[new_i][new_j]] = (
                            num, new_i, new_j, w, dNum)

        marbles = next_marbles[:]

        # 다음 수행을 위한 초기화
        for marble in next_marbles:
            next_marble_index[marble[1]][marble[2]] = BLANK

    print(colT)

위는 내가 해설을 참고해 작성한 테스트케이스를 통과한 정답 코드이다.

해설과 다른 점은 함수화해서 작성하지 않은 것이다.

에러를 해결한 방법은 next_marble_index를 전역변수로 선언하고 매초마다 초기화가 필요한 인덱스만 초기화해준 것이다. 처음에는 for t in range 반복문 안에서 next_marble_index 변수를 선언과 동시에 매초마다 전부 초기화해주었다. 아무래도 next_marble_index가 4001 x 4001 크기의 2차원 리스트이다 보니, 무리가 되었던 것 같다.

따라서 next_marble_index를 전역변수로 선언해주고, next_marbles에 저장된 t초 뒤 구슬들의 위치 정보를 이용하여 구슬이 이동한 자리만 다시 초기화해 주었다. 

리스트

선언

# 숫자 별 출현 횟수 1  2  3  4  5  6
count_arr = [0, 0, 0, 0, 0, 0, 0]

# 혹은 다음과 같이도 정의가 가능합니다.
count_arr = [0] * 7

# list comprehension을 이용할수도 있습니다.
count_arr = [0 for _ in range(7)]

원소의 인덱스

• 리스트.index(원소값)

nums = [1,2,3,4,3,2,4]
print(nums.index(max(list_num))) #3

정렬

• 리스트.sort(reverse=bool값)

reverse 가 True이면 내림차순, False이면 오름차순으로 정렬된다.

#예시
citations.sort(reverse=True) # Sort the array in non-increasing order

주의!

• 지역변수로 선언해야 하는 변수를 전역변수로 선언하거나, 반복할 때마다 초기화해야 하는 변수를 반복문 바깥에서 초기화하는 등의 실수 주의!
• dup_nums = nums의 대입문을 통해 새로운 리스트 dup_nums에 이미 존재하는 리스트인 nums를 복사하려고 하면, dup_nums는 nums가 가리키는 메모리와 동일한 메모리를 가리키게 된다. 따라서 dup_nums의 원소값을 바꾸면 nums의 원소값도 바뀌게 되므로,  이를 원하지 않는다면 아래 코드처럼 복사해주어야 한다. 

dup_nums = nums[:]

문자열

거꾸로

• 문자열[::-1]

s = 'abcde'
print(s[::-1])  # 'edcba'

Backtracking

함수 내에서 전역 변수 사용

• global 변수명

 local variable 'cnt' referenced before assignment

cnt = 0

def dfs(curr_pos, last_num):
    global cnt
    if curr_pos == n:
        cnt += 1
        return
    for i in range(1, 5):
        if curr_pos+i <= n and i != last_num:
            dfs(curr_pos+i, i)
    return

XOR

• ^

print(1 ^ 3 ^ 5)

BFS

메모리 초과 오류

• 초기값 설정

https://www.codetree.ai/missions/2/problems/knight-movements?utm_source=clipboard&utm_medium=text

위의 링크에 있는 문제를 풀던 도중 메모리 초과 오류 발생!

from collections import deque

n = int(input())
r1, c1, r2, c2 = map(int, input().split())
#해당 격자 칸에 도달하는 데 필요한 최소 이동 횟수를 저장
arr = [ 
    [0 for _ in range(n)]
    for _ in range(n)
]
dis, djs = [-1, -2, -2, -1, 1, 2, 2, 1], [-2, -1, 1, 2, 2, 1, -1, -2]

def in_range(i, j):
    return i >= 0 and i < n and j >= 0 and j < n

def bfs():
    global can_arrive
    while q:
        i, j = q.popleft()
        if i == r2 - 1 and j == c2 - 1:
            can_arrive = True
            print(arr[r2-1][c2-1])
            break
        for di, dj in zip(dis, djs):
            new_i, new_j = i + di, j + dj
            if in_range(new_i, new_j):
                arr[new_i][new_j] = arr[i][j] + 1
                q.append([new_i, new_j])

q = deque()
q.append([r1-1, c1-1])
can_arrive = False
bfs()
if not can_arrive:
    print(-1)

위의 코드로 실행했더니 메모리 초과 오류가 났다. 그래서 bfs함수를 살펴보다가 빠뜨린 조건 하나가 생각 나서 추가해 주고 while문 위쪽의 if문을 for문에 넣어서 원하는 결과가 구해지면 바로 함수 실행을 끝낼 수 있도록 하였다. 

from collections import deque
n = int(input())
r1, c1, r2, c2 = map(int, input().split())
#해당 격자 칸에 도달하는 데 필요한 최소 이동 횟수를 저장
arr = [
    [-1 for _ in range(n)]
    for _ in range(n)
]
dis, djs = [-1, -2, -2, -1, 1, 2, 2, 1], [-2, -1, 1, 2, 2, 1, -1, -2]

def in_range(i, j):
    return i >= 0 and i < n and j >= 0 and j < n

def bfs():
    global can_arrive
    while q and not can_arrive: #3.함수 실행을 끝낸다.
        i, j = q.popleft()
        for di, dj in zip(dis, djs):
            new_i, new_j = i + di, j + dj
            if in_range(new_i, new_j) and arr[new_i][new_j] == -1:#조건 추가!!!
                arr[new_i][new_j] = arr[i][j] + 1
                if new_i == r2 - 1 and new_j == c2 - 1: #1.원하는 결과를 구하면
                    can_arrive = True #2.변수값을 True로 설정하여
                    print(arr[r2-1][c2-1])
                    break
                else:
                    q.append([new_i, new_j])

if r1 == r2 and c1 == c2:
    print(0)
else:
    q = deque()
    q.append([r1-1, c1-1])
    arr[r1-1][c1-1] = 0
    can_arrive = False
    bfs()
    if not can_arrive:
        print(-1)

메모리 초과 오류를 해결하기 위해 가장 중요했던 것은 아마 bfs함수에 arr[new_i][new_j] == -1이라는 조건을 추가해준 것인 것 같다. 해당 격자 칸에 도달하는 데 필요한 최소 이동 횟수를 저장하는 arr의 초기값을 0으로 설정했었는데, 그렇게 하면 출발칸과 도착칸이 동일할 경우 문제의 답이 0이므로 해당 arr칸의 결과가 구해진 것인지 아닌지 구분할 수 없게 된다. 따라서 arr칸의 값이 구해지지 않았다는 것을 나타내기 위해 초기값을 -1로 설정해주고, bfs함수에서 arr[new_i][new_j] == -1이라는 조건을 통해 해당 칸의 값이 아직 구해지지 않은 경우에만 값을 구하도록 하였다.(그래야 최소 이동 횟수가 저장된다.)