알고리즘 구현 실수 유형 정리

1. 짝수 홀수 분기 처리 시 //이 아니라, %을 사용하기 

def recursive(matrix,n):
    if n == 1:
        return matrix
    #elif n // 2 == 0:
    elif n % 2 == 0:
        matrix = recursive(matrix, n//2)
        return multi(matrix, matrix)
    else:
        matrix = recursive(matrix, n-1)
        return multi(matrix, initial_matrix)

 

2. 호출 두번

-호출코드를 엄청 밑에다 적어둬서 보이지 않았음..

#index 이므로                 
BFS(start_point[0] - 1, start_point[1] - 1, start_point[2])


                    


#index 는 0으로 시작하므로 - 1
BFS(start_point[0] - 1,start_point[1] - 1,start_point[2])

 

3. 배열 선언

-문자열은 그 자체로 배열이므로, 2차원 배열로 선언 시 아래와 같이 한다.

    miro = ["." + input() + "." for _ in range(h)]

 

4. List index error

- range 오류가 날 때 선언 부분도 더블 체크 하자.

# ** h+2 **
 if 0 <= nr < h+2 and 0 <= nc < w+2 and miro[nr][nc] !="*" and not visited[nr][nc]:
                if 'A' <= miro[nr][nc] <= 'Z':
                    if chr(ord(miro[nr][nc]) + 32) not in key:
                        continue 
T = int(input())
for _ in range(T):
    h, w = map(int, input().split())
    miro = ["." + input() + "." for _ in range(h)]
    miro = ["." * (w+2)] + miro + ["." * (w+2)]
    # ** range를 h로 함 **
    visited = [[False] * (w+2) for _ in range(h)]
    key = {} 
    visited_doc = [] 
    for i in input():
        if i.isalpha(): 
            key[i] = True 
    answer = 0
    BFS(visited)
    print(answer)

 

5. for range 범위

- 실수로 -1을 넣는 행위

for i in range(1,len(location_list)-1): #실수부분
        if location_list[i] - current >= mid:
            count += 1
            current = location_list[i]
    if count < C: 
        return Binary(start, mid -1)
    else:
        answer = mid 
        return Binary(mid+1, end)

 

6. 문제를 잘못읽음(BJ14499)

주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다.

를 주체와 객체를 순간 헷갈려서. 주사위 바닥면에 칸이 복사된다라고 읽음.

 

7. 초기화를 안해줌(BJ17144)

# 미세먼지 안녕!
import sys
from collections import deque
si = sys.stdin.readline

# 실수 유형 체크 
R, C, T = map(int, si().split())
cleaner = []
graph = []
# 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]
# 그래프 초기화
for i in range(R):
    graph.append(list(map(int, si().split())))
    
# 청정기 위치 #으로 바꾸기 -> 중복때문
for i in range(R):
    for j in range(C):
        if graph[i][j] == -1:
            graph[i][j] = '#'

for _ in range(T): # 탐색 시작
    # for 문으로 완탐 -> 청정기 위치, 미세먼지 위치
    # tmp graph 영향을 주면 안됨
    tmp_graph = [[0 for _ in range(C)] for __ in range(R)]
    dust_list = [] #  아 초기화를 안해줬네..
    
    for i in range(R):
        for j in range(C):
            if graph[i][j] == '#': #청청기 위치
                cleaner.append((i,j))
            elif graph[i][j] != 0: 
                dust_list.append((i,j))
    
    # for 문으로 미세먼지 확산시키기
    for i in dust_list:
        x, y = i[0], i[1]
        if x == 5 and y == 7:
            pass
        tmp = graph[x][y] # 먼지량
        cnt = 0
        for idx in range(4): # 상하좌우
            nx, ny = x + dx[idx], y + dy[idx]
            if not (0<=nx<R and 0<=ny<C): continue # 범위 밖 X
            if graph[nx][ny] == '#': continue # 공기청정기 X 
            
            tmp_graph[nx][ny] += tmp // 5 # spread amount
            cnt += 1
        # 확산이 아예 안되는 경우는 없으므로 cnt == 0 체크하지 않음
        tmp_graph[x][y] -= (tmp//5) * cnt 


    # graph 수정하기
    for i in range(R):
        for j in range(C):
            if graph[i][j] != '#':
                graph[i][j] += tmp_graph[i][j]

먼지 list가 지역변수로 초기화해줘야 하는데 안해줘서 해맸음..

 

7. 인덱스 에러(BJ14503)

로직은 다 맞는데, 자꾸 인덱스 에러가남.. visited를 N *N 으로 초기화했더라..

#로봇 청소기
import sys
si = sys.stdin.readline
N, M = map(int, si().split())
r, c, d = map(int, si().split())
# 북, 동, 남, 서
dir = [(-1,0), (0,1), (1,0), (0,-1)]
robot = [r,c,d]
graph = []
cnt = 0
answer = 0
for i in range(N):
    graph.append(list(map(int, si().split())))
visited = [[0 for _ in range(M)] for _ in range(N)] # 이부분

 

8. 배열의 값을 넣을 떄는 얕은 복사 되므로 초기화를 하든 해야한다.(BJ20056)

# 마법사 상어와 파이어볼
import sys
import copy
si = sys.stdin.readline

N, M, K = map(int, si().split())
# 그래프 생성
graph = [[[] for _ in range(N)] for _ in range(N)]
dir = [(-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1)]
# 처음 파이어볼 넣기 초기화
for i in range(M):
    r, c, m, s, d = map(int, si().split())
    graph[r-1][c-1].append([m, s, d])

# 시작
for i in range(K):
    tmp_list = [[[] for _ in range(N)] for _ in range(N)]
    # 1. 그래프 돌기
    for i in range(N):
        for j in range(N):
            # 하나 이상이면 탐색하면서, 이동시키기
            if len(graph[i][j]) >= 1:
                while graph[i][j]: 
                    m, s, d = graph[i][j].pop()
                    nx, ny = (i + dir[d][0]*s) % N, (j + dir[d][1]*s) % N # 열, 행이 연결되어 있으므로
                    # graph에 하면 영향을 줘서 안된다.
                    tmp_list[nx][ny].append([m, s, d]) # 위치 이동
    
    #2. 이동 후 2개 이상의 파이어볼이 있는지 체크
    for i in range(N):
        for j in range(N):
            amount = 0
            speed = 0
            num = len(tmp_list[i][j])
            a_odd, a_even = True, True
            if len(tmp_list[i][j]) >= 2:
                for p in tmp_list[i][j]:
                    m, s, d = p
                    # 홀짝 체크
                    if d%2 == 1:
                        a_even = False
                    else:
                        a_odd = False
                    # 질량 합, 속력 합
                    amount += m
                    speed += s
                
                tmp_list[i][j] = [] # 초기화
                
                if amount // 5 == 0: continue # 질량이 0인 파이어볼은 소멸된다.
                
                # 방향
                if a_odd or a_even:
                    for q in [0, 2, 4, 6]:
                        tmp_list[i][j].append([amount//5, speed//num, q])
                else:
                    for q in [1, 3, 5, 7]:
                        tmp_list[i][j].append([amount//5, speed//num, q])
    
    # 그래프 초기화
    for i in range(N):
        for j in range(N):
            graph[i][j] = copy.deepcopy(tmp_list[i][j])

tmp_list[i][j].append()를 tmp_list.appen()라고 실수했다.

 

9. dir 넣을 때 실수 (BJ20056)

 

(-1-1)

 

10. combination은 list로 해줘야 for문 돌 수 있음

 

 

11. bfs pop(), popleft() (BJ15644)

popleft해야하는데 pop으로 해서 틀림

 

 

12. indexError

 

visited[nx][ny]를 체크하기 전에 0 <= nx < N and 0 <= ny < M 인지 체크해야함.