1.4.29 중복 값 찾기. 1
에서 n
까지의 값을 가진 요소 n
개를 가진 배열이 있을 때, 중복된 값이 있을지 판단하는 코드를 작성하라. 주어진 배열의 내용을 보존할 필요는 없지만, 별도의 배열은 사용하지 않아야 한다.
1.4.30 소수 세기. primesieve.py
(프로그램 1.4.3)와 다른 방법(연습문제 1.3.34)을 비교하라. 이 문제는 공간-시간 타협의 사례로서, primesieve.py
는 빠르지만 길이 n
인 불형 배열이 필요하고, 다른 방법은 정수 변수 두 개만 사용하지만, 상당히 느리다. python3 primesieve.py 1000000
을 실행하는 시간과 동일한 시간에 다른 방법으로 계산할 수 있는 n
의 값을 찾아, 이 둘 간의 실행 시간 차이가 어느 정도 규모인지 추정해보라.
1.4.31 지뢰 찾기. 명령 줄 인수로 m
, n
, p
를 입력받아 요소가 모두 확률 p
인 m x n
불형 배열을 생성하라. 지뢰 찾기 게임에서 점유된 셀은 폭탄을, 빈 셀은 안전한 셀을 나타낸다. 폭탄이 있는 셀은 별표, 안전한 셀은 점을 이용해 배열을 출력하라. 그러고 나서 안전한 셀은 이웃한 셀(상하좌우 및 대각선, 총 8개의 셀) 중 폭탄이 있는 셀의 수로 바꿔 다음과 같은 형태로 출력하라.
* * . . . * * 1 0 0 . . . . . 3 3 2 0 0 . * . . . 1 * 1 0 0
(m+2) x (n+2)
크기의 불형 배열을 이용해 예외 처리는 최소로 하면서 코드를 표현해보라.
1.4.32 자기-회피 보행 길이. 격자의 크기에 제한이 없다고 가정하자. 실험을 통해 평균 보행 거리를 추정해보라.