알고리즘&자료구조 4편 - 재귀함수, 검색, 정렬(1)

김영현·2023년 5월 23일
0

알고리즘 & 자료구조

목록 보기
4/6

강의내용을 정리하던중 문득 이런생각이 들었다. 저작권은 문제가 없나...?
문제가 있었다. 강의 내용을 정리하는건 되지만 강의 내용 자체를 붙여넣는건 저작권 위반이다.(이전 게시글에 올라온 캡쳐본도 삭제예정)
오늘은 나만의 방식으로 축약해서 가겠다.

재귀함수

재귀:본디의 곳으로 다시 돌아오는것.

이보다 더 정확한 설명은 없겠군. 재귀는 말 그대로 한번 돌아서 다시 원래자리로 오는것이다.
재귀함수는 이와 비슷하다.
어떤 함수 내부에서 자기 자신을 호출한다면 재귀함수라 부를수 있다.

function foo(){
...
foo()
};

왜 사용하지?

재귀함수를 접했을땐 너무 어려웠다. 코드를 한번보고 재귀적으로 바로 이해할수 있다면 지능이 꽤 높은사람 아닐까? 지금도 어렵지만 이 어려운걸 왜쓰는지 싶었다.
그럼에도 사용하는 이유는 크게 두가지
1. 알고리즘이 재귀적으로 표현해야 자연스러운것이 있다.
2. 변수의 사용을 줄여준다.

하지만 장점이 있다면 단점도 있는법. 재귀함수를 공부할땐 js의 함수 호출 방식인 callstack을 차근차근 밟아가며 공부했다. 이 callstack이 쌓일수록 의문이 들었다.

※ callstack이란?

이런식으로 재귀함수를 작성하고, 중단점을 붙여서 호출해보면

아래와 같이 호출스택이 쌓인것을 볼 수 있다.

Stack형식의 구조로 만들어진 호출순서는 Stack의 선입후출 구조를따라간다. 맨 마지막에 호출된녀석이 제일 먼저나감.

이거 메모리에 적체되는거 아녀...?
맞았다. 실제로 대부분의 재귀함수 메모리를 많이차지하고 반복문보다 시간을 더 잡아먹는다. stack에 적체되는 양이 많을수록 느려지고, 자칫하면 stack이 감당할수 없는 데이터가 쌓여 stackoverflow를 발생시킨다.
이걸 해결하는 방법이 꼬리재귀라고 있긴한데, 아직은 잘 모르겠다. 알고리즘을 끝까지 훑고나서 공부해봐야겠다!

검색 알고리즘

아주 간단하면서도 살짝 베리에이션이 있는 녀석들이다. 제목 그대로 무언가를 찾는 알고리즘이다.
예를 들어보자. 여기 배열이 있다.
const 똘춘즈 = ["김똘춘", "박똘춘", "평똘춘", "김똘츈", "김춘똘"]
똘춘이 아닌 녀석도 있지만 넘어가고...아무튼 나는 이 중 정확히 "김춘똘" 이라는 사람을 찾고싶다. 이때 직관적인 방법이 떠오른다. 그게 바로

그냥 쭉 훑는것이다.
우리는 김똘춘, 박똘춘, 김똘츈 등 그 무엇도 아닌 "김춘똘"을 찾고싶다. 

for(let i = 0; i < 똘춘즈.length; i++){
	if(arr[i] === "김춘똘") return console.log("내가 김춘똘이오");
}
return console.log("김춘똘이는 이미 떠났소");

아주 심플하면서 직관적이다. 하지만 배열이 길어지면 문제다. 지금은 배열의 길이가 5이기때문에 시간이 그리 걸리진 않지만, 김춘똘이를 5천만 국민 내에서 선형 검색으로 찾으려하면 최악의경우엔 5000만번의 검색을 해야할것이다.
따라서 선형 검색의 시간복잡도는 O(n)
음...똘춘씨를 찾기엔 너무 오래걸리는 시간이다. 더 좋은방법이 없을까?

좋은 방법이 있긴 있었다. 하지만 이 방법을 사용하려면 데이터가 정렬되어 있어야한다. 하지만 똘춘이로 예를 들면 코드가 복잡해지니 간단하게 [1,2,3,4,5,6,7,8,9,10]이라는 배열안에서 6이라는 숫자를 찾는다고 정해본다.
단계는 이렇다.
1. 중앙을 콕 찝어 절반으로 나눈다. 짝수니까 내림해서 중앙을 4라고 칭해보자.
2. 4는 우리가 구하는 6이라는 숫자보다 작다. 그러면 중앙을 포함한 왼쪽은 무시한다.
3. [5,6,7,8,9,10]이 남는다. 다시 이중에서 중앙을 콕 찝는다. 내림해서 7.
4. 7은 우리가 구하는 6보다 크다. 그러면 7을 포함한 우측은 무시한다.
5. [5,6,7] 이 남는다. 중앙을 콕 찝는다. 6이네?

let left = 0;
let right = arr.length - 1;
//중요한점은 while문의 조건이다. 최악의 경우 마지막엔 양 끝에 있기때문에.
while(left <= right){
	const middle = Math.floor(right-left/2);
  if(arr[middle] === targetNumber) return console.log("당신이 원하는 숫자가 있소");
  if(arr[middle] < targetNumber) {
    left = middle + 1;
  } else {
    right = middle + 1;
  }
}
//while문에서 return을 못하면 false인것.
return console.log("그딴 숫자는 없는뎁쇼");

