공부 기록장

코딩 테스트 문제 풀이 시 최소값과 최대값을 설정해야 하는 경우가 종종 있다. 문제에서 주어진 최대 범위를 활용해 설정해도 되지만 무한수로 설정하기도 한다. 예를 들면, 최단 경로 문제에서 도달할 수 없는 노드에 대한 거리를 설정할 때 무한(INF)으로 설정한다. 무한수를 설정하는 방법에는 크게 3가지 정도가 있다. 1. 지수 표현 가장 널리 쓰이는 방법인 것 같다. 문제에서 가능한 최댓값이 10억 미만이라면 초기화를 10억으로 해줄 수 있는데 1e9 혹은 -1e9 와 같이 지수 표현으로 10억을 설정해주면 0의 개수가 많아져서 실수하는 것을 줄일 수 있다. INF = 1e9 최대값의 범위에 따라 2e9 혹은 -2e9로 사용할 수도 있다. 2. sys.maxsize sys 라이브러리의 maxsize 를 ..

완전 탐색 문제를 푸는데 백트래킹을 알아야 시간 내에 풀리는 문제들이 많았다. 왜 완전 탐색 유형 문제인데 백트래킹이 나오지 하는 의문을 갔고 일단 나왔으니까 풀어야지 하는 생각을 풀었는데 알고보니, 백트래킹은 완전 탐색을 개선한 형태의 탐색 방식이었다. 완전 탐색 모든 경우를 탐색해가면서 무언가를 세거나 어떤 조건이 가능한 경우가 있는지 확인하는 방법 DFS/BFS도 결국 완전 탐색의 한 유형으로 이해할 수 있다. 사용하는 경우 발생 가능한 경우의 수가 충분히 적은 경우 따져야 하는 상황이 특정 규칙에 따라 발생하지 않는 경우 각각의 경우에 따져야 하는 상황이 명확한 경우 사용하는 방법 발생 가능한 모든 경우를 찾아낸다 각각의 경우에 대해 조건에 부합하는지 판단한다 백트래킹 재귀를 이용한 완전 탐색 방..

input()과 sys.stdin.readline()의 차이점 1. input() 입력 받은 값의 개행 문자를 rstrip() 함수를 적용해 삭제하고 리턴함 parameter로 promt message 입력 가능 2. sys.stdin.readline() 개행 문자를 포함한 값을 리턴 결론적으로 말하자면, input 함수는 메세지도 출력하고, 개행 문자를 삭제하고 리턴하기 때문에 sys.stdin.readline에 비해 속도가 느리다 따라서, 코딩 테스트에서 python으로 문제를 풀 때에는 input() 보다는 sys.stdin.readline()을 활용해 입력을 받는 것이 좋다. 구체적으로 말하자면, 1-2줄 입력일 때에는 크게 차이가 없을 수 있지만 반복문을 통해 여러 줄을 입력 받는 경우에는 in..

시작에 앞서, 알아야 하는 연산량에 따른 수행 속도 1억(100,000,000 = 10^8) → 1초 1. 입출력 제한 보고 파악하기 1) 입력이 100 이하인 경우 (입력값 범위가 매우 작은 경우) 완전 탐색 백트래킹 (?) 2) 입력이 10,000 (10^4, 만) 이하인 경우 최대 O( N^2 ) 이내로 끝내야 함 ( 문제따라 O( N^2 log N ) 까지도 허용) N x N 차원 리스트를 모두 순회하는 문제 ↑ 3) 입력이 1,000,000 (10^6, 백만) 이하인 경우 최대 O( N log N ) 으로 끝내야 함 힙, 우선순위 큐 정렬 DP 위상 정렬 다익스트라 알고리즘 4) 입력이 100,000,000 (10^8, 억) 이하인 경우 최대 O( N ) 으로 끝내야 함 DP 그리디 5) 그 이..