Find Peak Element
주어진 배열에서 Peak를 찾아라. peak란 배열의 요소 중에서 양 옆의 값보다 큰 요소의 인덱스를 뜻한다. [1, 2, 3, 5, 4] -> Peak : 5 [1, 3, 2, 4, 5, 7, 6] -> Peak : 7 가장 쉬운 방법으로는 배열을 순회 하면서 양 옆의 값보다 큰 요소를 찾는 방법이 있겠다. (O(n)) 그러나 가장 효율적인 방법은 O(logN)의 방법. 즉 Binary Search를 이용하는 것이다. 즉 나열된 값들의 중간 값(Pivot)을 찾고 그 다음 값이 Pivot 값보다 크면 오른쪽, 작으면 왼쪽으로 인덱스를 옮기는 방식으로 탐색을 진행 한다. #include int findPeakElement(int* nums, int numSize) { int left = 0; int ri..
2021. 10. 25.
Find Pivot Index
주어진 배열에서 Pivot Index를 찾아라. Pivot이란 배열 상에 있는 값들 중, 임의의 인덱스를 중심으로 왼쪽과 오른쪽의 합이 같은 지점의 인덱스이다. 예 : [ 1, 8 , 2, 9, 2, 3, 6 ] --> Pivot : 9 개념 배열을 순회하는 인덱스를 중심으로 좌, 우의 값들의 합을 계산한다. ( LeftSum, RightSum ) LeftSum과 RightSum이 동일하면 해당 인덱스가 Pivot 이다. (종료) LeftSum과 RightSum 이 다르면 순회를 계속 진행하되 이전 인덱스의 값을 저장한다. (PastPivotNum) #include int accumulation(int* nums, int numSize) { int resultSum = 0; for (int i = 0; ..
2021. 10. 19.
Move Zeros
주어진 배열에서 숫자 0은 모두 오른쪽 끝으로 옮겨라. 0이 아닌 숫자들의 순서는 바뀌면 안된다. [ 0, 5, 2, 1] -> [ 5, 2, 1, 0] [ 5, 7, 0 , 9, 13, 0, 45] -> [5, 7, 9, 13, 45, 0, 0] 0을 찾아서 오른쪽 끝으로 보내기? 첫번째 예에서 0을 1의 오른쪽으로 보낼때 다른 숫자들도 하나씩 왼쪽으로 밀어야 한다. 0을 찾을때 마다 오른쪽의 있는 숫자와 버블 스왑 반복 반대로 쉽게 생각해보면 0이 아닌 숫자를 만나면 왼쪽으로 보내면 되겠다! 구현 예 #include void moveZeros(int* nums, int numsSize) { int wIndex = 0; for (int index = 0; index < numsSize; index++)..
2021. 10. 18.