7개의 댓글이 있습니다.

• 
  Being

  첫 번째 문제는 A에다 대고 이분검색하면 되겠네요. 원소 하나 잡아서 그게 A에서 i번째 원소라고 하면, B에서 정확히 어떤 위치를 찾아서 확인할 수 있는지 결정되니 그렇게 해결하면 되겠습니다.

  두 번째 문제는 잘 모르겠네요.

  
  11년 전 link

• 
  mujugi

  1) 첫번째 문제는 배열이 꽈배기 같이 순서가 꼬여있을때 좀 헷갈리는 겉가아요 (변형된 바이너리 서치를 하면 될 것같은 느낌이긴합니다)
  a = [10,20,30,40,50,60,70,80,90]
  b= [1,2,25,30,43,56,74,65,120]

  k = 2 라고 가정
  a = 50 -> 인덱스 2보다큼 -> 10,20,30,40 -> 20 인덱스 2보다큼
  b= 43 -> 인덱스 2보다큼 -> 1,2,25,30,43 -> 25 인덱스 2보다큼
  -> 10,20 인덱스 2 -> a > b -> 10 ->
  -> 1,2 인덱스 2 -> a > b -> 1,2 -> 2

  이런 로직일것 같고요 (생각은 되는데 코딩이 안되네요)

  
  11년 전 link

• 
  sven

  K 랑 N 이 의미하는 바가 무엇인가요?
  1번은 바이너리 서치를 이중으로 하면 log A log B 로 풀릴 것 같네요.
  2번은 문제가 좀 이상한 것 같습니다. log N 해법이 존재한다고 가정하면 임의의 주어진 배열에 대해 맨 뒤에 찾기를 원하는 원소와 같은 값을 지니는 원소를 추가하면 그냥 탐색 문제로 귀결되는데, 정렬되어있지 않은 경우에 대해서 log N 해법은 없죠.

  
  11년 전 link

• 
  Kureyo

  2번 문제는 1<=A_i<=n같은 제한 조건이 있을거 같은 느낌이 드네요.

  
  11년 전 link

• 
  Kureyo

  A_i <= A_(i+1) <= A_i + 1이라는 조건하에선 lgN이 가능할거같은데 그게 아니라면 모르겠네요

  
  11년 전 link

• 
  Being

  앞에도 설명했듯 첫 번째 문제는 그냥 바이너리 서치 한 번으로 풀립니다. 첫 번째 배열에서 i번째 원소 하나를 잡아서 그 값을 A_i라 하면 두 번째 배열에서 어떤 위치를 검사해야 할 지 그냥 알 수 있습니다. 검사해야 할 위치를 j라 하면 B_j, B_j+1과 A_i 사이의 관계로 메디안이 어디에 있을 지 알 수 있습니다.

  첫 번째 배열에 없다면 다음 배열에서 찾아보면 됩니다.

  
  11년 전 link

• 
  sven

  아, 그렇네요.

  
  11년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.