동적 기획 과 몰 투표 법

동적 계획
위 키 피 디 아 는 동적 계획 (Dynamic programming · DP 로 약칭) 에 대해 수학, 관리 과학, 컴퓨터 과학, 경제학, 생물 정보 학 에서 사용 하 는 것 으로, 원 문 제 를 상대 적 으로 간단 한 하위 문제 로 분해 하 는 방식 으로 복잡 한 문 제 를 푸 는 방법 을 정의 한다.
피 보 나치 수열
피 보 나치 수열 은 원 문 제 를 상대 적 으로 간단 한 서브 문제 로 분해 하 는 전형 적 인 방식 으로 복잡 한 문 제 를 해결 할 수 있 는 예 이다.다음은 피 보 나치 수열 의 수학 적 정의 이다.

F(0)=0，F(1)=1

F(2)=F(1)+F(0)=1+0=1

F(n)=F(n-1)+F(n-2) (n>=2)

이 수학 정의 에 따 르 면 우 리 는 재 귀적 인 방식 으로 이 알고리즘 을 쉽게 실현 할 수 있다.

package main

import (
    "fmt"
    "time"
)

func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

func main() {
    start := time.Now().Unix()
    fib(45)
    end := time.Now().Unix()
    fmt.Println(end-start)
}

위의 코드 는 우리 가 구 하 는 것 은 F (45) 이다. 코드 는 매우 간단 하지만 계산 시간 이 6 초 정도 되 고 효율 이 매우 낮다. 다음은 방금 코드 에 따라 그 려 진 F (5) 의 트 리 그림 이다. 그림 에서 알 수 있 듯 이 F (3) 는 2 번 계산 하고 F (2) 는 3 번 계산 하 며 F (1) 는 4 번 계산 하고 중복 계산 이 많이 발생 했다. 이것 도 효율 이 낮은 원인 이다.최적화 해 야 할 사고방식 은 이런 불필요 한 중복 계산 을 없 애 는 것 이다.이제 우 리 는 모든 하위 문제 의 계산 결 과 를 저장 합 니 다. 같은 하위 문제 에 다시 부 딪 혔 을 때 이전에 저 장 된 결과 에서 직접 값 을 얻 을 수 있 으 니 다시 계산 하지 않 아 도 됩 니 다.예 를 들 어 계산 F (2) 를 처음 만 났 을 때 하나의 사전 으로 F (2) 의 계산 결 과 를 저장 할 수 있 습 니 다. 계산 F (2) 를 다시 만 났 을 때 사전 에서 직접 값 을 얻 을 수 있 습 니 다. 개 조 된 코드 는 다음 과 같 습 니 다.

package main

import (
    "fmt"
    "time"
)

var m = map[int]int{0:0, 1:1}
func fib(n int) int {
    if v, ok :=m[n]; ok {
        return v
    }
    m[n-1],m[n-2] =fib(n-1),fib(n-2)
    return m[n-1]+m[n-2]
}

func main() {
    start := time.Now().UnixNano()
    fib(45)
    end := time.Now().UnixNano()
    fmt.Println(end-start)
}

