Test of Week 2
강의 내용을 바탕으로 4문제를 풀게 되었다.
Test에 대한 정보는 위와 같았으며 바로 문제로 넘어가보겠다.
1번 문제는 동적배열에서 PopBack이라는 새로운 API를 생성했다고 했을 때 기능은 마지막 요소를 제거하는 것이며 PushBack과 달리 재할당을 하지않으며 만약 빈 배열에서 호출 시 에러를 반환하는 역할을 수행한다고 한다.
이때 24번의 PushBack과 24번의 PopBack이 진행될 때 Capacity의 최대/최소값을 구하는 문제이다.
2번 문제는 마찬가지로 PopBack에 대해 설명하며 대신 size <= capacity/2의 조건을 만족하면 동적할당이 진행되는 기능이 추가되었다. 이때 복사하여 옮기는 과정에서 Order가 n의 2승을 만족하는 조건을 찾는 것이다.
3번 문제는 좀더 복잡한 PopBack API에 대한 내용이 나오며 size <= capacity/4의 조건을 만족하면 동적할당이 일어난다. 이 때 빈 동적배열에서 n번의 PushBack과 PopBack 동작을 진행할 때 amortized cost가 O(1)에 해당하는 potential function을 찾아야 한다.
4번 문제에서는 PopMany를 정의하는데 i개만큼 PopBack을 진행하는 역할이다. 빈 스택에서 시작하여 어떤 동작이든 수행할 때 amortized cost에 대한 설명으로 옳은 것을 고르면 된다.
통과 시 위와 같이 통과가 되었다고 뜨며 1번문제부터 리뷰해보겠다.
어렵지 않게 풀 수 있었는데 다만 처음에 size를 구하는 줄 착각하고 max를 24로 선택했었는데 capacity를 구하는 것으로 다시 확인하고 max는 32 으로 수정하고 min 1로 그대로 선택하였다.
2번부터 약간 골머리를 썩혔는데 모든 케이스에 일반화를 해서 증명할 필요는 없어서 n=2, 3, 4의 대략적인 케이스들만 비교하여 풀었다. 설명이 더 잘 나와 있으니 패스.
3번의 경우 보기 3은 숱한 예제를 통해 확인하여서 아닌 것을 알았고 보기 2번 또한 ∅(h0)가 0이 아니므로 부합하지 않아 제외. 그럼 1 or 4인데 max함수를 통해 비교하는 조건이니 솔직히 인자에 0이 들어간 것이 더 맞을 확률이 있다고 생각했으나... 오산.
마지막 문제는 많이 고민하여 풀었지만 처음 시도에서 보기 1번을 놓쳤다. 보기 2와 3은 거의 같은 의미이니 패스하고 보기 1번만 보자면 Push 동작은 1번을 push에 1번은 potential을 증가시키는데 사용되어 amortized cost가 2이고 Pop과 PopMany를 함께 보자면 i번을 pop에 -i번을 potential에 사용되므로 결국 amortized cost는 0로 수렴한다. 따라서 O(1)에 해당하는 케이스이다.
강의 내용을 바탕으로 4문제를 풀게 되었다.
Test에 대한 정보는 위와 같았으며 바로 문제로 넘어가보겠다.
1번 문제는 동적배열에서 PopBack이라는 새로운 API를 생성했다고 했을 때 기능은 마지막 요소를 제거하는 것이며 PushBack과 달리 재할당을 하지않으며 만약 빈 배열에서 호출 시 에러를 반환하는 역할을 수행한다고 한다.
이때 24번의 PushBack과 24번의 PopBack이 진행될 때 Capacity의 최대/최소값을 구하는 문제이다.
2번 문제는 마찬가지로 PopBack에 대해 설명하며 대신 size <= capacity/2의 조건을 만족하면 동적할당이 진행되는 기능이 추가되었다. 이때 복사하여 옮기는 과정에서 Order가 n의 2승을 만족하는 조건을 찾는 것이다.
3번 문제는 좀더 복잡한 PopBack API에 대한 내용이 나오며 size <= capacity/4의 조건을 만족하면 동적할당이 일어난다. 이 때 빈 동적배열에서 n번의 PushBack과 PopBack 동작을 진행할 때 amortized cost가 O(1)에 해당하는 potential function을 찾아야 한다.
4번 문제에서는 PopMany를 정의하는데 i개만큼 PopBack을 진행하는 역할이다. 빈 스택에서 시작하여 어떤 동작이든 수행할 때 amortized cost에 대한 설명으로 옳은 것을 고르면 된다.
통과 시 위와 같이 통과가 되었다고 뜨며 1번문제부터 리뷰해보겠다.
어렵지 않게 풀 수 있었는데 다만 처음에 size를 구하는 줄 착각하고 max를 24로 선택했었는데 capacity를 구하는 것으로 다시 확인하고 max는 32 으로 수정하고 min 1로 그대로 선택하였다.
2번부터 약간 골머리를 썩혔는데 모든 케이스에 일반화를 해서 증명할 필요는 없어서 n=2, 3, 4의 대략적인 케이스들만 비교하여 풀었다. 설명이 더 잘 나와 있으니 패스.
3번의 경우 보기 3은 숱한 예제를 통해 확인하여서 아닌 것을 알았고 보기 2번 또한 ∅(h0)가 0이 아니므로 부합하지 않아 제외. 그럼 1 or 4인데 max함수를 통해 비교하는 조건이니 솔직히 인자에 0이 들어간 것이 더 맞을 확률이 있다고 생각했으나... 오산.
마지막 문제는 많이 고민하여 풀었지만 처음 시도에서 보기 1번을 놓쳤다. 보기 2와 3은 거의 같은 의미이니 패스하고 보기 1번만 보자면 Push 동작은 1번을 push에 1번은 potential을 증가시키는데 사용되어 amortized cost가 2이고 Pop과 PopMany를 함께 보자면 i번을 pop에 -i번을 potential에 사용되므로 결국 amortized cost는 0로 수렴한다. 따라서 O(1)에 해당하는 케이스이다.
댓글
댓글 쓰기