📝 오늘 한 것

1. 프로그래머스 문제 풀이 - 예산

2. 다익스트라 알고리즘 / 공간 복잡도

📖 학습 자료

1. 책 '누구나 자료 구조와 알고리즘'

📚 배운 것

1. 프로그래머스 문제 풀이

1) Level 1 문제

(1) 예산

• Summer/Winter Coding(~2018)

🔎 내가 작성한 풀이

function solution(d, budget) {
  d.sort((a, b) => b - a);
  let count = 0;
  let pop = d.pop();

  while (budget >= pop) {
    budget = budget - pop;
    pop = d.pop();
    count++;
  }

  return count;
}

---

13장. 그래프로 뭐든지 연결하기

어제 공부에 이어서

5) 다익스트라 알고리즘(Dijkstra Algorithm)

• 가중치 그래프를 이용해 최단 경로 문제를 푸는 알고리즘

• 가중치를 각 도시에서 다른 도시로 갈 때 얼마나 빨리 갈 수 있느냐로 표현함으로써, 매핑과 GPS 기술에서 사용할 수도 있다. 이를 통해 한 장소에서 다른 장소로 운전할 때 어떤 경로로 가야 할지 결정할 수 있다.

• 아래에서는 가중치를 가격으로 표현한 예제를 살펴볼 것이다.

(1) 설명

[ 예제 ]

애틀란타로부터 다른 도시들까지의 가장 저렴한 경로를 기록해라

[ 코드 설명 ]

1. 시작 정점을 현재 정점으로 한다.

2. 현재 정점에 인접한 모든 정점을 확인해서, 시작 정점으로부터, 알려진 모든 위치까지의 가중치를 계산하고 기록한다.

3. 다음 현재 정점을 결정하려면, 시작 정점으로부터 도달할 수 있는, 방문하지 않은, 가장 저렴한, 알려진, 정점을 찾는다.

4. 그래프 내 모든 정점을 방문할 때까지 1 ~ 3 단계를 반복한다.

(2) 코드 구현

pp.292 ~ 294
Ruby로 구현된 코드 → JavaScript로 변환

🙋‍♀️ Q1. 미완성 코드다. 오류가 발생했는데 더 이상 어떻게 수정해야 할지 모르겠다. 발생한 오류는 아래와 같다. (코드 참고)

Uncaught TypeError: Cannot convert undefined or null to object
    at Function.keys (<anonymous>)
    at dijkstra (🙋‍♀️ Q1(1))
    at 🙋‍♀️ Q1(2)

→ 💡 원인은 알겠는데 어떻게 고쳐야 하는지를 모르겠다.

🙋‍♀️ Q2. 위 오류가 발생한 원인 같은데 해결을 못하겠다. (코드 참고)
→ 💡 A2 참고

class City {
  constructor(name) {
    this.name = name;
    this.routes = {};
    this.visited = false;
  }

  add_route(city, price_info) {
    this.routes[city] = price_info;
  }
}

// 가중 그래프 만들기
const atlanta = new City('atlanta');
const boston = new City('boston');
const chicago = new City('chicago');
const denver = new City('denver');
const elpaso = new City('elpaso');


atlanta.add_route(boston, 100);
atlanta.add_route(denver, 160);
boston.add_route(chicago, 120);
boston.add_route(denver, 180);
chicago.add_route(elpaso, 80);
denver.add_route(chicago, 40);
denver.add_route(elpaso, 140);
elpaso.add_route(boston, 100);
/* 🙋‍♀️ Q2. 이렇게 쓴 후 콘솔 창에 atlanta를 출력하니까 {'[object Object]': 160}이 나온다.
심지어 atlanta.routes[chicago]를 출력해도 160이 나온다.
테스트 해보니까 atlanta.routes[오브젝트]를 출력하면 어떤 오브젝트건 간에 160이 나온다.
이게 왜 이렇게 되는 건지 모르겠다. */

/* 그래서 밑의 다익스트라 알고리즘 코드는 아래 주석처럼 boston.name, denver.name이라고 쓴 상태로 구현을 했다.
근데 이번엔 아마도 이것 때문에 밑에서 오류가 뜨는 거 같다...*/
// atlanta.add_route(boston.name, 100);
// atlanta.add_route(denver.name, 160);

/* 💡 A2. add_route 함수는 첫 번째 인자로 city를 받는데 전해주는 값이 문자열이 아닌 object라서 에러가 생긴 것
다익스트라 알고리즘이랑 전혀 상관없는 에러였...ㅎㅎ */