개 조 를 거 쳐 F (45) 를 계산 하 는 것 은 1 초도 안 된다.일단 정자 문제 에 대한 해답 이 계산 되면 다음 에 같은 하위 문제 가 해 제 될 때 직접 표를 찾 는 것 도 동적 기획 의 중요 한 내용 이다.
그래서 동태 계획 의 두 가지 가장 중요 한 점 은:
4. 567917. 복잡 한 문 제 를 몇 개의 키 문제 로 나 누 었 다
4. 567917. 모든 하위 문제 의 결 과 를 저장 하여 모든 하위 문 제 를 한 번 만 해결 하도록 한다
House Robber
다음은 LeetCode 의 이전 House Robber 라 는 제목 을 동적 기획 방법 으로 해결 하 는 것 입 니 다.
당신 은 전문 적 인 도둑 으로 길 을 따라 있 는 집 을 훔 칠 계획 입 니 다.모든 방 안에 일정한 현금 이 숨겨 져 있 는데 도 난 에 영향 을 주 는 유일한 제약 요 소 는 바로 인접 한 집 이 서로 연 결 된 도 난 방지 시스템 을 설치 하 는 것 이다. 만약 에 인접 한 집 두 칸 이 같은 밤 에 도둑 에 게 침입 하면 시스템 은 자동 으로 경찰 에 신고 할 것 이다.
각 집의 보관 금액 을 대표 하 는 비 마이너스 정수 그룹 을 지정 하여 경보 장 치 를 건 드 리 지 않 은 상태 에서 훔 칠 수 있 는 최고 금액 을 계산한다.
현재 각 주택 이 보관 하고 있 는 금액 이 각각 2, 7, 9, 3, 1 이 라 고 가정 하여 최대 훔 칠 수 있 는 금액 을 구한다.
우 리 는 P (n) 로 총 n 칸 짜 리 집 이 있 을 때 훔 칠 수 있 는 최대 금액 을 표시 하고 r (n) 로 n 번 째 집에 보관 할 수 있 는 금액 을 표시 합 니 다.n 이 1 일 때 P (1) = r (1), n 이 2 일 때 P (2) = Max (r (1), r (2).제목 은 인접 한 방 두 칸 을 약탈 할 수 없 도록 요구 하기 때문에 n 칸 이 있 을 때 P (n) = Max (P (n - 2) + r (n), P (n - 1).방정식 으로 표시 하면:

P(1)=r(1)
P(2)=Max(r(1), r(2))
P(n)=Max(P(n-2)+r(n), P(n-1))

그래서 이 문 제 는 몇 개의 키 문제 로 분해 되 었 고 다음은 코드 가 실현 되 었 다.

package main

import "fmt"

var m = map[int]int{}

func rob(arr []int) int {
    l := len(arr)
    if l <= 0 {
        return 0
    }
    if v,ok:=m[l-1];ok{
        return v
    }
    if l == 1 {
        m[0]=arr[0]
        return arr[0]
    }
    if l == 2 {
        if arr[0] >= arr[1] {
            m[1]=arr[0]
            return arr[0]
        } else {
            m[1]=arr[1]
            return arr[1]
        }
    }
    a, b:= rob(arr[:l-2])+arr[l-1],rob(arr[:l-1])
    if a>=b{
        m[l-1]=a
    } else {
        m[l-1]=b
    }
    return m[l-1]
}

func main() {
    arr := []int{2,7,9,3,1}
    m[0]=arr[0]
    ret :=rob(arr)
    fmt.Println(ret)
}

위의 코드 는 바로 우리 가 방정식 에 따라 머리 없 이 쓴 알고리즘 에 따라 최대 금액 을 훔 치 는 목적 을 달성 한 것 이다. 그러나 사실은 최적화 공간 이 있다. 우 리 는 P (n) 를 계산 하려 면 예전 의 P (n - 2) 와 P (n - 1) 만 기억 하면 된다. 그러나 우 리 는 사실 P (1), P (2),..., P (n - 2) 를 모두 기억 하고 메모리 낭 비 를 가 져 왔 다.이 문제 가 발생 한 이 유 는 우리 가 P (n) 를 풀 때 P (n - 1), P (n - 2),..., P (1) 는 위 에서 아래로 구 해 지 는 방식 이기 때 문 입 니 다. 아래 에서 위로 구 해 지 는 방식 으로 바 꾸 면 다음 과 같은 코드 를 쓸 수 있 습 니 다.

package main

import "fmt"

func rob(arr []int) int {
    pre1, pre2 := 0, 0
    for _,v := range arr {
        if pre2+v >= pre1 {
            pre1,pre2 = pre2+v,pre1
        } else {
            pre1,pre2= pre1,pre1
        }
    }
    return pre1
}

func main() {
    arr := []int{2,7,9,3,1}
    ret :=rob(arr)
    fmt.Println(ret)
}

위의 변 수 는 pre 1 과 pre 2 는 각각 P (n - 1) 와 P (n - 2) 를 나타 내 는데 이렇게 하면 아래 에서 위로 결 과 를 구 할 수 있 고 위 에서 아래로 하 는 것 보다 메모 리 를 절약 할 수 있다.
그래서 동태 계획 이 기억 해 야 할 몇 가지 관건 은 복잡 한 문 제 를 몇 개의 키 문제 로 나 누고 서브 문제 의 결 과 를 기억 하 며 위 에서 아래로, 아래 에서 위로 나 누 는 것 이다.
몰 투표 법
만약 10 명 이 투표 에 참여 한다 면, 어떤 사람 은 A 에 게, 어떤 사람 은 B 에 게, 어떤 사람 은 C 에 게 투표 할 것 이다. 우리 가 A, B, C 가 누가 가장 많은 표를 얻 었 는 지 찾 으 려 고 할 때, 우 리 는 두 개의 서로 다른 투 표를 한 쌍 으로 삭제 할 수 있다. 더 이상 삭제 할 수 없 을 때 까지 그 결과 에 남 은 투표 가 가장 많은 표를 얻 은 것 이다.예 를 들 어 상기 10 명의 투표 상황 은 [A, B, C, C, B, A, A, B, A] 이 고 다음은 삭제 하 는 과정 이다.

[A,B,C,C,B,A,A,A,B,A]==>[C,C,B,A,A,A,B,A] //A,B          
                                          //        
[C,C,B,A,A,A,B,A]==>[C,A,A,A,B,A] //C,C           ，  
                              //          C,B         
[C,A,A,A,B,A]==>[A,A,B,A]
[A,A,B,A]==>[A,A]                 

끊임없이 서로 다른 투 표를 한 쌍 으로 삭제 함으로써 투표 결과 마지막 에 [A, A] 만 남 았 기 때문에 A 가 가장 많은 표를 얻 었 다.몰 투표 법의 핵심 은 서열 에 있 는 두 개의 서로 다른 요 소 를 상쇄 하거나 삭제 하 는 것 이다. 서열 마지막 에 하나의 요소 나 여러 개의 똑 같은 요 소 를 남 긴 다 면 이 요 소 는 가장 많이 나타 난 요소 이다.
Majority Element
구 중 수 는 바로 몰 투표 법의 전형 적 인 운용 장면 이다. 예 를 들 어 다음 과 같은 알고리즘 문제 가 있다.
n 크기 의 배열 을 지정 하여 그 중의 중 수 를 찾 습 니 다.중 수 는 배열 에서 n / 2 이상 나타 나 는 요 소 를 말한다.주어진 배열 [2, 2, 1, 1, 1, 2, 2, 4, 5, 2, 3, 2, 2] 그 중 수 를 찾 아 라.
구현 코드 는 다음 과 같 습 니 다:

package main

import "fmt"

func main() {
    arr := []int{2,2,1,1,1,2,2,4,5,2,3,2,2}
    maj, count := arr[0], 1
    for i:=1;i

코드 에서 먼저 배열 의 첫 번 째 요 소 는 중수 라 고 가정 하고 하나의 변수 count 로 이 중수 가 나타 난 횟수 를 기록 합 니 다. 교 체 된 숫자 가 이 중수 와 같 을 때 count 는 1 을 추가 하고 다 를 때 상쇄 작업 을 합 니 다. 즉, count 가 1 을 줄 이면 count 가 0 일 때 교체 되 는 수 를 새로운 중수 로 설정 하고 count 를 1 로 설정 합 니 다.
이상 은 몰 투표 법의 원리 와 응용 이다.