https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
1. 동기
N-Queen 문제를 파이썬으로 풀어보며 이 문제에 대해 생각해보게 됐다.
분명 같은 알고리즘을 이용해 C++로 구현한 코드는 통과가 되는데, 파이썬은 통과가 되지 않는다.
흔히들 파이썬의 단점을 꼽으면 시간이 오래 걸린다는 점을 꼽는다.
그렇다면 왜 시간이 오래 걸리는 것일까?
2. 핵심 이유
https://jhkang-tech.tistory.com/136
인터프리터 언어와 컴파일 언어의 차이
안녕하세요 강정호입니다. 오늘은 인터프리터 언어와 컴파일 언어의 차이에 대해서 알아보겠습니다. 인터프리터언어 인터프리터 언어는 원시코드(프로그래머가 작성한 소스코드)를 기계어로
jhkang-tech.tistory.com
파이썬은 인터프리터 언어, C 혹은 C++은 컴파일 언어이기 때문이다.
인터프리터 언어와 컴파일 언어의 결정적인 차이는 빌드의 유무이다.
컴파일 언어는 코드를 기계어로 변환한 후, 프로그램을 실행하는 반면
인터프리터 언어는 코드를 한줄씩 읽으며 기계어로 변환하지 않고 실행하게 된다.
때문에 빌드가 끝난 컴파일 언어 실행 프로그램이 훨씬 빠른 실행 속도를 갖게 되는 것이다.
3. 시간초과를 해결하기 위해 알고리즘 풀이에 사용할 수 있는 몇몇 기술들
1) sys.stdin.readline()
일반적으로 사용하는 input함수는 Prompt메시지를 출력한 후, 입력받는 한글자씩 버퍼에 저장해 처리하게 된다.
반면 readline메소드는 Prompt메시지 출력도 없으며, 한 줄을 통째로 버퍼에 저장하기 때문에 시간이 훨씬 절약된다.
나는 보통 input = sys.stdin.readline을 프로그램 초반부에 선언해 input을 대체시켜 사용한다.
이것만 바꿔도 해결되는 문제가 아주아주 많다..!
2) 포함 여부를 확인할 때는 set 사용
배열을 이용해 in 명령어를 사용하면 포함 여부를 사용할 수 있으나,
처음 요소부터 하나 하나 확인하므로 최대 n의 시간이 걸린다.
반면 set을 이용해 같은 코드를 수행하면 O(1)의 시간 복잡도로 수행 가능하다.
3) pop(0)을 사용해야 할 때는 deque 자료형의 popleft()사용
큐를 필요로 할 때, 일반 리스트로 만들고 pop(0)을 사용하는 경우가 있는데,
pop(0)메소드는 첫번째 인자를 추출하고 나머지 인자를 앞으로 당겨오기 때문에 O(N)의 시간복잡도가 소요된다.
collections 모듈의 deque을 사용하여 popleft()메소드를 사용하면 같은 기능을 O(1)의 시간복잡도로 구현 가능하다.
4) 재귀 횟수 초과 오류가 날때
종종 재귀 횟수 초과 메시지가 뜨는 경우가 있다.
사실 이 경우에는 시간이 오래 걸리기 때문에 동적 프로그래밍을 이용해 해결하는 것이 낫겠지만,
재귀로밖에 해결할 수 없는 상황이라면 sys.setrecursionlimit(n) 메소드를 이용해 재귀 한도치를 재설정하자.