이정훈

이정훈

기록을 습관화하자

0920 - 0926

0924

55일 차

2교시

소스코드의 평가되고 실행되는 과정이 모두 실행 컨텍스트에서 실행된다.
다른 말로는 심볼 테이블이라고 한다. 여기서 심볼은 식별자를 뜻한다.

변수 선언이라는 것은 식별자를 실행 컨텍스트 등록하는 것

초기화를 하는 습관을 가져야 한다.

bindingObject를 통해서 전역 객체와 연결하는 이유
환경에 따라서 전역 객체가 다르기 때문에

함수에서 this는 호출될 때(동적) 상위 스코프는 함수가 정의될 때(정적) 생성된다.

3교시

window 객체를 가리키는 것이 아무것도 없더라도 window 객체는 사라지지 않는다.

실행 컨텍스트가 없더라도 렉시컬 환경은 만들 수 있다.

for 문의 초기화 문이나 조건식, 증감문은 사실 코드 블럭 내부에 있는 것이다.

4교시

원칙적, 이론적으로는 자바스크립트의 모든 함수가 클로저이다.
하지만 일반적으로 외부 함수보다 더 오래 살아남는 중첩함수이면서 중첩함수가 외부 함수의 식별자를 참조해야 클로저라고 한다.

debugger 지시자를 써 주면 코드가 break가 걸린다.

클로저는 상태를 안전하게 변경하고 유지하기 위해 사용한다.

0925

알고리즘 문제 풀이

이번 주말에는 BFS, DFS와 이를 활용한 그래프 문제를 풀기로 했다.
여기서 새로 알게 된 내용과 어떻게 문제를 풀었는지를 정리해보고자 한다.

프로그래머스 Level3 - 여행경로

function solution(tickets) {
  const answer = [];
  const tmp = [];
  const sh = {};
  let flag = false;

  tickets.forEach(([start, end]) => {
    sh[start] = [...(sh[start] || []), end];
  });

  Object.keys(sh).forEach((v) => sh[v].sort());

  function DFS(v) {
    if (flag) return;
    if (tmp.length === tickets.length + 1) {
      answer.push(tmp.slice());
      flag = true;
    } else {
      if (sh[v] !== undefined) {
        const len = sh[v].length;
        for (let i = 0; i < len; i++) {
          const port = sh[v].shift();
          tmp.push(port);
          DFS(port);
          sh[v].push(port);
          tmp.pop();
        }
      }
    }
  }
  tmp.push("ICN");
  DFS("ICN");

  return answer[0];
}

console.log(
  solution([
    ["ICN", "JFK"],
    ["HND", "IAD"],
    ["JFK", "HND"],
  ])
);
console.log(
  solution([
    ["ICN", "SFO"],
    ["ICN", "ATL"],
    ["SFO", "ATL"],
    ["ATL", "ICN"],
    ["ATL", "SFO"],
  ])
);
  • 배열 고차 함수인 sort() 메서드는 생각보다 강력했다. 2차 배열을 대상으로 sort메서드를 돌리면 각 배열마다 앞 요소부터 문자열을 비교하여 유니코드 상으로 정렬해주고, 문자열이 같다면 다음 요소의 문자열을 비교하여 정렬해주었다.
  • 배열이나 객체 디스트럭처링 문법을 적극적으로 사용한다면 기본 세팅을 해줄 때 훨씬 간편하고 깔끔하게 코딩을 할 수 있다.
  • DFS를 재귀적으로 타고 들어가다보면 막히는 경로가 생길수도 있는데, 이를 생각하지 못하고 코딩했다. 더 이상 경로가 없는 경우를 되돌아가기 위해 sh[v] !== undefined를 설정해주었다.
  • 1번 테스트케이스가 조금 시간이 오래 걸렸는데, 애초에 처음부터 알파벳 순으로 정렬하고 DFS를 돌리면 처음으로 찾는 경로가 해답이 되므로 시간을 많이 줄일 수 있었다.

프로그래머스 Level3 - 단어 변환

function canChange(word1, word2) {
  let cnt = 0;
  for (let i = 0; i < word1.length; i++) {
    if (word1[i] !== word2[i]) cnt++;
  }

  return cnt === 1 ? true : false;
}

function solution(begin, target, words) {
  if (!words.includes(target)) return 0;

  let answer = 0;
  let queue = [];
  let sh = new Map();

  words.forEach((v) => sh.set(v, 0));

  function BFS() {
    while (queue.length) {
      answer++;
      const len = queue.length;
      for (let i = 0; i < len; i++) {
        const word = queue.shift();

        for (let j = 0; j < words.length; j++) {
          if (!sh.get(words[j]) && canChange(word, words[j])) {
            console.log(word, words[j], answer);
            if (words[j] === target) return;
            queue.push(words[j]);
            sh.set(words[j], 1);
          }
        }
      }
    }
  }
  queue.push(begin);
  BFS();

  return answer;
}