이진탐색의 시간복잡도는 O(log n). 참고로 상용로그가 아니라 log2 n인데 생략임!
뭐 이건 당연히 log n이다. 절반씩 나누니까!
근데 정렬되어 있는건 알겠는데, 어떻게 하는거지? 자바스크립트에선 sort()에 compareFunction으로 뚝딱이었는데...알고리즘은 그렇게 하진 않을테고.
흠.

정렬 알고리즘

짜잔~ 그런 나를 위한 정렬 알고리즘 등장!
정렬 알고리즘은 컴퓨터 과학분야에서 굉장히 중요시 되는 것중 하나다. 데이터가 주어지면 보통 개발자는 이를 정렬해서 사용하기때문에 아~주 자주쓰이는 알고리즘이다. 또한 아주아주 fast한 탐색알고리즘인 이진탐색을 사용하기위해 주로 정렬한다!

정렬 알고리즘은 크게 2가지로 나뉜다.
1. 시간복잡도가 O(n^2) 인것.
2. 시간복잡도가 O(n log n)인것.
나머지는 특수한 상황을 가정한것이기에 이렇게 나뉜다.

O(n^2) = 버블, 선택, 삽입.

1. 버블정렬

버블정렬은 쉽게말해 제일 큰 수를 맨 뒤로 보내는 정렬이다.
=> 맨 뒤는 정렬이 되어있다. 그렇다면 정렬이 될때마다 끝에서 한칸씩 땡겨주자.

//자리는 바꿔주는 함수. 구조분해할당으로 왼쪽과 오른쪽을 바꿔준다.
function swap(arr, left, right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
}

function bubble(arr) {
for(let i = arr.length; i > 0; i--;){
	for(let j = 0; j < i; j++){
    if(arr[j] > arr[j+1]) swap(arr,j,j+1);
    }
}
  return arr;
}

2. 선택정렬

선택정렬은 쉽게말해 제일 작은 수를 맨 앞으로 보내는 정렬이다. 언뜻보면 버블정렬과 비슷하지만 반대되는 개념이다.
똑같이 swap을 사용하니 swap 선언은 생략하겠음.

function selection(arr) {
  for(let i = 0; i<arr.length; i++){
    let minNumIndex = 0;
    //i는 이미 선택하니까 i+1부터 비교한다.
  	for(let j = i+1; j<arr.length; j++){
    //순회하면서 최솟값을 찾는다.
      if(arr[minNumIndex] > arr[j]) minNumIndex = j;
    }
    //중첩 순회가 끝에 도달했을때, i가 minNumIndex가 아닐때
    if(i !== minNumIndex) swap(arr, i, minNumIndex);
  }
  return arr;
}

3. 삽입정렬

삽입정렬은 쉽게말해 앞측은 정렬하면서 나아가는 형태다.
a. [5,4,3,1,2]라는 배열이 있다고 치자. 첫번째 값인 5와 두번째 값인 4을 비교한다. 4가 더 작으니 왼쪽에 감.
b. [4,5,3,1,2] 이렇게 [4,5]는 정렬되었다. 이제 정렬된 상태의 마지막값, 즉 두번째값인5와 세번째 값인3를 비교. 3이 더 작으니 왼쪽에 간다. 이제 3과 4를 비교. 역시나 3이 더 작으니 4의 왼쪽으로 간다.
c. [3,4,5,1,2] 왼편은 정렬되었다. 나머지 부분도 반복한다.
이걸 코드로 나타내보자.

function insertion(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentValue = arr[i];
    //j는 첫 인덱스까지 비교를 해야한다. 대신 arr[j]가 currentValue보다 작다면 굳이 비교할 필요는 없다.
    for (let j = i - 1; j >= 0 && arr[j] > currentValue; j--) {
        //아래 코드는 한칸씩 우측으로 요소들을 밀어버린다. currentValue는 이 때문에 저장한다.
      	//대신 중복되는 값이 생김. 그 자리를 for루프 탈출해서 currentvalue로 바꿔준다.
      arr[j + 1] = arr[j];
    }
    //arr[j] < currentValue. 즉 저장한 타겟값보다 더 작은값이 나왔으면 중첩for문을 나와서 '더 작은값'바로 우측(아마 중복된값)에 저장한 타겟값을 넣는다.
    arr[j + 1] = currentValue;
  }
  return arr;
}

헷갈리는 Point

  • i가 1부터 시작하는건, 그 전의값과비교해야하기 때문이다.
  • currentValue는 알고리즘이 삽입해야할 요소다.
  • 우측으로 이동한다는건, 중복된 값이 생긴다. 그 중복된 값 자리가 결국엔 currentValue가 들어간다.

recap

  • 재귀함수는 보기 편함 + 변수사용을 줄이려 사용한다. 어려울땐 callstack을 천천히 확인해보자(그래도 어려움)
  • 탐색 알고리즘은 이진탐색이 정렬되어있어야 한다는것
  • 버블 정렬은 큰 수를 뒤로 보내는 것
  • 선택 정렬은 작은 수를 앞으로 보내는 것
  • 삽입 정렬은 currentValue를 잡고, 그 값보다 작은값이 나올때까지 왼편의 값들을 우측으로 한칸씩 이동하는것.(앞측 정렬)

출처

  1. 재귀
    https://medium.com/sjk5766/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EB%A5%BC-%EC%93%B0%EB%8A%94-%EC%9D%B4%EC%9C%A0-ed7c37d01ee0
  2. 나머지는 udemy JavaScript 알고리즘 & 자료구조 마스터클래스의 내용을 적절히 구조분해할당해봄
profile
김영현
모르는 것을 모른다고 하기
이전 포스트

알고리즘&자료구조 3편 - 문제해결(2) 패턴

다음 포스트

알고리즘&자료구조 4 - 정렬(2)

0개의 댓글