백준 18353 병사 배치하기

LIS (Longest Increasing Subsequence) 최장 증가 부분 수열 구하기

 

움.. 여태까지 DP는 많이 풀어보진 않았지만 아직까지는 모든 문제가 그래프로 그려질 수 있는 문제 였습니다.

문제의 규칙을 알아보기 위해 그래프를 그려보자면 ?? 

 

DP 배열을 순차적으로 보여주는 그래프

i(인덱스)/ 전투력	15	11	4	8	5	2	4
초기상태	1	1	1	1	1	1	1
1	1	2	1	1	1	1	1
2	1	2	3	1	1	1	1
3	1	2	3	3	1	1	1
4	1	2	3	3	4	1	1
5	1	2	3	3	4	5	1
6	1	2	3	3	4	5	5

위 그래프는 DP 배열 이라고 생각하시면 됩니다.

예를 들면 반복문의 초기상태 DP 배열은 [1, 1, 1, 1, 1, 1, 1] 

1번째는 [1, 2, 1, 1, 1, 1, 1]

2번째는 [1, 2, 3, 1, 1, 1, 1]

...

배열의 각 요소는 i번째 요소를 포함한 최장 부분 증가 수열의 length 입니다.

 

LIS는 기본이 오름차순인데 이 문제는 내림차순으로 구하는 것 빼고는 다른점이 없습니다.

위 그래프를 자세히 보면

15 > 11 -> + 1

11 > 4 -> + 1

4 > 8 -> 그대로

규칙이 보이죠 ㅎ..ㅎ? 규칙 찾았으니 코드를 한번 볼게요.

 

코드

func sol() -> Int {
    let n = Int(readLine()!)!
    var arr = readLine()!.split(separator: " ").map{ Int(String($0))! }
    var dp = [Int](repeating: 1, count: n)
    
    for i in 1..<n {
        for j in 0..<i {
            if arr[i] < arr[j] && dp[i] < dp[j] + 1{
                dp[i] += 1
            }
        }
        
    }
    return n-dp.max()!
}

print(sol())

속도 : 20ms

 

let n = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int(String($0))! }
var dp = [Int](repeating: 1, count: n)

func sol() -> Int {
    
    for i in 1..<n {
        for j in 0..<i {
            if arr[i] < arr[j] && dp[i] < dp[j] + 1{
                dp[i] += 1
            }
        }
        
    }
    return n-dp.max()!
}

print(sol())

속도 : 52ms

 

의문점. 전역변수 지역변수 차이 밖에 없는데 왜 속도 차이가 나는지?

1. 전역변수는 일반적으로 최적화에 불리하다.

전역 변수는 절대 레지스터에 저장되지 않는다. 전역 변수는 포인터에 의한 간접 접근이나 함수 호출에 의해서 값이 변할 수 있기 때문에 레지스터에 저장될 수 없다. 그래서 항상 메모리에서 가져다 써야 해서 차이가 생길 수 있다.

출처: https://200315193.tistory.com/667 [quatre의 블로그]

또한 캐시 적중률 때문에 속도 차이가 날 수도 있는데, 자주 사용할 것 같은 변수를 캐시 메모리 에다가 넣는다. 전역 변수보다 지역 변수가 캐시 적중률이 높을 확률이 크다.

그렇지만 성능 때문에 전역변수를 안쓴다기 보다는 코드 버그 가능성에 좀 더 무게를 실어야 한다.

캐시 적중률에 관한 정보

https://velog.io/@springkim/C-%ED%95%98%EB%93%9C%EC%9B%A8%EC%96%B4%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EC%B5%9C%EC%A0%81%ED%99%94-%EA%B8%B0%EB%B2%95

[C] 하드웨어를 이용한 최적화 기법

최적화에 대한 참고 내용 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=knix008&logNo=221167323667 

[ C코드의 최적화 : 전역 변수 vs. 지역 변수 ]

 

결론

위의 코드를 보면 전역 변수를 반복문에 넣고 계속 사용하는데 그럼 메모리에서 CPU로 계속 꺼내서 사용할 수 밖에 없는데 여기서 레지스터 사용+캐시 적중률이 높은 지역 변수가 속도면에서 유리하다.