[03-3] 배열을 알아보자(활용편)

여태까지 배열의 구조와 원리를 알아보았다.

 

역시 가장 중요한건, 그래서 코테에서 어떻게 쓰이는데?

결론부터 말하면, 배열은 반복문에서 많이 쓰인다.

 

list는 순서가 있기 때문에, 순차적으로 접근하는 반복문과 잘어울린다.

 

1. for 문

우리가 쉽게 생각하는 구조인 for문은 대표적 리스트 활용사례라고 봐도 무방하다.

예를 들어서

A = [5, 8, 3, 2, 11, 9, 4, 1, 13] 라는 리스트가 주어졌을 때,

"두개의 값 합했을 때 10이 나오면 True, 넘지 않으면 Fasle를 반환하시오"

라는 문제가 주어졌다면 A[i] + A[j]를 활용해야 겠다는 생각을 하게 된다.

 

자연스럽게 for문을 떠올리고, for문 안에 for 문인 이중for문을 구성하는데

우선은 이렇게 자연스럽게 for for를 써야겠다 라는 생각을 할 수 있는 사고력을 키우는데 집중하자

여기서 심화시킨다면 for문을 n번 하는구나, 그리고 그 안에서 for문을 n번 반복하니까 O(n²)이겠구나

라고 생각해보는 능력을 기르자.

 

정리하자면

1. for문을 돌리는 이유: list에서 값을 하나씩 테스트하려는 것

2. for문을 써야겠다!: list를 활용해야 하니까 O(n).. 이중이면 O(n²)이니까 n≤10⁴ 까지 가능하겠구나

 

2. 정렬

내림차순, 오름차순 정렬을 한다면 결국 리스트를 활용한다.

여기서 중요한건, 정렬에서 시간 복잡도는 O(nlogn)이다.

 

정렬이 왜 중요하냐면, 정렬은 낮은 시간 복잡도를 가지고 있지만, 파급력이 어마어마 하기 때문이다.

앞선 예시와 동일한 케이스를 가져와보자.

A = [5, 8, 3, 2, 11, 9, 4, 1, 13]   이 리스트에서 더해서 10이 나오면? 해서 for i, j 를 썼다.

하지만 오름차순 정렬을 해보자

A = [1, 2, 3, 4, 5, 8, 9, 11, 13] 로 정렬할 수 있고, 양 끝에 포인터를 두어서 1, 13을 찍어 더한다.

10이 넘네? 그러면 13을 왼쪽으로 옮겨서 1, 11로 한다. 어 넘네? 1, 9 성공!

만약에 10보다 작다면, 왼쪽 포인터를 오른쪽으로 옮기면 되겠지.

 

이처럼 정렬은 복잡한 가정을 줄여주기 때문에 굉장히 효율적이다. 낮은 시간복잡도를 가지고, 굉장히 파워풀하다.

 

항상 코드를 구현할 때는

1. 어떤 문제인가?

2. 어떻게 이 문제를 풀 수 있을까?

3. 코드를 그림으로 표현해보자(그려보자)

4. 그린 코드를 구현하자

 

4단계의 스텝으로 진행하면 좋다.

 

이 문제에 적용해보면

1. 더해서 10을 만들어야하는구나.. 정렬이 안되어 있네.. 리스트를 다 더하는건가? 조건을 보자. n≤10⁴이네

2. 리스트 원소를 하나씩 다 더해서 구할 수 있겠군! O(n²)이라서 너무 시간복잡도가 타이트하네..정렬을 해볼까? O(nlogn)이니까 할만할 것 같아. 정렬해서 끝을 하나씩 더해볼까? 오케이!

3. A.sort() ⇒ O(nlogn)이고, 왼쪽 포인트를 left, 오른쪽을 right 변수로 써봐야겠군. l=0, r=n-1 이군!

4. nums[l] + nums[r] == traget ⇒True 만약 타켓보다 작다면? l+1, 타켓보다 크다면? r-1. 언제까지? l<r되기 전까지!

 

자 생각해보면? 정렬은 O(nlogn), 해당 반복문은 결국 random access로 접근하니 O(1)이고.. 안에서 n번만큼 돌 수 있으니 O(n) 이구나. 그렇다면? O(nlogn)+O(n)이니까 O(nlogn)의 복잡도를 갖는구나!

 

정렬 한방에 모든게 수월해졌다!