스터디 1일차

1강 <인터뷰 배열 기초>

sorting의 종류 - heap sort, quick sort, merse sort

 

stable한 알고리즘은 merge sort이 있고, unstable한 알고리즘은 quick sort, heap sort가 있다. (퀵힙은 불안정)

ABC 로 테이블이 있을 때, 정렬한 후에도 ABC 이 순서로 유지된다면 stable 알고리즘이다. (잘못 이해했음. 아래에 부가 설명 참고!)

 

search는 배열을 전부 다 돌아야 하기 때문에 O(n) 정도로 걸린다

binary search -> O(logn)

2차원 다차원 array..

 

 

먼저 정렬 알고리즘이란

컴퓨터 과학과 수학에서 정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. (출처: 위키피디아)

안정 정렬(Stable Sort)

중복된 키를 순서대로 정렬하는 정렬 알고리즘을 뜻한다.

예를 들어, 다음과 같은 list가 있다고 하자.

list=[1, 7, 3, 5, 4, 7, 9]

이 리스트에서 7이 두번 나온다. 구분을 위해 ()를 이용해 앞은 (1), 뒤는 (2)를 표시하면

list=[1, 7(1), 3, 5, 4, 7(2), 9] 와 같다.

 

이때 이 리스트를 정렬했을 때
(1) list=[1, 3, 4, 5, 7(1), 7(2), 9]
(2) list=[1, 3, 4, 5, 7(2), 7(1), 9]

(1)처럼 나오면 안정(Stable) 정렬, (2)처럼 나오면 불안정(Unstable) 정렬이라고 한다.

 

즉, 정렬을 했을 때 중복된 값들의 순서가 변하지 않으면 안정(Stable) 정렬, 변하면 불안정(Unstable) 정렬인 것이다.

 

<대표적인 알고리즘들>

Stable Sorting 알고리즘은 다음과 같다:

• Insertion Sort (삽입정렬)
• Merge Sort
• Bubble Sort (버블정렬)
• Counting Sort

Unstable Soring 알고리즘:

• Selection sort
• Heap Sort
• Shell Sort
• Quick Sort

 

 

 

 

---

2강 <코딩테스트, 기초, 퀵 정렬>

Quick sort 에는 pivot, partitioning 개념이 있다.

 

9 5 2 3 7 8 4 라는 배열에 대해서 살펴보자.

임의로 5를 pivot 으로 잡아본다.

 

 

pivot 을 정해주고 나머지 element들을 파티셔닝 해주는 것

그 다음 단계는 남은 element들에 대해서 pivot을 정해주고 partioning 반복..

swap을 통해서 Quick sort를 진행해야 한다.

 

 

 

 

[ 9 5 2 3 7 8 4 ]   

▲ 5를 임의로 피벗으로 선정... 5와 맨 끝 4 교체

[ 9 4 2 3 7 8 5 ]   

▲ 5를 기준으로 양 끝 인덱스 비교.. 9의 인덱스는 그대로 있고 오른쪽 인덱스는 (<- 방향) 움직이며 비교..

▲ 3은 5보다 작으므로 3과 9를 교체

[ 3 4 2 9 7 8 5 ]   

▲ 양끝 인덱스 비교하면서 움직이다보면 서로의 인덱스가 역전됨

▲ 9와 5를 교체

[ 3 4 2 5 7 8 9 ] 

▲그 다음 피벗 5를 기준으로 양 옆 2개의 파티션 내부에서 각각을 파티셔닝 해준다 (swap 진행시키기)

[ 2 3 4 5 7 8 9 ]

 

 

 

 

피벗을 정하는 방법은 여러가지가 있다.

1) 임의의 피벗을 정한 후, 마지막 숫자와 교환

2) 마지막 숫자를 피벗으로 선정 (오히려 더 느린 sorting)

3) 피벗 숫자를 잡은 뒤 양쪽에서 인덱스를 잡는 것이 아니라 한쪽에서 인덱스를 잡음

 

 

 

