📝 오늘 한 것

1. 프로그래머스 문제 풀이 - 소수 찾기 / 에라토스테네스의 체

2. 무방향 그래프 / 방향 그래프 / 너비 우선 탐색 / 그래프 데이터베이스 / 가중 그래프

📖 학습 자료

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

📚 배운 것

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

1) Level 1 문제

(1) 소수 찾기

🔎 처음 작성한 풀이

• 실제 채점에서 테스트 케이스 3개가 시간 초과로 통과 못했다. 당연히 효율성 테스트는 0점.

function solution(n) {
  let noPrimeCount = 1;
  for (let i = 2; i <= n; i++) {
    for (let j = 2; j < i; j++) {
      if (i % j === 0) {
        noPrimeCount++;
        break;
      }
    }
  }
  return n - noPrimeCount;
}

🔎 두 번째 작성한 풀이

• 소수를 판별하기 위해 2부터 시작해서 하나씩 나눠보는 방법 말고 또 뭐가 있을까. 이 부분에서 시간을 많이 소요하는 거 같다.

function solution(n) {
  let nums = [];
  for (let i = 2; i <= n; i++) {
    nums.push(i);
  }

  const primes = nums.filter(num => {
    for (let i = 2; i < num; i++) {
      if (num % i === 0) {
        return false;
      }
    }
    return true;
  });

  return primes.length;
}

🔎 다른 사람의 풀이

• Javascript 소수 찾기 - 에라토스테네스의 체 참고

function solution(n) {
  const primes = new Array(n+1).fill(true).fill(false, 0, 2);
  // 💡 배열의 인덱스를 숫자로 활용할 것
  // 따라서, n+1자리 배열을 true(소수를 의미)로 채운 후
  // 0과 1은 소수가 아니므로 아예 처음부터 false로 바꿔줌
  
  for (let i = 2; i * i <= n; i++) { // 💡 i는 (2 ~ 'n의 제곱근')까지 1씩 증가시킴
    if (primes[i] === true) { // 배열의 i번째 자리에 있는 값이 true라면(즉, i = 소수)
      for (let j = i * i; j <= n; j += i) { // 💡 j는 i * i부터 시작되는 i의 배수를 의미함
        primes[j] = false; // 배열의 j번째 자리에 있는 값들을 전부 false로 바꿔줌(∵ j ≠ 소수)
      }
    }
  }

  return primes.filter(e => e).length;
  // 값이 true인 요소(=소수)만 남긴 배열의 길이(=소수의 개수)를 리턴
}

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

📌 그래프는 데이터들의 어떻게 연결되어 있는지를 파악하기 쉬운 자료 구조이다.

📌 그래프 용어

정점	간선
노드로 표현	각 선으로 표현
ex. 사람	ex. 사람 간 관계

1) 그래프

(1) 설명 및 코드 구현

💡 대표적으로 해시 테이블을 이용해 구현 가능하다

🔎 무방향 그래프

• 상호 관계를 표현하는 그래프 ex) 페이스북 친구
• 그림으로 표현할 때 단순 선을 이용한다

2차원 배열에 관계 리스트를 저장할 수 있다.
이 경우, alice의 전체 친구 리스트를 알기 위해 O(N)이 걸린다.

const relationships = [
  ['alice', 'bob'],
  ['bob', 'cynthia'],
  ['alice', 'diana'],
  ['bob', 'diana']
];

대신에 그래프를 이용하면, O(1) 만에 전체 친구 리스트 검색이 가능하다.

p.263
Ruby로 구현된 코드 → JavaScript로 변환

const friends = {
  'alice': ['bob', 'diana'],
  'bob': ['alice', 'cynthia', 'diana'],
  'cynthia': ['bob'],
  'diana': ['alice', 'bob']
};

console.log(friends.alice); // ['bob', 'diana'] → O(1) 만에 검색 가능

🔎 방향 그래프

• 방향성이 있는 관계를 표현하는 그래프 ex) 트위터 팔로우
• 그림으로 표현할 때 화살표를 이용한다

const follwees = {
  'alice': ['bob', 'cynthia'],
  'bob': ['cynthia'],
  'cynthia': ['bob']
};

💡 객체 지향 구현도 가능하다

class Person {
  constructor(name) {
    this.name = name;
    this.friends = [];
  }

  add_friend(friend) {
    this.friends.push(friend);
  }
}

const mary = new Person('mary');
const peter = new Person('peter');
mary.add_friend(peter);
peter.add_friend(mary);