// 🔥 다익스트라의 알고리즘 (어느 도시에서 다른 도시들로 가는 각각의 가장 저렴한 경로 구하기)
function dijkstra(starting_city, other_cities) {
  // 도시 : [시작 도시로부터 이 도시까지의 가장 저렴한 가격, 해당 경로에서 이 도시 바로 전에 들르는 도시]
  const routes_from_city = {};

  // 시작 도시에서 시작 도시로 가는 비용은 0
  routes_from_city[starting_city] = [0, starting_city];

  // 다른 도시들 데이터 초기화 (시작 도시 외에 다른 도시들로 가는 비용과 경로는 아직 알려지지 않았으므로 일단 무한대 값 할당)
  other_cities.forEach(city => routes_from_city[city] = [Infinity, null]);
  console.log(routes_from_city);

  // 방문했던 도시 기록
  const visited_cities = [];

  // 시작 도시를 현재 도시[정점]로 지정
  let curr_city = starting_city;

  // 각 도시를 방문하는 루프 시작
  while(curr_city) {
    visited_cities.push(curr_city);

    // 현재 도시로부터 각 경로를 확인
    Object.keys(curr_city.routes).forEach(city => { // 🙋‍♀️ Q1(1)
      if (routes_from_city[city][0] > curr_city.routes[city] + routes_from_city[curr_city][0]) {
        routes_from_city[city] = [curr_city.routes[city] + routes_from_city[curr_city][0], curr_city]
      }
    });

    // 다음으로 방문할 도시 결정
    curr_city = null;
    let cheapest_route_from_curr_city = Infinity;
    Object.keys(routes_from_city).forEach(city => {
      if (routes_from_city[city][0] < cheapest_route_from_curr_city && !visited_cities.includes(city)) {
        cheapest_route_from_curr_city = routes_from_city[city][0];
        curr_city = city;
      }
    });
  }

  return routes_from_city;
}

const route = dijkstra(atlanta, ['boston', 'chicago', 'denver', 'elpaso']);
// 🙋‍♀️ Q1(2)

Object.keys(route).forEach(city => console.log(`city: ${city}, price_info: ${route[city][0]}`));

14장. 공간 제약 다루기

📌 시간 복잡도 : 자료 구조나 알고리즘이 완료까지 얼마나 많은 단계가 걸리느냐

📌 공간 복잡도 : 자료 구조나 알고리즘이 완료까지 얼마나 많은 메모리를 소비하느냐

1) 빅 오 표기법

💡 알고리즘의 효율성

• 알고리즘의 속도

  데이터 원소가 N개일 때, 알고리즘은 N에 비례하는 연산 단계가 걸린다.

• 알고리즘에 최대 얼마나 많은 공간이 필요한가

  데이터 원소가 N개일 때, 알고리즘은 메모리 내 추가로 들어 있는 데이터 원소 수에 비례해서 공간을 소모한다.

💡 들어가기 전에 앞서, '여기서는' 공간 복잡도를 계산할 때 추가로 소비되는 메모리(보조 공간)만을 고려한다. 즉, 원래 데이터는 계산 시 포함하지 않는다.

(1) O(N)

function makeUpperCase(arr) {
  const newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr[i] = arr[i].toUpperCase();
  }
  return newArr;
}

위 함수는 원소 N개를 받아 원소 N개인 새로운 배열을 생성한다.
예를 들어, 원래 배열의 원소가 5개, 10개이면 원소의 개수가 5개, 10개인 새로운 배열을 생성한다.

따라서, 공간 효율성은 O(N)이다.
데이터의 크기가 N개면, 추가로 소비하는 공간은 N이 된다.

(2) O(1)

function makeUpperCase(arr) {
  for (let i = 0; i < arr.length; i++) {
    arr[i] = arr[i].toUpperCase();
  }
  return arr;
}

위 함수는 새 변수나 새 배열을 생성하지 않는다.
예를 들어, 원래 배열의 원소가 5개든 10개든 원래 배열 외에 어떤 메모리도 쓰지 않는다.

따라서, 공간 효율성은 O(1)이다.
데이터의 크기와 상관없이, 추가로 소비하는 공간은 0으로 항상 같다.

시간 복잡도에서 O(1)은, 데이터의 크기와 상관없이, 알고리즘 속도가 상수라는 뜻이다. 공간 복잡도에서 O(1)은, 데이터의 크기와 상관없이, 알고리즘이 소모하는 메모리가 상수라는 뜻이다.

2) 시간과 공간 트레이드 오프

[ 예제 ]

배열에 중복 값이 있는지 확인하는 코드

// 버전 1
function hasDuplicateValue(arr) {
  const newArr = [];
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        return true;
      }
    }
  }
  return false;
}

// 버전 2
function hasDuplicateValue(arr) {
  const checkedValue = [];
  for (let i = 0; i < arr.length; i++) {
    if (checkedValue[arr[i]] === undefined) {
      checkedValue[arr[i]] = 1;
    } else {
      return true;
    }
  }
  return false;
}

• 효율성 비교

  	시간 복잡도	공간 복잡도
  버전 1	O(N^2)	O(1)
  버전 2	O(N)	O(N)

• 상황에 따라 알맞은 버전을 골라 써야 한다

✨ 내일 할 것

1. 프로그래머스 문제 풀이