2024 동계 모각코 3회차

2025/01/20

3회차 목표

1) Udemy 강의:
- 섹션 10: 검색 알고리즘
2) 실습:
- 강의의 문제 구현
- 프로그래머스 문제

---

TIL

검색 알고리즘(Search Algorithm): 주어진 데이터 집합에서 특정한 값이나 조건을 만족하는 데이터를 찾기 위한 절차 또는 방법

 

 

검색 알고리즘의 분류

 

1. 선형 검색(Linear Search)

• 배열 또는 리스트의 첫 번째 요소부터 마지막 요소까지 순차적으로 탐색하며 원하는 값을 찾는 방법
• 시간 복잡도: O(n) (n은 데이터의 크기)
• 특징: 정렬되지 않은 데이터에도 사용할 수 있지만, 데이터 크기가 커질수록 비효율적.선형 검색(Linear Search)
• 예시 코드:

1.  

function linearSearch(arr, target) { 
	for (let i = 0; i < arr.length; i++) { 
    	if (arr[i] === target) { 
        	return i; // 인덱스 반환 
         } 
     } return -1; // 찾지 못하면 -1 반환 
}

console.log(linearSearch([1, 2, 3, 4, 5], 3)); // 2

 

 

2. 이진 검색(Binary Search)

• 데이터가 정렬되어 있는 경우, 가운데 값을 기준으로 원하는 값이 있는지 확인하며 검색 범위를 절반으로 줄여나가는 방식.
• 시간 복잡도: O(log n) (n은 데이터의 크기)
• 특징: 정렬된 데이터에만 사용할 수 있으며, 매우 빠르고 효율적.이진 검색(Binary Search)
• 예시 코드:

1.  

function binarySearch(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; 
 } 
 
 console.log(binarySearch([1, 2, 3, 4, 5], 3)); // 2

 

---

 

1. Array.prototype.indexOf()

• 배열에서 특정 값을 찾아 인덱스를 반환. 값이 없으면 1을 반환
• 선형 검색(Linear Search)에 해당.

예제:

const arr = [10, 20, 30, 40, 50];
console.log(arr.indexOf(30)); // 결과: 2
console.log(arr.indexOf(60)); // 결과: -1

 

 

 

2. Array.prototype.includes()

• 배열이 특정 값을 포함하고 있는지 여부를 반. (불리언 값)

예제:

const arr = [10, 20, 30, 40, 50];
console.log(arr.includes(30)); // 결과: true
console.log(arr.includes(60)); // 결과: false

 

 

 

3. Array.prototype.find()

• 배열에서 조건을 만족하는 첫 번째 요소를 반환. 조건에 맞는 요소가 없으면 undefined를 반환.

예제:

const users = [
    { id: 1, name: 'Alice' },
    { id: 2, name: 'Bob' },
    { id: 3, name: 'Charlie' }
];
console.log(users.find(user => user.name === 'Bob'));
// 결과: { id: 2, name: 'Bob' }

 

 

4. Array.prototype.findIndex()

• 배열에서 조건을 만족하는 첫 번째 요소의 인덱스를 반환. 조건에 맞는 요소가 없으면 1을 반환.

예제:

const nums = [5, 10, 15, 20];
console.log(nums.findIndex(num => num > 10)); // 결과: 2
console.log(nums.findIndex(num => num > 50)); // 결과: -1

 

 

 

5. Array.prototype.filter()

• 조건을 만족하는 모든 요소를 새로운 배열로 반환. 조건에 맞는 요소가 없으면 빈 배열을 반환.

예제:

const nums = [5, 10, 15, 20, 25];
console.log(nums.filter(num => num > 10)); // 결과: [15, 20, 25]
console.log(nums.filter(num => num > 50)); // 결과: []

 

 

 

6. Array.prototype.some()

• 배열의 요소 중 하나라도 조건을 만족하면 true를 반환. 모든 요소가 조건에 맞지 않으면 false를 반환.

예제:

const nums = [5, 10, 15];
console.log(nums.some(num => num > 10)); // 결과: true
console.log(nums.some(num => num > 20)); // 결과: false

 

 

 

7. Array.prototype.every()

• 배열의 모든 요소가 조건을 만족하면 true를 반환. 하나라도 조건을 만족하지 않으면 false를 반환.

예제:

const nums = [5, 10, 15];
console.log(nums.every(num => num > 0)); // 결과: true
console.log(nums.every(num => num > 10)); // 결과: false

 

 

 

8. String.prototype.includes()

• 문자열에서 특정 서브 문자열을 포함하고 있는지 여부를 확인.

예제:

const str = "Hello, world!";
console.log(str.includes("world")); // 결과: true
console.log(str.includes("JavaScript")); // 결과: false

 

 

 

9. String.prototype.indexOf()

• 문자열에서 특정 서브 문자열의 첫 번째 위치를 반환. 찾지 못하면 1을 반환.

예제:

const str = "Hello, world!";
console.log(str.indexOf("world")); // 결과: 7
console.log(str.indexOf("JavaScript")); // 결과: -1

 

 

 

10. Set.prototype.has()

• Set 객체에서 특정 값을 포함하고 있는지 확인.

예제:

const set = new Set([1, 2, 3, 4, 5]);
console.log(set.has(3)); // 결과: true
console.log(set.has(6)); // 결과: false

 

 

 

11. Map.prototype.has()

• Map 객체에서 특정 키가 존재하는지 확인.

예제:

const map = new Map([
    ['key1', 'value1'],
    ['key2', 'value2']
]);
console.log(map.has('key1')); // 결과: true
console.log(map.has('key3')); // 결과: false

 

 

 

12. Object.keys() / Object.values() / Object.entries()

• 객체의 키, 값, 또는 키-값 쌍을 배열로 반환하여 검색.

예제:

const obj = { a: 1, b: 2, c: 3 };
console.log(Object.keys(obj)); // 결과: ['a', 'b', 'c']
console.log(Object.values(obj)); // 결과: [1, 2, 3]
console.log(Object.entries(obj)); // 결과: [['a', 1], ['b', 2], ['c', 3]]

 

 

 

---

느낀 점

알고리즘 재수강 해야지..