console.log(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]));
console.log(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log"]));
  • BFS를 활용하여 문제를 해결했다.
  • BFS 문제를 풀 때 주의할 점을 발견했는데, 일반적으로 BFS는 while문 안에서 queue가 빌 때까지 진행된다.
    • 초기에 넣을 queue를 세팅하고 BFS를 호출하는데, queue에서 모두 꺼내어 반복문을 돌리고 반복문 내부에서 새롭게 돌려야 하는 queue 요소들을 push한다. 이 과정이 하나의 레벨이다.
    • 이 때 반복문을 돌릴 때 내부에서 queue에 새로운 요소들을 push 하므로 queue의 길이가 바뀔 수 있다. 때문에 반복문을 돌리기 전에 queue의 길이를 변수에 담고, 그 길이만큼만 반복문을 돌려야 한다.

프로그래머스 Level3 - 네트워크

function solution(n, edges) {
  let answer = 0;
  let ch = Array.from(Array(n)).fill(0);

  function DFS(v) {
    for (let i = 0; i < n; i++) {
      if (ch[i] === 0 && edges[v][i] === 1) {
        ch[i] = 1;
        DFS(i);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (ch[i] === 0) {
      answer++;
      ch[i] = 1;
      DFS(i);
    }
  }

  return answer;
}

console.log(
  solution(3, [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1],
  ])
);
console.log(
  solution(3, [
    [1, 1, 0],
    [1, 1, 1],
    [0, 1, 1],
  ])
);
  • 처음에는 이 문제를 union&find 문제로 풀어야 하나 생각했다.
  • 하지만 DFS 만으로도 문제를 해결할 수 있었다.
  • 이 문제의 핵심은 외부에서 DFS를 반복문으로 실행하는 것. 반복문이 한 번 돌때마다 들린적 없는 곳이라면, 들렸다고 배열에 체크하고 다시 DFS를 실행했다. 그러면 DFS에서 연관있는 곳들을 체크 배열에 체크해준다. 이를 처음부터 끝까지 반복문을 돌리고 나면 몇 개로 네트워크가 떨어져 있는지 구할 수 있다.

0926

일 - 알고리즘 문제 풀이

오늘은 Union & Find 개념을 학습하고 이전에 풀었던 문제를 다시 풀었다.
MST와 크루스칼 알고리즘에 대해서도 복습하고, 그래프 관련 문제를 풀어보았다.

복습

핵심은 Find 함수에 있다.

function Find(v) {
  if (unf[v] === v) return v;
  else return (unf[v] = Find(unf[v]));
}
  • 처음에 노드를 인덱스 값으로 초기화한다. (각자 다른 집합을 가지고 있다.)
  • Union 함수를 쓰거나, 서로 집합이 다르면 같게 만들어주는 로직을 작성하여 노드를 연결해준다.
  • Find 함수는 노드가 속한 소속을 찾아준다. 이를 활용하여 연결 되었는지, 안되었는지 확인할 수 있다.
  • MST는 그래프에서 모든 정점을 포함하는 트리인 스패닝 트리 중 가중치가 최소인 트리이다.
    • 이는 n개의 노드가 있다면 n-1개의 간선으로 이어져야 한다.
    • 크루스칼 알고리즘을 적용하기 위해서는 가중치를 오름차순으로 정렬한 뒤, Find 함수로 두 노드가 연결되었는지 확인하면서 안된 경우에만 이어주고 가중치를 더해주면 된다.

프로그래머스 Level3 - 여행경로

function solution(n, edge) {
  let answer = 0;
  const ch = Array.from({ length: n + 1 }, () => 0);
  const graph = Array.from({ length: n + 1 }, () => []);
  let tmp = [];

  for (let [a, b] of edge) {
    graph[a].push(b);
    graph[b].push(a);
  }

  function BFS() {
    let queue = [];
    queue.push(1);

    while (queue.length) {
      let len = queue.length;
      tmp = [];
      for (let i = 0; i < len; i++) {
        let node = queue.shift();
        tmp.push(node);
        for (let x of graph[node]) {
          if (ch[x] === 0) {
            ch[x] = 1;
            queue.push(x);
          }
        }
      }
    }
  }
  ch[1] = 1;
  BFS();
  answer = tmp.length;
  return answer;
}

console.log(
  solution(6, [
    [3, 6],
    [4, 3],
    [3, 2],
    [1, 3],
    [1, 2],
    [2, 4],
    [5, 2],
  ])
);
  • 어제 오늘 학습한 그래프와 BFS를 조합하여 문제를 해결하였다.
  • 양방향 그래프이므로 이를 생각해서 그래프에 삽입하였다.
  • 만약 갔던 노드라면 BFS 특성상 최단거리가 될 수 없으므로 패스하기 위해서 배열을 사용하였다.
  • 짧은 시간에 학습하여 프로그래머스 3단계 문제들을 여러개 푸니 성취감이 상당했다.

태그:

카테고리:

업데이트:

참고