swift ) 백준 1149 - RGB거리 feat.cache

 

DP문제이다.

두 가지 코드를 작성했는데

1. 2d array를 하나 만들어서 그 배열에 있는 값들을 수정함(dp)

2. 2d array를 두개 만들어서 하나는 입력받은 값을 저장, 하나는 연산한 값을 넣음.

 

1. 

let num = Int(readLine()!)!
var dp = [[Int]]()
for _ in 1...num {
	dp.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

for i in 1..<num {
	dp[i][0] = dp[i][0] + min(dp[i-1][1],dp[i-1][2])
	dp[i][1] = dp[i][1] + min(dp[i-1][0],dp[i-1][2])
	dp[i][2] = dp[i][2] + min(dp[i-1][1],dp[i-1][0])
}

print(dp[num-1].min()!)

 

 

2.

let num = Int(readLine()!)!
var arr = [[Int]]()

for _ in 1...num {
	arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

var dp = Array(repeating: Array(repeating: 0, count: 3), count: num)

for i in 1..<num {
	dp[i][0] = arr[i][0] + min(dp[i-1][1],dp[i-1][2])
	dp[i][1] = arr[i][1] + min(dp[i-1][0],dp[i-1][2])
	dp[i][2] = arr[i][2] + min(dp[i-1][1],dp[i-1][0])
}

print(dp[num-1].min()!)

 

 

처음 작성했던 코드는 2번인데, 제출한 사람들 코드를 보니 1번으로 하는게 더 코드도 짧고, 빨라보여서 수정해봄

결과는 놀랍게도 1번의 속도가 더 빨랐다.

입력한 데이터가 클 수록 속도의 차이도 꽤 났다.

귀찮아서(....) 정말 큰 테스트케이스는 만들어보지 않았지만

입력한 값이 10,20개가 되었을 때 속도 차이가 7,8배정도로 벌어졌다.

 

왜????????

궁금해서 찾아보고, 물어보고 다닌 결과...

캐시 문제가 아닐까 라는 결론을 얻게 되었다.

 

https://parksb.github.io/article/29.html

💵 캐시가 동작하는 아주 구체적인 원리: 하드웨어로 구현한 해시 테이블

 

 

두 코드의 차이는 고정된 값을 가진 배열로부터 값을 읽어오는 것 / 값이 계속 변하는 배열로부터 값을 읽어오는 것인데

2의 경우 캐시에서 업데이트된 값을 메모리에 쓰는 과정이 추가되기도 하고,

바뀐 값에 대한 캐시를 다시 불러오는 과정이 있기 때문에 1과 속도차이가 나는 것 같다.