코딩테스트 문제 풀이 오답 노트

리스트

선언

# 숫자 별 출현 횟수 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

위 에러는 전역변수를 지역 변수로 호출했기 때문에 발생하며 

간단하게 함수 내부에 global '변수명' 을 추가하면 해결된다.

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이라는 조건을 통해 해당 칸의 값이 아직 구해지지 않은 경우에만 값을 구하도록 하였다.(그래야 최소 이동 횟수가 저장된다.)