Notice
Recent Posts
Recent Comments
Link
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
Archives
Today
Total
관리 메뉴

heyday2024 님의 블로그

[알고리즘 특강] padStart, 시간 복잡도, 공간 복잡도 간단하게 정리! 본문

프론트엔드 부트캠프

[알고리즘 특강] padStart, 시간 복잡도, 공간 복잡도 간단하게 정리!

heyday2024 2024. 10. 14. 20:33

<이전 알고리즘 숙제 살펴보기>

 

****을 나는 repeat과 slice를 이용해서 붙이고 문제를 풀었다. 하지만 더욱 쉽게 풀수 있게 해주는 메소드가 존재했다....

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)

//항상 숙지하자

 


단연 생각을 많이하게 했던 문제... 노트에 직접 적어가며 생각했다... 대각선 길이를 생각해야하나... 정렬을 해야하나 여러생각을 하다가... 애초에 가로길이를 세로 길이보다 길게 만든 후에 비교하면 더욱 쉽겠구나라는 것을 깨닫고 모든 명함을 같은 조건에 만들어놓고 너비와 높이의 max 값을 찾아냈다.

 

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 표기법을 사용함. 주로 Worst case를 기준으로 분석함. 다양한 알고리즘의 효율성을 파악하고자 많이 씀.

 

최악의 경우의 수를 나타내는 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

 

 

시간 복잡도, 공간복잡도를 생각하면서 더욱 효율적인 알고리즘을 짜는 것은 많은 데이터를 처리하는데 더욱 중요해질 것이다. 프론트엔드 개발자로서 성장하면서도 기본이 되는 알고리즘 공부를 항상 틈틈히 잊지 않게 공부를 해야겠다!