2) 너비 우선 탐색

• 그래프를 순회하는 방법으로 너비 우선 탐색과 깊이 우선 탐색이 있다
• 이 책에서는 너비 우선 탐색 알고리즘만 다룬다
• 너비 우선 탐색 알고리즘은 처리할 정점을 추적하기 위해 큐(Queue)를 사용한다

(1) 설명

[ 예제 ]

링크드인은 직접 네트워크 외에 2차, 3차 커넥션을 정할 수 있는 기능을 가지고 있다. 예를 들어, (앨리스 - 밥 - 신시아)가 연결되어 있을 때, 앨리스는 밥을 통해 신시아와 연결되므로, 신시아는 앨리스의 2차 커넥션이다.

이러한 비직접적인 커넥션을 모두 포함해 앨리스의 전체 네트워크에 있는 이름을 표시하고자 할 때 그래프 탐색을 이용할 수 있다

[ 코드 설명 ]

• 큐에서 정점을 삭제(shift)해 이를 현재 정점(curr_vertex)으로 지정한다

• 각 현재 정점마다 그 정점의 인접 정점을 각각(forEach) 방문한다

• 💡 queue 외에 visited_vertex에도 방문한 노드를 하나씩 추가해 기록해놓은 후 알고리즘이 종료됐을 때 이러한 노드들의 visited 속성을 다시 false로 바꿔준다 (이미 방문한 정점은 큐에 넣지 않기 위해)

(2) 코드 구현

p.275
Ruby로 구현된 코드 → JavaScript로 변환

위의 그래프 객체 지향 구현 코드에 '너비 우선 탐색' 메서드를 추가함

class Person {
  constructor(name) {
    this.name = name;
    this.friends = [];
    this.visited = false; // 추가
  }

  // 그래프 만들기 (관계 설정하기) ❗
  add_friend(friend) {
    this.friends.push(friend);
  }

  // 너비 우선 탐색 ❗
  display_network() {
    // 방문할 노드를 기록할 visited_vertex
    const visited_vertex = [this];
    // 큐를 생성한다. 처음에는 루트 정점을 포함한다.
    const queue = [this];
    this.visited = true;

    while (queue.length) {
      let curr_vertex = queue.shift(); // 큐로부터 제거한 정점이 현재 정점이다
      console.log(curr_vertex.name);
      curr_vertex.visited = true;

      // 현재 정점의 인접 정점을 모두 큐에 추가한다
      curr_vertex.friends.forEach(friend => {
        if (!friend.visited) {
          visited_vertex.push(friend);
          queue.push(friend);
          friend.visited = true;
        }
      });
    }

    // 알고리즘의 종료된 후 각 노드의 'visited' 속성을 false로 할당한다
    visited_vertex.forEach(friend => friend.visited = true);
  }
}

// 그래프 만들기 (관계 설정하기)
const alice = new Person('alice');
const bob = new Person('bob');
const candy = new Person('candy');
const derek = new Person('derek');
const elaine = new Person('elaine');
alice.add_friend(bob);
alice.add_friend(candy);
alice.add_friend(derek);
alice.add_friend(elaine);

const fred = new Person('fred');
const helen = new Person('helen');
bob.add_friend(fred);
bob.add_friend(helen);

const gina = new Person('gina');
const irena = new Person('irena');
derek.add_friend(gina);
derek.add_friend(irena);

// 그래프 확인
console.log(alice);

// 너비 우선 탐색 - alice의 전체 네트워크에 있는 이름 표시
alice.display_network();

(3) 빅 오 (정점 처리 + 간선 처리)

[ 정점 처리 ]
위에서 살펴본 바로는,
그래프에 V개의 정점이 있을 때, 큐에서 V번 삭제한다.
이를 빅오 표기법으로 O(V)라고 부른다.

이때, 지금까지처럼 N개의 정점이 있을 때 효율성을 O(N)이라고 하지 않고 O(V)라고 하는 이유는 무엇일까? 이는 너비 우선 탐색이 단순히 정점만 처리하는 게 아니라 간선도 처리하는 단계를 추가로 포함하기 때문이다.

위 코드에서 현재 정점의 인접 정점을 모두 큐에 추가하는 부분만 떼어서 살펴보자.

curr_vertex.friends.forEach(friend => {
  if (!friend.visited) {
    visited_vertex.push(friend);
    queue.push(friend);
    friend.visited = true;
  }
});

