🚨 시간 초과 발생 문제

[2018007956]

시간 단축 솔루션

• 모든 값을 순회하지 않고, Counter 모듈을 사용하여 같은 값들은 각 개수만큼 한번에 처리 (백준 18111)
• else에 비해 elif가 시간이 많이 걸린다고 하여 elif -> else로 수정 (백준 18111)
• 한번만 처리해 주면 되는 코드를 반복문 안에서 매번 실행시켰던 실수 수정 (백준 18111)
• 재귀 함수(Top-Down)로 구현된 동적 프로그래밍을 반복문(Bottom-Up)으로 변환 (백준 1003)
• sum(arr[start:end]) 대신 input 받을 때 누적합을 계산하여 시간 단축 (백준 11659)
• slicing 크기(end-start)를 줄이고 cursur, check 등 변수 추가해서 탐색 (백준 5525)
• heapq 사용, check 배열 만들어서 두 배열 동기화, 원소들을 (숫자, index)로 저장하여 check 배열 접근 (백준 7662)
• 표현하는 수의 크기가 커지면 메모리 초과와 함께 연산이 오래 걸려서 시간 초과까지 발생 -> 연산 중 나머지 계산 (백준 1904)
• 스택을 이용하여 문자열을 순차적으로 처리하면서도 제거 작업을 효율적으로 수행 (백준 9935 문자열 폭발 문제)
• 같은 알파벳 칸 두 번 방문 불가 => 26개의 아스키 문자 개념 사용해서 [ord(문자)-65]로 방문 index 처리 해줌 (백준 1987)
• checked 배열 만들어서 방문 여부 확인하는 것 대신 set을 만들어서 방문한 값들을 넣고, 탐색 후 값 계산하는 방식으로 시간 단축 (백준 16946) -> 배열 크기가 너무 크다면 배열 초기화에도 시간 소요됨
• 불필요한 elas문 사용 제거 (백준 2467)
• 반복문 밖에서 정의해도 되는데, 안에 정의하여 불필요한 동작을 반복수행하고 있진 않은지 항상 확인 필요 (boj 2866)
• 백트래킹 탐색 과정이 순서대로 이루어지기 때문에 min값 저장 후 return이 아니라 바로 exit() 하는 것으로 수정 (boj 2661)
• 백트래킹 문제) 1~9까지 모든 수를 탐색하지 않고, 탐색하지 않을 숫자를 조건에 맞게 미리 remove 후 탐색 (boj 2580)
• 이전에 방문한 좌표 이후의 좌표만 탐색 (boj 18290)
• in 연산은 list에 할 땐 O(N)인데, set에 할 땐 O(1) (boj 13144)
• 투포인터 로직 측면) start가 업데이트 될 때마다 리스트를 초기화하지 않고 add, remove 연산을 수행하면 end 탐색 과정을 단축 시킬 수 있음 (문제 참고) (boj 13144)

[2018007956]

• 백준 18111번 마인크래프트 문제 시간 복잡도 계산 과정 의문 : 2중 포문 돌리면 시간 초과 떠야된다고 생각했는데, 안 뜨는 이유가 궁금하여 게시판 질문 https://www.acmicpc.net/board/view/141727 => 코드를 돌아가는 구조를 분석하면 257^2회가 되어서 넉넉하게 돌아감

[2018007956]

• 동적 프로그래밍의 구현 방법
  • Top-Down : 주로 재귀함수로 구현
  • 장점 : 코드 가독성 높음
  • 단점 : 많은 스택 메모리 사용할 수 있으며, 메모이제이션의 처리 오버헤드 존재 가능
  • Bottom-Up : 주로 반복문으로 구현
  • 장점 : 스택 메모리를 사용하지 않아 메모리 절약 효과, 메모이제이션의 처리 오버헤드가 없음
  • 단점 : 코드 가독성 낮음

[2018007956]

• 백준 9019번 DSLR 문제
  • [BFS 구현] Python3 제출 시 시간 초과, PyPy3 통과
  • Python3로 통과된 코드 : 역방향도 고려해줌 -> 코드 공부해보기

[2018007956]

• 최소 최댓값을 빠르게 출력해내야 할 때, heapq 사용
  • https://github.com/2018007956/Teamnote-archive/issues/2