time complexity 와 space complexity ... 

 

 

 

Quick sort 가 가장 빠르게 끝낼 수 있는 방법은 피벗을 가운데 값으로 선정할 때이다.

-> O(nlogn) 으로 best case가 된다.

반대로 worst case는 피벗을 최대값으로 선정할 때 발생되며, time complexity는 O(n^2) 가 걸린다.

 

 

※ 일반적으로 피벗을 맨 끝의 숫자로 정하기보다는 랜덤의 위치의 숫자로 정하거나 가운데 값을 가지는 숫자를 피벗으로 정하게 되는데, 그 이유는 정렬된 배열일 경우가 있기 때문이다.

 

 

Quick sort 의 단점은 ustable sort 였다. 다시 한번 각인하자! stable sort는 merge sort 이다.

 

 

 

partition 이라는 함수는 정렬을 시켜주는 함수이다. 오른쪽에 있는 선생님이 필기하신 그림과 같이 보면,

첫번째 quickSort 함수는 left(4) 와 pivot-1(2) 를 퀵정렬을 하는 것이고,

두번째 quickSort 함수는 pivot+1(9) 와 right(6) 을 퀵정렬 하는 것이다.

 

 

 

 

 

 

---

3강 <코딩테스트, 기초, 배열 인터뷰 Binary Search>

일반적인 배열 Search는 time complexity가 O(n) 이 된다.

그러나, Binary Search를 사용하게 되면 time complexity가 O(logn) 이 된다.

 

 

 

이것도 left index와 right index가 사용된다. left index와 right index의 중간 지점과 검색하려는 숫자를 비교해 나가며, 탐색 범위를 좁혀 나가는 것이 특징이다. 

pivot = (L + R) / 2

 

 

만약 1 3 5 6 7 15 20 이라는 배열이 있을 때, 16이라는 숫자를 Search 하려고 한다.

(0번 인덱스 + 6번 인덱스) / 2 = 3번 인덱스(피벗)

 

3번 인덱스인 6이 pivot이 되면서 16과 6을 비교했을 때, 16이 더 크다 -> Left index는 7로 옮겨간다.

....과정을 반복해서

Left index와 right index 가 역전되면 return -1 (실패라는 뜻)을 해준다.

 

 

 

 

 

 

맨 첫줄 코드부터 설명하면, left index = 0 &  right index = nums.length로 지정해준다.

left index가 right index보다 항상 왼쪽에 있을 때에 이 반복문은 실행된다.

피벗을 구해주고

1) 만약 이 피벗이 목표 숫자와 같다면 피벗 리턴 -> 반복문 빠져나오기

2) 피벗 < 목표 숫자라면, left index는 피벗의 오른쪽으로 이동

3) 피벗 > 목표 숫자라면, right index는 피벗의 왼쪽으로 이동

-> 이 과정을 반복하여 언젠가 left index와 right index가 교차된다면 while 조건문에 위배되므로 실행이 종료된다. (찾고자 하는 숫자를 못찾은 Case 가 된다)  

 

 

 

 

 

 

 

---

4강 <코딩테스트, 초급, Movezeros>

[ 0 5 0 7 6 3 ] 이라는 배열이 있을 때, 0을 맨 뒤로 옮기면서 5 7 6 3 은 순서가 바뀌지 않는게 포인트이다.

-> [ 5 7 6 3 0 0 ]

 

 

몇가지 방법을 생각해 볼 수 있다.

1) 직관적으로 0을 찾아서 뒤로 보내기, 그리고 뒤에 있는 숫자를 한 칸씩 앞으로 이동

2) 0을 버블정렬을 이용해서 뒤로 한칸씩 점진적으로 보내기 = O(n * 0의 개수)

 

 

 

여기서 0이 아닌 숫자를 찾아서 왼쪽으로 보내는 방법을 생각해보자! (Zeromoves)

 

[ 0 5 0 7 6 3 ]