현재 정점의 인접 정점들의 visited 속성이 false일 때만 큐에 그 인접 정점을 추가하도록 했지만, visited 속성이 true인지 false인지 알기 위해서는 어차피 모든 인접 정점들을 전부 방문해야 한다.

예를 들어, 현재 정점이 bob인 경우에, fred는 visited 속성이 false이므로 큐에 집어 넣고, alice는 visited 속성이 true이므로 큐에 집어넣지는 않는다. 이때 큐에 집어넣든 안 집어넣든 방문은 하므로 단계에는 포함이 된다.

자세히 살펴보면, 너비 우선 탐색에서 인접한 정점에 방문하는 횟수는 그래프에 있는 간선 수의 2배이다.
이는 각 간선이 두 정점을 연결하고, 모든 정점에 대해 인접한 정점을 모두 확인하기 때문이다.이 과정에서 각 간선은 2번씩 쓰인다.

[ 간선 처리 ]
그래프에 E개의 간선이 있을 때, 인접한 정점을 2E번 확인한다.
이를 빅오 표기법으로 O(E)라고 부른다. (빅오는 상수 무시)

💡 정리하면,

너비 우선 탐색의 효율성은 O(V+E)라고 할 수 있다.

3) 그래프 데이터베이스

[ 예제 ]

서로가 모두 연결된 5명의 친구로 이뤄진 소셜 네트워크가 있다고 하자.

(1) 전통적인 관계형 데이터베이스

관계형 데이터베이스를 이용해 다섯 명의 정보를 저장할 수 있다.
한 테이블에는 각 사용자의 개인 정보를, 다른 테이블에는 친구들 간 관계(user_id, friend_id)를 저장할 수 있다.

이때, 5명 중 1명인 A가 자신의 모든 친구들의 개인 정보를 요청한다고 하자.

먼저, 애플리케이션은 관계 테이블에서 A의 user_id가 적혀 있는 모든 줄을 찾아 전체 friend_id 리스트를 만들어야 한다. 그 후, 개인 정보 테이블에서 friend_id에 대응하는 각 줄을 찾아야 한다.

(예시로 든 관계형 데이터베이스의 경우) 이진 검색이 가능하므로 각 친구를 검색하는 데는 O(logN)이 걸린다. 정리하면, 친구가 M명 일 때 정보를 가져오는 효율성은 O(M logN)이 된다.

(2) 그래프 데이터베이스

그래프 데이터베이스를 이용해 다섯 명의 정보를 저장할 수도 있다.
데이터 베이스 내 각 정점은 각 사용자의 모든 정보를 저장한다.

마찬가지로, 5명 중 1명인 a가 자신의 모든 친구들의 개인 정보를 요청한다고 하자.

애플리케이션은 그래프 데이터베이스에서 A를 찾은 후에 A와 4명의 친구들이 연결되어 있는 간선을 순회해 정보를 가져온다.

A와 4명의 친구들이 간선으로 연결되어 있으므로 각 친구의 정보를 가져오는 데는 딱 한 단계가 걸릴 뿐이다. 정리하면, 친구가 N명일 때 정보를 가져오는 효율성은 O(N)이 된다.

4) 가중 그래프

(1) 설명

• 가중 그래프란 그래프의 간선에 추가적인 정보가 포함된 그래프를 말한다.

• 무방향 그래프
  ex. 각 도시를 정점으로 하며, 각 정점을 잇는 간선에는 도시들 간 거리를 나타내는 숫자가 붙어 있는 그래프

• 방향 그래프
  ex. 각 도시를 정점으로 하며, 각 정점을 잇는 간선에는 한 도시에서 다른 도시로 가는 항공료를 나타내는 숫자가 붙어 있는 그래프 (간선은 화살표가 있는 선이고, 항공료는 서로 다를 수 있다)

(2) 코드 구현

• 가중 그래프는 인접 정점을 표현할 때 해시 테이블을 이용해야 한다.

p.284
Ruby로 구현된 코드 → JavaScript로 변환

class City {
  constructor(name) {
    this.name = name;
    this.routes = {}; // 해시 테이블 o, 배열 x
  }

  add_route(city, price) {
    this.routes[city] = price; // 간선에 추가 정보를 포함
  }
}

const dallas = new City('Dallas');
const toronto = new City('Toronto');
dallas.add_route(toronto, 138);
toronto.add_route(dallas, 216);

✨ 내일 할 것

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

2. 책 계속 읽기