rdd6584   3년 전

제목 그대로 배열을 변경시키지 않고 k번째 수를 찾는 방법이 있을까요?

O(n) 시간대에 끝나야 하는데, quick select를 구현했는데, 배열의 값이 계속 변경되서 골치네요ㅠㅠㅠ.

chogahui05   3년 전

어떤 문제에서 필요할까요???

혹시 k번째 수 찾기 문제 말씀하시는 건가요?

djm03178   3년 전

단순히 k번째 수를 찾는 거라면 배열의 값이 변경돼도 상관 없죠. 굳이 변경이 안 되게 하려면 전체를 다른 배열에 복사해두고 찾아도 되고요.

rdd6584   3년 전

우선 답변 감사합니다. 문제는 중앙값 찾기 문제입니다.

중앙값을 N - k 번 찾아야 해서 과정을 여러번 반복해야했어요.

quick select로도 풀 수 있다고 들어서 전체를 다른 배열에 복사해두고 하는 방식으로 하고, 시간초과 나는지 지켜봐야겠네요. ㅠㅠ

nth_element도 알아보고 안되면 다른 구현빡센 알고리즘으로 풀어보려구요.

djm03178   3년 전

중앙값 문제는 퀵 셀렉트로는 시간 복잡도상으로도 안 풀립니다. 한 번의 검색이 lgN이나 lgK 시간 내에 끝나는 방법을 찾아야 됩니다.

rdd6584   3년 전

네 감사합니다.

그러면 혹시 하나만 더 여쭤봐도 될까요?


if (mat[x + 1][y] == '.') {
  memcpy(temp, mat, sizeof(mat));
  for (i = x + 1; mat[i][y] == '.'; i++)
    mat[i][y] = '*';
  c1 = go(i - 1, y) + 1;
  memcpy(mat, temp, sizeof(mat));
}

if (mat[x - 1][y] == '.') {
  memcpy(temp, mat, sizeof(mat));
  for (i = x - 1; mat[i][y] == '.'; i--)
    mat[i][y] = '*';
  c2 = go(i + 1, y) + 1;
  memcpy(mat, temp, sizeof(mat));
}

if (mat[x][y + 1] == '.') {
  memcpy(temp, mat, sizeof(mat));
  for (i = y + 1; mat[x][i] == '.'; i++)
    mat[x][i] = '*';
  c3 = go(x, i - 1) + 1;
  memcpy(mat, temp, sizeof(mat));
}

if (mat[x][y - 1] == '.') {
  memcpy(temp, mat, sizeof(mat));
  for (i = y - 1; mat[x][i] == '.'; i--)
    mat[x][i] = '*';
  c4 = go(x, i + 1) + 1;
  memcpy(mat, temp, sizeof(mat));
}


배열 같은 경우는 인자에다가 넣어도 파라미터로 전달이 되잖아요?

그런데 재귀함수가 돌면서 배열원본이 변경되지 않도록 하기 위해 다음처럼 조금 비효율적인 코드를 짜곤 하는데,

혹시 이걸 해결할 수 있는 방법이 있을까요?

rdd6584   3년 전

문제는 MxN 보드 완주하기입니다.

djm03178   3년 전

문제를 풀어보지 않아서 무엇에 필요한 코드인지는 모르겠지만, 값을 변경할 지점의 위치만 따로 모아 기록해뒀다가 사용이 끝나면 원래대로 돌려놓는 방법이 있겠습니다만, 한 번에 묶어서 처리하는 memcpy보다 효율성이 높을 것 같지는 않네요.

rdd6584   3년 전

답변이 도움이 됐습니다 .정말 감사합니다

댓글을 작성하려면 로그인해야 합니다.