Week 2
이번 주의 내용은 Dynamic arrays and Amortized analysis에 관한 내용이었다.
우선 Dynamic arrays에 대한 내용이다.
우선 이전에 보았던 배열은 정적이라는 것에서부터 출발한다. 위와 같이 처음에 크기를 정하면 더이상 크기를 변경하지 못하게 된다. 이를 해결하기 위해 도입된 것이 동적할당배열이다.
동적배열은 얼만큼의 데이터가 입력될 지 알 수 없는 상황에서 굉장히 유용하게 사용될 수 있는 장점을 가지고 있다.
동적배열은 위와 같은 동작들을 통해 구현된다. Get은 i번째 요소를 반환하고 Set은 i번째 요소를 val값으로 설정한다. PushBack은 val를 해당 배열의 마지막에 위치시키고 Remove를 통해 i번째 요소를 제거할 수도 있다. Size로 몇개의 요소를 가지고 있는지도 확인이 가능하다.
실행시 위와 같은 인자들이 기준이 된다. arr은 동적배열을 가리키는 포인터이며 capacity는 동적할당된 배열의 총 크기, size는 현재 배열이 차지한 요소의 갯수를 의미한다.
예시를 들어 arr로 capacity가 2인 배열을 할당하고 PushBack으로 a를 입력할 수 있다. 이때 size는 1이다.
이후 b도 PushBack으로 입력이 가능하며 size가 2로 증가한 것을 볼 수 있다.
추가로 c를 입력하게되면 arr은 새로운 배열을 동적할당하게 되며 위의 예시에서는 capacity가 4인 배열을 가져온다.
arr는 새 배열을 가리키고 기존 값들을 새로운 배열에 하나씩 복사해 넣고 c도 채운 뒤 기존 배열을 삭제한 것을 볼 수 있다.
만약 d까지 입력되어 size 4, capacity 4로 동일한 상태일 때 e를 PushBack한다면 또 다시 더 큰 배열을 할당하고 arr는 새 배열로 옮기게 된다.
똑같이 모든 요소를 옮기고 마지막으로 e를 입력하고 마무리짓게 된다. size는 5, capacity는 8인 상태로.
동적할당배열이 어떤식으로 움직이는지는 API들을 보면 쉽게 알 수 있다. 먼저 Get은 리스트에 존재하는 요소에 대한 index가 들어오면 그 순번에 맞는 원소를 반환한다.
Set은 해당 자리에 요청한 값을 입력해준다.
PushBack은 이전의 순서처럼 size가 capacity와 같다면 새로운 배열(크기가 2배인)을 할당하여 모두 복사한 뒤 해당 값을 입력하며 아직 size가 capacity보다 작다면 그냥 입력하는 수순에 size만 증가시키는 것을 알 수 있다.
Remove는 단순히 index만 맞게 요청이 된다면 그 뒤의 단의 요소들을 앞쪽으로 당겨 복사하는 수순을 통해 제거를 한다. size는 1 줄어든다.
Size는 배열의 원소갯수를 반환한다.
일반적인 동적할당배열 용법으로 볼 때 C++에서는 vector로 사용하며 Java에서는 ArrayList로 Python에서는 list로 사용하는데 Python에서는 정적배열이 없다.
퀴즈가 먼저 나오는데 n개의 요소에 대해 PushBack이 가장 많이 실행되는 상황에서 Order은 몇번 소요되는 지에 대한 질문인데 위에 나왔듯 resize가 될 때 O(n)시행되는 것을 보았다.
해당 API들에 대한 순차 횟수이다.
요약내용이며 동적할당배열은 크기재조정이 가능하다는 장점을 가지고 있으며 이 때 최대 걸리는 순차는 O(n)이다.
이번에는 Amortized cost에 대한 내용을 공부한다. 첫번째로 Aggregate Mothod에 대한 내용을 공부한다.
동적배열의 크기재조정이 빈번함에 따라 여러번의 O(1)작용이 O(n) 이후에 진행되는데 이 때 전체 비용은 어떻게 되는지 계산하는 것이 핵심이다.
Amortized cost의 정의 자체는 위의 수식과 같다. 일례로 차를 구매하는데 5년의 주기를 가진다고 한다. 이 때 두가지 방안이 있는데 1번째는 5년에 한번씩 차값을 치루는 것인데 $6000이라고 할 때 한번 지불 시 $6000을 한번에 지급하고 5년뒤 또다른 차를 $6000에 구매하는 방식이다. 2번째는 이를 매달 나눠 계산하는 것으로 5년은 60개월이기 때문에 매월마다 $100를 지불하는 방식이되겠다. 이 때 매달 나눠 내는 비용이 Amortized cost가 된다.
밑의 내용이 마무리되기 전 퀴즈가 나왔는데 해당 수식에 가장 상계에 가까운것을 찾는 것인데 기하급수에 의거하여 위와 같은 정리가 완성된다고 한다.
동적배열의 예를 들어 Amortized cost를 계산해보려한다. n번의 PushBack이 있을 때 Ci를 cost of i'th insertion으로 보고 Ci를 계산하면, 먼저 크기재조정이 필요없을 때에 Ci은 1일 것이다. 그리고 재조정이 필요한 경우 복사해서 붙여넣어야하는 순서가 필요하므로 i -1을 더하게 된다. 이 때 2의 n승으로 더해지게 되는데 이는 배열할당 시 2배씩 늘어나기 때문이다.
따라서 수식화 하면 위와 같이 정리가 되며 최소 Order는 O(1), 최대 Order는 O(n)이 된다.
다음은 Banker's Method를 사용하여 Amortized cost를 이해하는데 추상적 개념으로 보고 넘어가면 될 듯하다. 마치 은행에 대출을 하고 매달 갚는 방식과 비슷하다고 생각하면 된다고 한다.
데이터 삽입시 마다 1 token이 들며 이후에 재조정이 필요할 때 옮기면서 사용이 되는 형식이다.
위와 같이 비어있는 배열에 a를 입력하고 여기에 token을 지불(추후에 이동할 때 사용될 비용 포함)하게 된다. token은 실질적 존재가 아닌 개념적 존재라는 것에 유의하자.
이후에 PushBack을 통해 b를 추가할 때 새로운 배열을 할당하여 데이터를 옮기고 추가한다. 이 때 동일하게 b에 token을 부여하고 a도 추가해주는데 총 3개의 token이 사용되었다고 설명한다. 1개는 실질적으로 사용이 완료되었고 2개는 현재 보류하고 추후에 사용될 예정인 것들이다.
PushBack으로 c를 입력하면 또 다시 새로운 배열을 할당하고 옮기면서 token을 소멸시킨다.
이 후 c를 추가시키고 새롭게 token을 부여하며 a에도 token을 걸어둔다.
PushBack으로 d를 추가하면서 token을 걸고,
그 후 b에도 token을 부여한다.
PushBack으로 e를 추가하면서 token들을 소멸시키고 새롭게 추가된 e와 a에 token을 부여한 것을 볼 수 있다.
사실 정리하면서 다시 보아도 정확이 어떤 개념인지 이해가 되질 않는다. 더 찾아본 뒤 업데이트를 해야겠다.
다음은 Physicist's Method이다 여기서 위치에너지가 운동에너지로 전환되는 예를 들면서 설명한다. 위에서 ∅는 potential energy를 의미한다. h0는 초기 데이터구조의 상태를 말하고 ht는 시간이 지난 후의 데이터 구조이며 이 때의 potential energy는 음수가 되지 않는다.
또한 해당 방법에서의 amortized cost는 Ct + ∅(ht) - ∅(ht-1)으로 표기되며 Ct가 작으면 그만큼 potential은 증가하고 크다면 감소한다.
cost의 수식을 재구성하면 위와 같이 다시 표현이 가능하며 중간에 상쇄되는 요소들로 마지막 줄과 같이 정리된다.
예를 들게되어 위와 같은 수식으로 결정하면 initial potential은 2 * 0 - 0 = 0이며 이후 포텐셜은 동일한 수식을 갖는데 이 때 0보다 큰 이유는 size가 capacity/2보다 크기 때문이다.
따라서 resize하는 경우의 amortized cost는 위와 같이 정리가 될 수 있으며 Ci는 1인데 resize가 아닌 상황에서 O(1)이 1이기 때문이다. capacity는 불변이므로 상쇄가 되겠고 이전 size와 이후 size의 차이는 1개의 요소만 추가되었기 때문에 1이고 이들을 정리하여 계산하면 3이된다. 이는 Banker's Method에서 보았던 것처럼 token이 3개가 사용된 것과 일치하는데 우연이 아닌 것이다.
이번엔 resize의 경우를 살펴보면 size와 cap이 같은데 이는 resize하는 경우에는 둘이 같아야 하기 때문이다. 그렇다면 ∅(hi-1)과 ∅(hi)는 위와 같이 정리가 될 것이고 결국 3으로 동일하게 수렴한다는 것을 알 수 있다.
이 퀴즈를 처음 봤을 때에는 정확히 몰랐기에 틀렸지만 이제는 확실히 위와 같은 과정을 거쳤다는 것을 알 수 있기때문에 이해가 가능했다.
Amortized Analysis에 대한 Summary로 접어들어 정리를 한다. 동적배열로 돌아와서 2배씩 증가시킨데 반해 1.5 혹은 2.5 아니면 이외의 factor로 증가계수를 바꾼다면 이 때에도 constant amount를 사용할 수 있는지에 대핸 질문을 던지고,
그 예로 10배를 택했을 때 aggregate method로 증명하는 모습이다. 결론적으로는 불가능하다고 정리를 하며 이는 두배로 증가시킬 때 O(1)으로 cost가 적었던 것에 비해 열배로 바꾸니 O(n)으로 cost가 증가한 것을 확인할 수 있었다. 즉 constant factor를 사용하는 것이 중요하다고 정리한다.
3가지 Method를 통해 amortized cost를 계산하는 것에 대해 알아볼 수 있었고 주어진 수식을 통해 계산해보는 시간이었다. 잘 이해가 안되는 부분이 중간중간 있었기에 한번 더 개념을 찾아봐야 할 것 같다.
이번 주의 내용은 Dynamic arrays and Amortized analysis에 관한 내용이었다.
우선 Dynamic arrays에 대한 내용이다.
우선 이전에 보았던 배열은 정적이라는 것에서부터 출발한다. 위와 같이 처음에 크기를 정하면 더이상 크기를 변경하지 못하게 된다. 이를 해결하기 위해 도입된 것이 동적할당배열이다.
동적배열은 얼만큼의 데이터가 입력될 지 알 수 없는 상황에서 굉장히 유용하게 사용될 수 있는 장점을 가지고 있다.
동적배열은 위와 같은 동작들을 통해 구현된다. Get은 i번째 요소를 반환하고 Set은 i번째 요소를 val값으로 설정한다. PushBack은 val를 해당 배열의 마지막에 위치시키고 Remove를 통해 i번째 요소를 제거할 수도 있다. Size로 몇개의 요소를 가지고 있는지도 확인이 가능하다.
실행시 위와 같은 인자들이 기준이 된다. arr은 동적배열을 가리키는 포인터이며 capacity는 동적할당된 배열의 총 크기, size는 현재 배열이 차지한 요소의 갯수를 의미한다.
예시를 들어 arr로 capacity가 2인 배열을 할당하고 PushBack으로 a를 입력할 수 있다. 이때 size는 1이다.
이후 b도 PushBack으로 입력이 가능하며 size가 2로 증가한 것을 볼 수 있다.
추가로 c를 입력하게되면 arr은 새로운 배열을 동적할당하게 되며 위의 예시에서는 capacity가 4인 배열을 가져온다.
arr는 새 배열을 가리키고 기존 값들을 새로운 배열에 하나씩 복사해 넣고 c도 채운 뒤 기존 배열을 삭제한 것을 볼 수 있다.
만약 d까지 입력되어 size 4, capacity 4로 동일한 상태일 때 e를 PushBack한다면 또 다시 더 큰 배열을 할당하고 arr는 새 배열로 옮기게 된다.
똑같이 모든 요소를 옮기고 마지막으로 e를 입력하고 마무리짓게 된다. size는 5, capacity는 8인 상태로.
동적할당배열이 어떤식으로 움직이는지는 API들을 보면 쉽게 알 수 있다. 먼저 Get은 리스트에 존재하는 요소에 대한 index가 들어오면 그 순번에 맞는 원소를 반환한다.
Set은 해당 자리에 요청한 값을 입력해준다.
PushBack은 이전의 순서처럼 size가 capacity와 같다면 새로운 배열(크기가 2배인)을 할당하여 모두 복사한 뒤 해당 값을 입력하며 아직 size가 capacity보다 작다면 그냥 입력하는 수순에 size만 증가시키는 것을 알 수 있다.
Remove는 단순히 index만 맞게 요청이 된다면 그 뒤의 단의 요소들을 앞쪽으로 당겨 복사하는 수순을 통해 제거를 한다. size는 1 줄어든다.
Size는 배열의 원소갯수를 반환한다.
일반적인 동적할당배열 용법으로 볼 때 C++에서는 vector로 사용하며 Java에서는 ArrayList로 Python에서는 list로 사용하는데 Python에서는 정적배열이 없다.
퀴즈가 먼저 나오는데 n개의 요소에 대해 PushBack이 가장 많이 실행되는 상황에서 Order은 몇번 소요되는 지에 대한 질문인데 위에 나왔듯 resize가 될 때 O(n)시행되는 것을 보았다.
해당 API들에 대한 순차 횟수이다.
요약내용이며 동적할당배열은 크기재조정이 가능하다는 장점을 가지고 있으며 이 때 최대 걸리는 순차는 O(n)이다.
이번에는 Amortized cost에 대한 내용을 공부한다. 첫번째로 Aggregate Mothod에 대한 내용을 공부한다.
동적배열의 크기재조정이 빈번함에 따라 여러번의 O(1)작용이 O(n) 이후에 진행되는데 이 때 전체 비용은 어떻게 되는지 계산하는 것이 핵심이다.
Amortized cost의 정의 자체는 위의 수식과 같다. 일례로 차를 구매하는데 5년의 주기를 가진다고 한다. 이 때 두가지 방안이 있는데 1번째는 5년에 한번씩 차값을 치루는 것인데 $6000이라고 할 때 한번 지불 시 $6000을 한번에 지급하고 5년뒤 또다른 차를 $6000에 구매하는 방식이다. 2번째는 이를 매달 나눠 계산하는 것으로 5년은 60개월이기 때문에 매월마다 $100를 지불하는 방식이되겠다. 이 때 매달 나눠 내는 비용이 Amortized cost가 된다.
밑의 내용이 마무리되기 전 퀴즈가 나왔는데 해당 수식에 가장 상계에 가까운것을 찾는 것인데 기하급수에 의거하여 위와 같은 정리가 완성된다고 한다.
동적배열의 예를 들어 Amortized cost를 계산해보려한다. n번의 PushBack이 있을 때 Ci를 cost of i'th insertion으로 보고 Ci를 계산하면, 먼저 크기재조정이 필요없을 때에 Ci은 1일 것이다. 그리고 재조정이 필요한 경우 복사해서 붙여넣어야하는 순서가 필요하므로 i -1을 더하게 된다. 이 때 2의 n승으로 더해지게 되는데 이는 배열할당 시 2배씩 늘어나기 때문이다.
따라서 수식화 하면 위와 같이 정리가 되며 최소 Order는 O(1), 최대 Order는 O(n)이 된다.
다음은 Banker's Method를 사용하여 Amortized cost를 이해하는데 추상적 개념으로 보고 넘어가면 될 듯하다. 마치 은행에 대출을 하고 매달 갚는 방식과 비슷하다고 생각하면 된다고 한다.
데이터 삽입시 마다 1 token이 들며 이후에 재조정이 필요할 때 옮기면서 사용이 되는 형식이다.
위와 같이 비어있는 배열에 a를 입력하고 여기에 token을 지불(추후에 이동할 때 사용될 비용 포함)하게 된다. token은 실질적 존재가 아닌 개념적 존재라는 것에 유의하자.
이후에 PushBack을 통해 b를 추가할 때 새로운 배열을 할당하여 데이터를 옮기고 추가한다. 이 때 동일하게 b에 token을 부여하고 a도 추가해주는데 총 3개의 token이 사용되었다고 설명한다. 1개는 실질적으로 사용이 완료되었고 2개는 현재 보류하고 추후에 사용될 예정인 것들이다.
PushBack으로 c를 입력하면 또 다시 새로운 배열을 할당하고 옮기면서 token을 소멸시킨다.
이 후 c를 추가시키고 새롭게 token을 부여하며 a에도 token을 걸어둔다.
PushBack으로 d를 추가하면서 token을 걸고,
그 후 b에도 token을 부여한다.
PushBack으로 e를 추가하면서 token들을 소멸시키고 새롭게 추가된 e와 a에 token을 부여한 것을 볼 수 있다.
사실 정리하면서 다시 보아도 정확이 어떤 개념인지 이해가 되질 않는다. 더 찾아본 뒤 업데이트를 해야겠다.
다음은 Physicist's Method이다 여기서 위치에너지가 운동에너지로 전환되는 예를 들면서 설명한다. 위에서 ∅는 potential energy를 의미한다. h0는 초기 데이터구조의 상태를 말하고 ht는 시간이 지난 후의 데이터 구조이며 이 때의 potential energy는 음수가 되지 않는다.
또한 해당 방법에서의 amortized cost는 Ct + ∅(ht) - ∅(ht-1)으로 표기되며 Ct가 작으면 그만큼 potential은 증가하고 크다면 감소한다.
cost의 수식을 재구성하면 위와 같이 다시 표현이 가능하며 중간에 상쇄되는 요소들로 마지막 줄과 같이 정리된다.
예를 들게되어 위와 같은 수식으로 결정하면 initial potential은 2 * 0 - 0 = 0이며 이후 포텐셜은 동일한 수식을 갖는데 이 때 0보다 큰 이유는 size가 capacity/2보다 크기 때문이다.
따라서 resize하는 경우의 amortized cost는 위와 같이 정리가 될 수 있으며 Ci는 1인데 resize가 아닌 상황에서 O(1)이 1이기 때문이다. capacity는 불변이므로 상쇄가 되겠고 이전 size와 이후 size의 차이는 1개의 요소만 추가되었기 때문에 1이고 이들을 정리하여 계산하면 3이된다. 이는 Banker's Method에서 보았던 것처럼 token이 3개가 사용된 것과 일치하는데 우연이 아닌 것이다.
이번엔 resize의 경우를 살펴보면 size와 cap이 같은데 이는 resize하는 경우에는 둘이 같아야 하기 때문이다. 그렇다면 ∅(hi-1)과 ∅(hi)는 위와 같이 정리가 될 것이고 결국 3으로 동일하게 수렴한다는 것을 알 수 있다.
이 퀴즈를 처음 봤을 때에는 정확히 몰랐기에 틀렸지만 이제는 확실히 위와 같은 과정을 거쳤다는 것을 알 수 있기때문에 이해가 가능했다.
Amortized Analysis에 대한 Summary로 접어들어 정리를 한다. 동적배열로 돌아와서 2배씩 증가시킨데 반해 1.5 혹은 2.5 아니면 이외의 factor로 증가계수를 바꾼다면 이 때에도 constant amount를 사용할 수 있는지에 대핸 질문을 던지고,
그 예로 10배를 택했을 때 aggregate method로 증명하는 모습이다. 결론적으로는 불가능하다고 정리를 하며 이는 두배로 증가시킬 때 O(1)으로 cost가 적었던 것에 비해 열배로 바꾸니 O(n)으로 cost가 증가한 것을 확인할 수 있었다. 즉 constant factor를 사용하는 것이 중요하다고 정리한다.
3가지 Method를 통해 amortized cost를 계산하는 것에 대해 알아볼 수 있었고 주어진 수식을 통해 계산해보는 시간이었다. 잘 이해가 안되는 부분이 중간중간 있었기에 한번 더 개념을 찾아봐야 할 것 같다.
댓글
댓글 쓰기