코딩테스트 풀면서 실수를 되풀이하지 않기 위해 정리한 리스트

문제 풀면서 나 혼자 보려고 노션에 정리해둔거 가져온거라 정리가 깔끔하게 잘 되어있지는 않으니 참고 바람

문제 접근

• 어떤 문제 먼저 풀지 잘 정하기 (N 큰 거 버려)
• 시간복잡도 계산해보기 - 하지만 시뮬레이션 문제면 그냥 ㄱ
• 자료구조 생각해보기 - 스택, 큐, heap, 이중리스트, set, dict
  • 빠른 코드 보다는 디버깅 가능한 방향으로 정하자
• 알고리즘 생각해보기 - 순열/조합/부분집합, bfs, dfs, 백트래킹, 다익스트라, MST, 유니온 파인드
  • 다익스트라는 방문 여부가 아니고 거리 갱신 가능 여부로 조건 처리하기
  • 갈 수 있는지 여부가 아니고 단순 거리라면 bfs/dfs가 아닌 순열/조합으로 풀 수 있음
• 제발제발 있는 그대로 읽고 그대로 구현하기 (TODO 리스트 만들기)
• 구현하기 쉽지만 실수하기 쉬운 if문 보다는 반복문으로 한번에 짜서 실수를 줄이기
• 벽을 감쌀지 말지 판단하기
  • 벽을 감싸는게 편한 문제(바둑2)가 있고 감싸면 안되는 문제가 있음
• 재귀와 배열 복사는 피할 수 있다면 피하기
  • 재귀 내부는 최대한 간단하게 만들고 N이 다 돌고 나서 처리하게끔
  • 배열 복사는 최대한 하지 않고 조합 만들어서 처리하기
    • 또는 처리 후 복원 시켜서 하나의 배열에서 처리하기
• 그리디하게 접근할 바에 정직하게 완전탐색하기
• 함수 단위로 한 문제 한 문제 푼다고 생각하고 단계별로 쪼개서 생각하기

시간 초과

• in / count() / index / filter 이런 것들은 O(N)이기 때문에 느림
• dict에서 in보다 get이 더 빠르다고 함
• lookup 테이블 최대한 활용하여 반복 줄이기
  • 치킨집 거리
  • 애너그램은 visited에 True/False만 담기보다 숫자를 같이 쓰기
  • 온풍기나 주사위2 같이 반복적인 것들은 점수 미리 계산해놓기
  • 달팽이나 미세먼지, 꼬리잡기 라운드 정보 등 좌표 미리 만들어놓기
  • 알파벳 횟수 저장할 룩업테이블
  • 미로 탈출하기에서 탈출할 수 있는 곳 저장해두기
  • 모래성에서는 파도 몇 번 쳐야되는지 저장해두기
• 불필요한 작업 줄이기
  • 이미 방문한 곳 재탐색하는 일 없도록 하기
  • 하나의 값만 봐도 되는데 여러 개 가지고 와서 정렬할 필요 X
  • 이미 탐색할 대상이 다 제거되었다면 조기 종료
  • 직사각형 탈출이나 유령의 집 탈출하기에서 애초에 못 가는 곳 미리 표시해두기
• 가지치기
  • 설정한 초기값을 갱신하지 못해 return 못 하는 경우
  • 남은 턴에 할 수 있는거 다 해도 최대값 갱신 못하면 가지치기
• 조건문은 빨리 탈출할 수 있는 조건을 앞으로 쓰기
• 구간합 구할 때는 투포인터 활용하여 반복 줄이기
  • 앞에 0으로 패딩하는게 풀 때 편함

실수 모음

• 처음과 마지막을 가장 주의하기
  • 초기 값
    • 초기 값을 음수로 뒀어야 했는데 0으로 둔 경우
    • 초기 값 갱신이 안 되는 경우
      • None, 상-상-상, 0, 1 등 초기 값 주의하기
  • 반복문에서 못 찾으면 예외 처리 (break 또는 else) 빠뜨리지 말기
  • 종료 조건 위치 주의 (답 갱신 먼저 할지 / 종료 먼저 할지)
  • 애초에 반복문을 돌지 않아도 되는 경우 살펴보기
