heyday2024 님의 블로그
[알고리즘 특강] padStart, 시간 복잡도, 공간 복잡도 간단하게 정리! 본문
<이전 알고리즘 숙제 살펴보기>
padStart: 문자열이 특정 길이에 도달하도록, 문자열의 시작 부분에 주어진 문자열을 추가해주는 메서드. 이 메서드는 기존 문자열을 수정하지 않고, 패딩이 적용된 새로운 문자열을 반환함.
// str이 길이에 도달 할 때까지 문자로 채워나감
str.padStart(길이, 문자)
'1234'.padStart(8, '*') // '****1234'
'1234'.padStart(6, '*') // '**1234'
'1234'.padStart(4, '*') // '1234'
'1234'.padStart(3, '*') // '1234'
- for 문 사용할 때.... 배열의 요소를 모두 탐색하여 나누어 떨어지는지 확인한다 (= 완전탐색)
// 오름차순 정렬
arr.sort((a,b) => a - b)
// 내림차순 정렬
arr.sort((a,b) => b - a)
//항상 숙지하자
function solution(sizes) {
sizes.forEach(element => {
element.sort((a, b) => b - a);
});
const maxWidth = Math.max(...sizes.map((width) => width[0]));
const maxHeight = Math.max(...sizes.map((height) => height[1]));
return maxWidth * maxHeight
}
나는 두번째 문제에서 사용했던 sort와 강의에서 배운 스프레드 연산자( ...)와 map을 사용했다.
- 이 문제는 메소드를 많이 알아야 더 쉽게 푼다라는 느낌보다는 어떤 방식이 더 문제 해결에 효율적인가를 생각하게 만들어 더욱 흥미롭고 재밌는 알고리즘 문제였다.
사이즈
const width = size[0]
const height = size[1]
// 위 두 줄의 코드와 동일한 표현입니다.
const [width, height] = size // [3, 4]
너무 반가운 ㅋㅋㅋ 시간 복잡도와 공간 복잡도 ㅋㅋㅋㅋㅋ
알고리즘 효율성을 평가하기 위해 주로 쓰이는 두가지 지표임 --> 시간 복잡도, 공간 복잡도: 말그대로 코드 실행 시 걸리는 시간, 사용하는 공간의 효율성에 관한 것
- 자바스크립트는 좀 느린 (시간 효율성이 조금 떨어지는) 언어이긴함....
시간 복잡도 (time complexity)
📌 입력 값과 연산 수행 시간의 상관관계를 나타내는 척도 (= 코드의 시간적 효율성)
최악의 경우의 수를 나타내는 Big-O표기법.... 최악의 경우가 계산하기 편하면서도, 평균의 수행시간을 예측하기 쉬워서!!!
- O(1): 상수 시간 - 입력 크기에 관계없이 일정한 시간 (예: 배열의 첫 번째 요소 접근)
- O(n): 선형 시간 - 입력 크기 n에 비례하여 시간이 증가 (예: 배열의 모든 요소를 순회)
- O(n^2): 이차 시간 - 입력 크기 n에 대해 n^2에 비례 (예: 중첩 루프를 사용하는 경우)
- O(log n): 로그 시간 - 입력 크기가 증가할 때 시간이 느리게 증가 (예: 이진 탐색)
시간복잡도 개념의 시작
📌 코드의 효율성 측정을 위해 실제 실행 시간이 얼마나 걸릴지 표현해 보고 싶다!
- 하지만 실제의 실행 시간은 여러가지 요인에 의해 영향을 받습니다
- 컴퓨터의 처리 속도
- 사용된 언어
- 컴파일러의 속도
- 그래서 코드가 단순히 몇 초, 몇 분만에 실행됬다는 것을 기준으로 성능을 평가하기 여럽습니다
🤔 그러면 코드는 환경에 따라 실행 시간이 제각각인데 어떻게 하면 좋을까요?
function solution(n) {
let count = 0;
// 2n²
// 2번 반복
for (let i = 0; i < 2; i++) {
// n번 반복
for (let i = 0; i < n; i++) {
// n번 반복
for (let j = 0; j < n; j++) {
count++;
console.log('2n² 반복문', i, j, count);
}
}
}
// 8n
// 8번 반복
for (let i = 0; i < 8; i++) {
// n번 반복
for (let j = 0; j < n; j++) {
count++;
console.log('8n 반복문',i, j, count);
}
}
// 50
// 50번 반복
for (let i = 0; i < 50; i++) {
count++;
console.log('50번 반복문', i, count);
}
console.log('total count:', count);
}
solution(3)
solution(20)
solution(100)
// 상수, 낮은 차항, 계수는 무시합니다, 최고 차항만 따지면 됨..
2n² + 8n + 50 에서 가장 중요한 요소는 n²입니다
---> 시간 복잡도: O(n^2)
시간복잡도 문제의 예시
문제 ) 숫자 맞추기 게임 (up / down)
[문제 설명]
- 1 부터 10까지의 숫자가 있다
- A는 속으로 숫자를 생각하고, B는 A가 생각한 숫자를 맞추어야 한다
- B가 답을 말하면 A는 정답이 더 큰 수인지 작은 수인지 대답해 준다
- B가 최대한 효율적으로 숫자를 맞추려면 어떻게 해야할까?
[B가 취햇던 전략] 1. 가능한 숫자 중 중간에 있는 것를 말한다 2. UP/DOWN 정보를 통해 최대한 많은 수를 거른다 3. 위의 과정을 반복해서 정답을 찾는다
// [B의 전략을 코드로 바꾼다면]
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function binarySearch(num) {
debugger
// 0. 가장 작은수와 큰 수를 가르키는 변수를 만든다
let left = 0;
let right = arr.length - 1;
// 3. 위의 과정을 두 포인터가 만날 때까지 반복한다
while (left <= right) {
// 1. 가능한 숫자 중 가장 작은 수와 가장 큰 수를 가르키는 포인터를 통해 중간 숫자를 구한다
let mid = Math.floor((left + right) / 2);
// 2-1. 맞다면 숫자 찾기를 종료한다
if (arr[mid] === num) {
return `${num}은(는) 배열의 ${mid + 1}번째 위치에 있습니다.`;
// 2-2. UP이라면 작은 숫자를 거르기 위해 가장 작은 숫자를 업데이트한다
} else if (arr[mid] < num) {
left = mid + 1;
// 2-3. DOWN이라면 큰 숫자를 거르기 위해 가장 큰 숫자를 업데이트한다
} else {
right = mid - 1;
}
}
return `${num}은(는) 배열에 없습니다.`;
}
binarySearch(9)
- 이분 탐색: 배열이 정렬되어있다는 조건 하에 중간값을 계속 찾아내어 타깃을 찾아내는 방
공간 복잡도 (space complexity)
📌 프로그램의 실행에 얼마나 많은 공간(메모리)가 필요한지 나타내는 척도 (= 공간적 효율성)
function solution(n) {
return '수박'.repeat(5000).slice(0, n)
}
// 수박을 엄청 만들어놓고 잘라서 푸는 이 방식은 메모리를 너무 낭비하는 비효율적인 방식
- 가능하면 적은 메모리를 사용해서 문제를 풀이하도록 하는 것이 좋습니다
- 보통, 공간복잡도의 경우 제한량이 넉넉하게 주어지므로 크게 걱정하실 필요는 없습니다.
https://ko.javascript.info/debugging-chrome
Chrome으로 디버깅하기
ko.javascript.info
시간 복잡도, 공간복잡도를 생각하면서 더욱 효율적인 알고리즘을 짜는 것은 많은 데이터를 처리하는데 더욱 중요해질 것이다. 프론트엔드 개발자로서 성장하면서도 기본이 되는 알고리즘 공부를 항상 틈틈히 잊지 않게 공부를 해야겠다!

'프론트엔드 부트캠프' 카테고리의 다른 글
[3주차 JS 기초 문법] 데이터 타입, 메모리, 변수 선언과 데이터 할당, 얕은 복사와 깊은 복사, null/ undefined (1) | 2024.10.15 |
---|---|
[JS 1강] <var, let, const 의 차이> <&&, || 연산자> <if, else 와 switch 문으로 조건문> <for문으로 반복문> (0) | 2024.10.14 |
[알고리즘 특강2] 내가 작성한 코드와 비교해보자. (1) | 2024.10.11 |
[알고리즘 특강 1] (1) | 2024.10.10 |
[2주차 JS 문법] ES6 문법, 일급 객체, Map, Set (0) | 2024.10.10 |