2020년 8월 18일 TIL

paulkim·2020년 8월 18일
0

TIL

목록 보기
2/11

알고리즘 문제를 풀 때 가장 간단하게 해결 할 수 있는 case 부터 먼저 해결하는 것이다.

예를 들어, [1,2,3,4] 라는 원소를 갖고 있는 배열을 메소드 없이 반대로 표기해야 한다고 가정 해보자.

해당 배열의 길이 (array.length) 가 2보다 작다면 배열 그대로를 리턴하면 될 것이다. 그리고 이 것은 가장 기본적인 문제인, base case 에 대한 문제가 해소 된다. 그러면 나머지 [2,3,4] 에 대한 값은 어떻게 접근해야 할까?

우리는 재귀를 통해 이 문제에 대해서 접근할 것이다. 문제를 푸는 방법은 여러가지 이겠지만;

Array 나 리스트 문제를 해결 할 때는 head 와 tail 의 개념을 접목시키면 된다. arr.pop() 이란 메소드에 대해 한번 생각해보자. 해당 메소드를 이용하면 어레이의 마지막 원소를 지정해 제거시킬 수 있다. 만약 여러분들이 한번이라도 pop() 을 콘솔창에 찍어 본다면 pop 되는 원소를 보여주는 것을 알 수 있다. 이 것만으로 간단하게 문제 해결이 가능하다. 즉 앞서 말했던 것 처럼, 문제의 숫자를 줄여 나가면 되는 것이다. 각 재귀가 이루어 질 때, 마지막 자리에 위치 해있는 원소를 pop 하고 이 것을 원소의 첫번 째 항목에 이어 붙인다고 상상해보자.

const array = [1,2,3,4,5] 
console.log(array.pop()) // 5 
array.pop() // array = [1,2,3,4] 

그럼 만약 이렇게 pop 으로 빠진 값을 array 의 처음에 이어 붙인다면?

5 // [5,1,2,3,4]

4 // [4,1,2,3]

3 // [3,1,2]

2 // [2, 1]

1 // base case = 1

그리고 여기서 맨 아래의 경우부터 execution context 가 pop 하기 시작한다.

[1]

[2,1]

[3,2,1]

[4,3,2,1]

[5,4,3,2,1]

짜잔! 배열이 반대로 되었다!

0개의 댓글