• 0 / 비어 있는 경우 또는 작아지는 경우 고려하기
  • pop, remove, index 볼 때, for문으로 순회할 때
  • KeyError → dictionary에 key가 존재하지 않는 경우
  • array 비어있는 경우
  • 초기보다 array N, M이 작아지는 경우
  • ZeroDivisionError → 나누기 할 때 나누는 값이 0인 경우
• 인덱스 실수
  • 마지막에 i , i+1 / NN-1, NN / N, N+1 / 부등호 실수
  • array 행 열 범위 넘어가는 것들 처리 주의
  • x, y 좌표 방향 다른 경우 주의
• 배열 변경
  • 최대한 원본은 건드리지 않고 복사해서 쓰거나 초기 배열 만들어 쓰기
  • 새로운 배열 복사해서 거기서 총을 주워서 기존 지도에 남는 경우 주의
  • ValueError → 옮기기 전 아두이노와 옮긴 아두이노가 만나면 폭발되지 않도록 새로운 배열 만들어서 옮기기
• 반복문
  • while / for
    • while문 보다는 for문으로 실수를 줄이기
    • while문 쓰게 되면 while True하고 종료 조건 break로 쉽게 가자
  • 조건 처리
    • continue / break 뭐 쓸지 또는 빠뜨리지 않았는지 주의
    • 종료 조건은 반복문 마다 탈출해야 함 → 그냥 함수로 빼서 한번에 return시키기
• 여러 개
  • 메이즈 러너 한 칸에 여러 모험가가 있을 수 있음 → 모험가 각각 처리
  • 싸움땅 한 칸에 총 여러 개 있을 수 있음 → 3차원 배열 처리
• sync 맞추기
  • 반복문 돌 때 위치 옮겼으면 옮긴 위치로 바꾸기
  • 추가해야 하는데 덮어쓰지 않기 / 없애 버리지 않기
  • 최댓값 갱신 까먹지 말기
  • 자료형이 달라 == 판단이 안 되는 경우
  • 먹은 사과 없애주기, 자료 구조 바꿀 것들 확인
  • 죽은 애들 없애기, 안 죽은 곳 냄새 뿌리지 말기
• 전체 / 개별 관리
  • 곰팡이 단위로 다른 종 곰팡이 잡아먹는거 생각했는데 칸 단위로 큰 곰팡이 차지하는걸로 생각했어야 함
  • 인싸들의 가위바위보에서 플레이어별로 턴을 각각 가져가야했음
  • 로봇 개척자에서 각 농지별로 몇번째 씨앗인지 관리
• 오타
  • N, M / (d+2)%2 / nx, ny를 rr, cc로 / c를 d로 / += 인데 = 또는 +1
  • (1,0),(0,1) 순서 바꿔 쓰기
  • 가지치기 조건 or 안 적고 and 적음
  • blue[i][c] 안 적고 blue[c]라고 빠뜨림

Edge Case

• 눈 치울 때마다 sort해주기
• 무한 반복되는 지 확인 → 돌아올 때 같은 방향으로 돌아와야 Voyager
• 월드컵은 규칙 찾으면 빠지는 게 있을 수 있으니 재귀 dfs로 점수-1 → dfs → 점수+1 해보면서 확인해보기
• 오셀로 사이에 여러 돌이 있을 수 있다는 사실을 간과함
• 올림픽 동점자 처리
• 연구소 같이 바이러스 퍼뜨리는 거는 빈 칸을 미리 세두기
• 먹을 수 있는 물고기가 남아있지만 지나갈 수 없는 경우
• 날짜 변경 시 반올림 되는 경우와 0이 되는 경우 고려하기
• 소코반 이미 박스나 캐릭터가 목표점에 있는 경우
• 상어 중학교에서 무지개 블록은 visited 초기화 시키기
• 마상블 폭발을 동시다발적으로 시키지 않고 순차적으로 시키기
• 싸움땅 진 사람 이긴 사람 동시에 움직이는 거는 시키는 순서대로 하거나 기존 위치 없애놓고 시작하기
• 꼬리잡기에서 머리와 꼬리가 연결된 경우

