211009 토 Algorithms TIL

외벽점검

• 문제
• 코드
• 내가 푼 방식
  • weak point 간의 거리를 계산해서 1명 쓸 때는 그 거리가 제일 짧은 놈을 빼는 방식을 사용했는데
  • 아래와 같은 경우에 코드 돌리면 합이 같아 통과하지만 사실은 -1이다.
    

n = 100
peopple = [4, 2]
3 +3 = 4 + 2

출제 의도

• 카카오 문제풀이 https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/
• 원형으로 주어진 완전탐색 문제를 해결할 수 있는지 파악
• bit mask나, permutation 등을 활용할 수 있는지 파악
  해설

• dist의 길이가 최대 8로 크지 않기 때문에, 가능한 모든 방법을 탐색해서 해결할 수 있습니다. 따라서 dist에서 친구 한 명을 선택해 나열하는 방법, 친구 두 명을 선택해 나열하는 방법 … 친구 여덟 명을 선택해 나열하는 방법을 모두 고려해주면 됩니다.
• 이제 각각의 방법에 대해 취약지점을 모두 점검할 수 있는지 확인합니다. 먼저 점검해야 될 벽이 원형이 아니라 직선이라고 가정해 보면, 모든 취약지점을 점검하기 위해서는 시작 지점부터 순서대로 배정해야 된다는 점을 알 수 있습니다. 친구 한 명을 배정한 다음에는 아직 점검하지 않은 지점 중에서 바로 다음 지점에 친구를 순서대로 배정하면 됩니다.
• 배정을 마친 후에도 아직 점검하지 않은 취약지점이 남아있다면 해당 배치 방법으로는 모든 취약지점을 점검할 수 없다는 뜻입니다. 이제, 원형으로 이루어진 벽을 고려하기 위해, 다음 시작 지점을 기준으로 직선으로 펼쳐주면 됩니다.
• 예를 들어, N = 12, weak = [1, 5, 6, 10]인 경우 처음에 위치 1을 기준으로 직선으로 펼쳤다면, 이번에는 위치 5를 기준으로 [5, 6, 10, 13]과 같이 직선 형태로 만들어 주면 됩니다. 이때, 13은 값이 증가하는 형태로 만들어 주기 위해 1 + 12를 해준 결과입니다.
• 이제 각 친구들을 선택해 나열하는 방법에 대해서 모든 시작 지점에 대해 직선으로 펼친 후 취약 지점에 배정해본 다음, 그중 가장 적은 친구들을 선택하는 방법을 찾으면 됩니다.

동빈북 문제 풀이

• weak 리스트와 dist 길이가 매우 작다.
• 주어지는 데이터의 개수가 적을 때는 모든 경우를 일일이 확인하는 완전탐색 접근
• 문제에서 찾고자 하는 값은 '투입해야 하는 친구 수의 최솟값'
  • 친구의 전체길이는 최대 8
  • 모든 친구를 무작위로 나열하는 모든 수열 $_8{P}_8$ = 8$!$ = 40,320
• 원형 : 길이를 2배로 늘려서 '원형'을 일자 형태로 작업해주면 된다
  • https://yjyoon-dev.github.io/kakao/2021/01/04/kakao-wallcheck/
  • n=12 이고 weak = [1, 5, 6, 10] 일 때 weak = [1, 5, 6, 10, 13, 17, 18, 22] 로 표현한다.
  • [모든 K개의 외벽을 검사하는 것은 변형된 weak 배열에서 임의의 연속된 K개의 정점을 방문하는 것과 동일하다.]