자료구조와 알고리즘이 중요한 까닭

누구나 자료구조와 알고리즘

제 1장 자료구조가 중요한 까닭

let number = 2;
while(number<=100){
	if(number % 2 === 0) return number
	number+=1
}

let number = 2;
while(number<=100){
	return number
	number+=2
}

다음 코드는 2부터 100 사이에서 짝수를 하나 찾아내는 단순한 반복문이다.

• 첫 번째 while문은 최대 100번 반복
• 두 번째 while문은 단 1번에 종료

같은 기능이여도 효율적인 코드 작성이 중요한 이유다.

✅ 배열 vs 집합

배열 (array/list)	집합 (Set)
중복 허용	중복 X
순서 있는 리스트	순서 없음
맨 뒤 삽입(push) 1단계(이동이 필요없음)	맨 뒤 삽입 100개면 (갯수만큼) 101단계
순차처리가 필요할 때 사용	고유 ID같은 요소 저장시 사용
순차적으로 검색해서 느림	빠르게 검색함

• 배열은 indexOf, find 등으로 첫 번째 일치값은 쉽게 찾지만, 모든 일치값을 찾으려면 전체 순회해야 함.
• 집합은 중복을 자동으로 제거하고, 값의 존재 유무를 빠르게 확인할 수 있어 탐색이 효율적임.

---

제 2장 알고리즘이 중요한 까닭

자료를 어떻게 담을지만큼, 어떻게 다룰지도 중요하다.

🔍  전형적인 배열 vs 정렬된 배열

전형적인 배열	정렬된 배열
순서는 있으나 정렬되지않음	오름차순또는 내림차순 정렬(sort)
순차검색- 속도느림(최대 n단계)	이진탐색 - 속도 빠름 (최대 log₂n단계)

이진검색 동작 방식

1. 배열의 중앙값을 찾음.
2. 중앙값이 목표 값과 일치하면 검색이 종료됨.
3. 중앙값이 목표 값보다 크면 배열의 왼쪽 절반에서 검색을 이어가고,
4. 중앙값이 목표 값보다 작으면 배열의 오른쪽 절반에서 검색을 이어감.

이진검색 예시

const a = [1,2,3,4,5,6,7,8,9,10]

function handleA(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid; // 찾은 경우 인덱스 반환
        } else if (arr[mid] < target) {
            left = mid + 1; // 오른쪽 절반 탐색
        } else {
            right = mid - 1; // 왼쪽 절반 탐색
        }
    }

    return -1; // 못 찾은 경우
}

예시로 어릴때하던 숫자 맞추기 게임과 같다.

전형적인 배열은 섞여있기 때문에 오름차순 또는 내림차순으로 정렬된 배열에서만 이진검색을 수행할 수 있다.

100개의 값을 가진 배열에서 찾는다고 하면,

• 순차 검색은 최대 100번
• 이진 검색은 7번이면 끝

배열이 두 배로 늘어나도, 이진검색은 한 단계만 늘어난다.

데이터가 많아질수록 차이가 훨씬 커지는걸 알 수 있다.

단, 정렬된 배열이 삽입은 느리다.
어디에 넣을지 찾고, 그 위치값으로 가게끔 기존값들을 뒤로 이동시키는 작업이 있기 때문이다.

[1, 3, 5, 7, 9]에 4를 넣는다고 하면:

• 먼저 3과 5 사이 위치를 찾고,
• 5, 7, 9를 모두 뒤로 한 칸씩 밀어야 함

---

✏️  요약

• 자료구조는 데이터를 어떻게 담을지, 알고리즘은 그 데이터를 어떻게 처리할지에 대한 방법이다.
• 이진 검색처럼 빠른 알고리즘이 있어도, 그걸 가능하게 하는 정렬과 정렬에 따른 비용도 함께 생각해야 한다.
• 소프트웨어에서 삽입이 자주일어나나? 검색을 많이 필요로 하나? 삽입 이후에 한꺼번에 정렬처리 하는 방식으로 처리하는게 좋나?
  사용하는 소프트웨어 종류나 목적에따라 분석이 필요하다.