기타 TIP

• 소수 셋째 자리까지 출력 방법 → print(f'{answer:3f}')
• 앞에 padding해서 출력 방법 → print(f'{answer:3d}')
• 가로 세로가 헷갈릴 때는 회전해서 풀어보기
  • zip보다 for문이 빠르지만 N과 M이 다른 경우 zip 쓰거나 len(matrix)과 len(matrix[0]) 활용
• 반대로 생각해보기
  • 일곱 난쟁이는 9명 중 2명 뽑기
  • 동전 자판기(하)에서 (낼 수 있는 돈 - 내야 할 돈) 가장 적게 동전 쓰기
  • 시간별로 보는게 아니라 계단 중심으로 풀기
• tuple 안에 원소가 하나 밖에 없으면 tuple이 안 만들어짐
• 코드 지울 때 조심해서 지우기
• 중력
  • 테트리스 / 모노미노 위에서부터 내려오기 (밑에서 부터 ㄴㄴ)
  • 2048의 0 무시하거나 검정색 블록 중력 X 케이스 고려하기
  • 지워진 라인 위쪽 라인 블록들을 내리면 O 가장 밑 라인 블록들부터 처리하면 X
  • 푸시로봇처럼 모든 블록이 갈 수 있는 만큼 가기 (미네랄2)
• 방향 꺾기 nx, ny = (r+s*dx)%(2***(R-1)), (c+s*dy)%(2***(C-1))
• 냄새는 K+1로 해두고 -1로 K로 만들기
• 메이즈 러너에서 정사각형 길이 찾기와 위치 찾기 분리해서 생각하기
  • 가까운 방향 찾기 → 4가지 방향 다 보고 가까운 곳 찾기
• dict와 set은 dict.copy(), set.copy()
  • 합치기는 d1.update(d2)하면 d1에 d2가 합쳐짐
• 가장 큰 경우만 담아야 한다면 가장 큰 그룹의 미생물 수도 같이 담기
• 벽돌 깨기 문제는 bfs/dfs에 (r, c, 깰 벽돌 수)를 담아서 깨기
• 게리맨더링 2 같은 대각선 x + d1 + d2 < N and 0 <= y - d1 and y + d2 < N
• 예술성이나 성곽 같이 인접한 두 그룹 확인할 때는 모든 곳에서 다 확인해야함
  • bfs/dfs 돌면서 set에 add해주기
  • 성곽 벽 확인 matrix[nx][ny] & (1 << i) 으로 했었음
• 16진수 숫자 쓰는 법 → int(x, base=16)
• 연속된 거 찾을 때는 0이 아니라 1로 초기화해서 풀어야 함
• 내 앞에 3명이 있으면 계단 대기해야 되면 내 3개 앞 인덱스 살펴보기
• 사전순으로 우선순위를 찾기 위해서는 조합으로 해야함
• 빵집의 경우 흔적 남겨놓고 행마다 dfs돌기
  • 파이프 놓기에 실패했어도 흔적을 지우면 안됨 → 방문을 되돌리면 안됨 (그리디기 때문에)
• 버스 갈아타기 : 겹치는 곳 찾기
  • (x, y, xx, yy) 에서 (x1, y1, x2, y2) → if (x1 <= xx and x <= x2) and (y1 <= yy and y <= y2):
• CCW : (x1, y1), (x2, y2), (x3, y3) 있다고 했을 때 벡터 A : (x2-x1), (y2-y1) / 벡터 B : (x3-x1), (y3-y1) 두 벡터의 외적(대각선으로 곱하기)의 값이 양수면 시계 방향 음수면 시계 반대 방향

 

자료구조/알고리즘별 주의

 

스택

• 스택 연산 후 남은 것들 꼭 처리해주기
• 어려웠던 후위표기식 / 계산기 다시 코드 읽어보기

BFS / DFS / BackTracking

