주옥 노트

  • 한 파일에 천만(100000000)개의 7자리 정수(1천만보다 작음)가 있는데, 약 1M 메모리에 정렬을 양보한다.
  • 비트맵(bitmap), 길이 10000000의bit수 그룹 a를 0으로 초기화하고 숫자 x가 나타나면 a[x]=1을 출력한 다음에 표지 위치가 1인 다음 표지 번호를 순서대로 출력한다.10000000bit == 1250000byte == 1220K == 1.19M.
  • 만약에 엄격하게 1M을 이중 채널 프로그램으로 만들면 첫 번째 표기 전 500만 출력, 두 번째 표기 후 500만 출력이다.

  • 벡터 회전: abcdefgh(길이 n은 8), 왼쪽 회전 i=3회
  • 3차반전법
    i = i % n #n   
    reverse(0, i-1) #cbadefgh
    reverse(i, n-1) #cbahgfed
    reverse(0, n-1) #defghabc
    
  • 오른쪽으로 회전하면: 먼저 모드를 취하고ii=i%n, 오른쪽으로ii회 회전하면 왼쪽으로 n-ii회
  • 모 파일은 40억 개의 무작위 순서 32자리 정수를 포함하고 그 중 한 개의 정수가 나타나지 않아 찾아낸다.제한: 메모리 수백 바이트, 몇 개의 순서 파일.
  • 먼저 가장 높은 위치가 1인 것을 파일 a에 쓰고 가장 높은 위치가 0인 것을 파일 b에 쓰고 각각counta,countB를 계산한다.만약 최고위가 1인 정수가 모두 나타난다면counta>countB & &counta==2^31, 파일 b에서 찾으면 부족한 것은 반드시 최고위가 0이다.같은 이치로 두 번째 최고위, 세 번째 최고위를 찾을 때까지 구분한다
  • 한 사전에는 230000개의 단어가 있는데, file과life는 변위어이며, 모든 변위어를 찾아내는 어집이다.
  • 단어마다 순서대로 서명하여 변위어가 유일하게 같은 서명을 가지고 있는지 확인한다. 예를 들어 단어 자모를 승차순으로 배열하고 변위어를 정렬한 후 결과가 일치하도록 한다.그리고 서명 순서에 따라 각 서명의 변위 어집을 순서대로 출력한다
  • 커피 캔 문제: 검은색 콩과 흰색 콩이 들어 있는 커피 캔과'추가적'인 검은색 콩 한 무더기를 캔에서 두 개의 콩을 골라 색깔이 같으면 버리고 검은색 콩을 넣는다.색깔이 통하지 않으면 흰 콩을 항아리에 넣고 검은 콩은 버려라.항아리에 콩 한 알만 남을 때까지 상술한 과정을 반복한다.이 과정이 종료된다는 것을 증명하고, 마지막으로 남은 콩의 색깔은 초기 상태일 때 흰 콩과 검은 콩의 수량과 어떤 관계가 있는가?
  • 증명은 다음과 같다. 검은콩 B개, 흰콩 W개, 총수 S=B+W를 설정하고 콩 2개
    if bb:#   
        B=B-1; W=W; S=B-1+W
    elif ww: #   
        B=B+1; W=W-2; S=B+1+W-2
    else: #bw  
        B=B-1; W=W;; S=B-1+w
    
    를 취하면 매번 콩의 총수가 1씩 감소하기 때문에 과정은 반드시 종료된다.

  • bw와 bb가 같기 때문에 bb, ww 두 가지 상황만 있다고 볼 수 있다.매번 같은 색 bb, ww를 넣을 때마다 검은색을 넣기 때문에 콩의 수가 1개 또는 0개(0인지 1은 콩의 홀수 짝수에 달려 있다)로 줄어들기 전에 검은 콩을 다 뽑을 수 없다.그래서 우리는 간단하게 다음과 같이 요약한다. 바로 먼저 콩을 쌍으로 뽑아서 흰 콩 W=2n(짝수)을 뽑을 때 모든 콩을 먼저 뽑고 나머지는 검은 콩 B=B+n이다. 사실 지금 검은 콩의 수량은 상관없다. 모두 검은 콩이다. 흰 콩은 가입 경로가 없다. 마지막 라운드에 반드시 검은 콩이 흰 콩 W=2n+1(홀수)을 뽑을 때 먼저 쌍으로 콩을 뽑고 나머지 1개의 콩, 검은 콩 B=B+n을 뽑는다. 쌍으로 검은 콩을 뽑는다.최종적으로 반드시 1흑 1백이 남는다.1 검은색 1 흰색, 이색, 흰색 깡통, 검은색 버려.결국 화이트.결론: 흰 콩 짝수, 마지막은 검은 콩;팥 홀수, 마지막은 흰색
  • 최대 하위 벡터: 하나의 벡터로 모든 원소는 양과 음이 있고 최대 하위 벡터의 합을 구한다.
  • x = (31, -41, 59, 26, -53, 58, 97, -93, -23, 84)
    max_so_far = 0 #       
    max_ending_here = 0 #   0      i   
    for i in x:
         max_ending_here = max(max_ending_here+i, 0)#     
         max_so_far = max(max_so_far, max_ending_here)

  • 좋은 웹페이지 즐겨찾기