항상 0을 가리켜야 하는 파란색 화살표와 0 아닌 숫자를 가리켜야 하는 주황색 화살표로 생각(0번 인덱스부터 둘다 시작)

주황색 인덱스는 오른쪽 이동하여 5를 가르키게 되고 이때 파란색 인덱스와 swap이 발생한다.

그리고 파란색 인덱스는 오른쪽 한 칸 이동

(그 다음은 과정이 앞과 같다)

주황색 인덱스가 움직이고 7까지 한칸씩 이동 -> swap 발생 ......

 

 

 

wIdx는 파란색 인덱스, idx는 주황색 인덱스로 가정.

if 문에서 주황색 인덱스가 0 아닌 숫자를 가리킬 때, 파란색 인덱스와 swap 함수를 통해 교환한 다음 파란색 인덱스를 오른쪽으로 한 칸 이동해준다.

 

 

 

 

 

근데 여기서 두 인덱스 모두 0이 아닌 숫자를 가리킬 때 어떻게 될지 생각해보자.

 

 

 

그럴 땐 이렇게 코드를 작성해주면 된다. 주황색 인덱스와 파란색 인덱스가 copy의 개념으로 되며,

 

두 인덱스를 동시에 같이 한 칸씩 이동해주면 된다.

그 다음 뒤에 모두 0으로 복사한다.

 

 

 

문풀

(Inplace 알고리즘이란 추가적인 메모리 공간을 많이 필요로 하지 않는 혹은 전혀 필요하지 않는 알고리즘을 의미한다. 통상적으로, 공간은 O(logn)이고 O(n)이 될 때도 있다.

즉, n 길이의 리스트가 있고, 이 리스트를 정렬할 때 추가적으로 메모리 공간을 할당하지 않아도 정렬이 이뤄진다면 in-place 알고리즘이라고 불릴 수 있는 것이다.

 

In-place하지 않은 알고리즘은 n 길이의 리스트를 정렬할 때, n 만큼의 메모리보다 더 많은 메모리 공간을 할당한다. 즉, 이런 알고리즘들은 space complexity가 높다.)

 

---

5강 <코딩테스트, 초급, find pivot index>

[ 1 8 2 9 2 3 6 ] 이라는 배열이 있을 때, 9를 피벗으로 하고 피벗 기준 왼쪽 숫자의 합과 오른쪽 숫자의 합을 비교했을때 이 둘이 같으면 9가 피벗이 된다는 개념이다. 3번 인덱스를 리턴해주는 것이 정답이 된다.

[ 2 5 7 ] 일 경우, 피벗을 못 찾으므로 -1 을 리턴해주면 된다(실패)

 

이때 피벗을 앞에서부터 하나씩 잡게 되면 O(n) * n 가 된다. (n번 반복하게 되니까) - 좋지 않은 방법

 

 

( solution )

전체 sum을 구하면 O(n) 발생

1을 피벗으로 할때, 왼쪽은 0  &  오른쪽은 합 - 1 을 해준다.   ( O(1) 발생 )

8을 피벗으로 할때, 왼쪽은 0 + 1  &  오른쪽은 합 - 1 - 8 을 해준다.   ( O(1) 발생 )

....   O(1) * n 발생 

 

따라서 O(n) + O(n) => O(n) 이 된다.

 

 

 

 

accumulation 함수를 통해서 sum을 구해준다.

leftsum = 0 , rightSum = sum 으로 한다.

인덱스를 한 칸씩 이동하는 for문에서 rightSum에서는 num을 빼주고 이때 leftsum == rightsum 이면 인덱스를 리턴해준다. 인덱스가 한 칸 업데이트 되면 leftSum 에는 leftSum + 과거피벗넘버...

맨 마지막 pastPivotNum = num 을 써줌으로써, update 가 된다.

 

 

 

 

 

+ )

minimum size subarray sum

배열에서 합이 7인 최소 길이의 배열 찾기

이번 강의 문제를 Sliding 으로 하면 O(n)으로 해결이 가능하다. (직접 해보기 추천)