• 접근
  • 여러 방향을 보거나 벽을 여러 번 부술 때 마다 다른 visited를 관리하는게 용이할 경우 3차원 visited 활용하기
    • 견우와 직녀처럼 오작교 세운 경우 안 세운 경우와 같이 다른 상태를 관리해야 할 때
    • 4방향 별로 봐야할 때
  • 절대값 거리인지 갈 수 있는 거리인지 확인 잘하기
  • visited가 꼭 2차원 배열 말고 알파벳이나 차량 정비소처럼 1차원 룩업테이블을 쓰는 경우도 고려
• 조건
  • 애초에 탐색할 수 없는 경우 고려하기 (처음과 마지막 위치)
  • 조건 처리 잘 하기 (범위 내 + 미방문 + 4/8방향 + 문제 제시 조건)
  • 방문 조건 빼먹지 말기
• 한 번에 여러 개 넣는 경우
  • 탈출 문제는 불과 사람 순서를 주의해서 동시 도착할 경우 고려하기
  • 빈 공간으로 처리해서 퍼질 수 있게 하거나 조건 정리 잘 하기
  • 통나무 옮기기나 직사각형 탈출, 푸쉬로봇 같은 거는 하나의 지점 정해서 한 칸만 visit 처리
• 방문 처리
  • 첫 방문 체크 잊지말기 → 시간 초과나 메모리 초과나는 경우 이 실수 많음
  • 재방문을 막기 위해 처음을 -1이나 1로 만들어뒀거나 0을 방문하는 경우 주의하기
  • 재귀 DFS의 경우 다시 방문 복귀하는거 까먹지 말기
  • 수영장 만들기 처럼 중간에 return해야하는 경우 방문을 끊으면 안 되는 경우 있음
  • visited 테이블 여러개 쓰는 경우
    • 이모티콘에서 화면 이모티콘과 클립보드 이모티콘처럼 방문 여러개 쓰기
    • 환승에서 하이퍼튜브와 역으로 방문 2개 쓰기
• DFS / 재귀 / 백트래킹
  • BFS로 먼저 생각해보기 또는 DFS로 시간초과 난다면 BFS로 풀 수 있는지 확인하기
    • visited 초기화 하는 식으로
    • 불켜기 문제의 경우 내가 갈 수 있으면 다시 가볼 수 있게 append
    • 움직이는 미로 탈출의 경우 단계별로 미로 움직이는게 똑같으니까 bfs
    • 동전 줍기는 동전 주울 조합을 정해서 동전 주우면 visited 초기화해서 bfs 돌기
    • 마알은 옮길 수 있는 횟수를 visited 배열로 만들기
    • BFS 들어가는 순서를 따로 만들어서 queue에 넣기 (BFS 스페셜 저지)
    • 로봇 청소기는 청소할 곳의 조합별로 거리를 미리 룩업테이블로 계산
  • 종료 조건 위치 주의 (답 갱신 먼저 할지 / 종료 먼저 할지)
  • 갱신을 못 한 경우는 답으로 포함 X
  • 재귀 조건이 적합한지 확인
    • 돌아야 하는데 안 돌거나 / 돌지 말아야 하는데 도는 경우가 있는지 점검하기
• 같은 거리에 있는 것들 중 우선순위가 문제에 주어진 경우 동일 너비 처리 Skaffold로 풀기

다익스트라

• 거리 갱신 해줘야함
• 거리가 -일 수 있는 경우에는 다익스트라 X

MST

• Union Find는 간선을 정점-1 까지만 봐야 함
  • len(set(parents)) 아니고 idx == x 가 부모임
• Kruskal 알고리즘은 visited 배열이 필요 없고 간선을 다 봤으면 break
  • 단, 간선 짧은 순으로 정렬 잊지 말기
  • 응용 → 2개로 분리해야 하는 경우 V-2개까지만 연결
• 복제 로봇에서 bfs 돌면서 인접 리스트 만들기

DP

• 배낭 문제
  • 2차원 → if w <= j: D[i][j] = max(D[i-1][j-w]+v, D[i-1][j]) else: D[i][j] = D[i-1][j]
  • 1차원 → for j in range(K, -1, -1): D[j] = max(D[j-w]+v, D[j])