📝 오늘 한 것

1. 프로그래머스 문제 풀이 - 시저 암호 / 정수 내림차순으로 배치하기 / 이상한 문자 만들기 / 최대공약수와 최소공배수

2. 이진 트리 / 검색, 삽입, 삭제 / 정렬된 배열 VS 이진 트리

📖 학습 자료

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

📚 배운 것

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

1) Level 1 문제

(1) 시저 암호

🔎 내가 작성한 풀이

function solution(s, n) {
  const lower = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'];
  const upper = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];

  const newArr = s.split('').map(item => {
    // 공백
    if (item === ' ') {
      return ' ';
    }
    
    if (lower.includes(item)) { // 소문자
      const stringIndex = lower.indexOf(item) + n
      if (stringIndex <= 25) {
        return lower[stringIndex];
      } else {
        const newIndex = stringIndex % 25 - 1;
        return lower[newIndex];
      }
    } else { // 대문자
      const stringIndex = upper.indexOf(item) + n
      if (stringIndex <= 25) {
        return upper[stringIndex];
      } else {
        const newIndex = stringIndex % 25 - 1;
        return upper[newIndex];
      }
    }
  });

  return newArr.join('');
}

🔎 다른 사람의 풀이 1

• 나와 같은 흐름으로 풀었는데 훨씬 짧다. 조건부 삼항 연산자를 이용해textArr 변수에 먼저 lower인지 upper인지 판단해 배열을 할당한 후에 한 번에 코드를 작성했다.

• 나는 문제를 본 후 map()이 생각나서 문자열을 배열로 바꿨는데 굳이 배열로 바꿀 필요도 전혀 없었다.

function solution(s, n) {
  var upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  var lower = "abcdefghijklmnopqrstuvwxyz";
  var answer= '';

  for(var i =0; i <s.length; i++){
    var text = s[i];
    
    if(text == ' ') {
      answer += ' '; 
      continue;
    }
    
    var textArr = upper.includes(text) ? upper : lower;
    var index = textArr.indexOf(text) + n;
    if(index >= textArr.length) {
      index -= textArr.length;
    }

    answer += textArr[index];
  }
  
  return answer;
}

🔎 다른 사람의 풀이 2

• n이 1 ~ 25인 점을 이용한 풀이다. 한 번에 소문자, 대문자를 두 번씩 써줬다. (두 번째 쓸 때 마지막 z는 굳이 안 썼음)

function solution(s, n) {
  const chars = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY                          "
  return s.split('').map(e => chars[chars.indexOf(e)+n]).join('');
}

(2) 정수 내림차순으로 배치하기

🔎 내가 작성한 풀이

• parseInt(string) 대신에 +string이라고 작성해도 된다. 문자열에 + / - 기호가 붙으면 문자열이 숫자로 바뀐다.

function solution(n) {
  const string = (n + '').split('').sort((a, b) => b - a).join('');
  return parseInt(string);
  // return +string;
}

(3) 이상한 문자 만들기

🔎 내가 작성한 풀이

• 먼저, 주어진 문자열을 split()를 이용해 배열로 바꿔주었다. 그 후, map()을 이용해 그 배열의 요소 하나하나를 다시 하위 배열로 바꿔준 후 또 다시 map()을 이용해 그 하위 배열의 요소 하나하나를 조건에 맞게 바꿔주었다. 마지막으로, 하위 배열을 join()을 이용해 문자열로 만들어준 후 또 다시 join()을 이용해 상위 배열을 문자열로 만들어주었다.

function solution(s) {
  return s.split(' ').map(s => s.split('').map((s, i) => i % 2 === 0 ? s.toUpperCase() : s.toLowerCase()).join('')).join(' ');
}

(4) 최대공약수와 최소공배수

🔎 내가 작성한 풀이

function solution(n, m) {
  const limit = n < m ? m : n;
  const common_factor = [];

  for (let i = 1; i <= limit; i++) {
    if (n % i === 0 && m % i === 0) {
      common_factor.push(i);
    }
  }

  const gcf = Math.max(...common_factor);
  const lcm = gcf * (n / gcf) * (m / gcf);

  return [gcf, lcm];
}

---

12장. 이진 트리로 속도 향상

📌 정렬된 배열 : 검색 빠름(이진 검색) / 삽입, 삭제 느림

📌 해시 테이블 : 검색, 삽입, 삭제 빠름 / 순서 유지 불가능

📌 이진 트리 : 검색, 삽입, 삭제 빠름 / 순서 유지 가능

1) 이진 트리(Binary Tree)

(1) 설명

🔎 트리(Tree)

• 트리는 연결 리스트와 마찬가지로 노드 기반 자료 구조이다.

• 연결 리스트에서 각 노드는 다른 한 노드로의 링크만 포함하는 반면,
  트리에서 각 노드는 여러 노드로의 링크를 포함한다.

• 가장 상위 노드를 '루트'라고 부른다.

• '부모' 노드는 '자식' 노드를 가진다.

• 트리에는 '레벨'이 있다.

🔎 이진 트리(Binary Tree)

• 각 노드의 자식은 0 ~ 2개이다.

• 한 노드의 자식이 둘이면, 한 자식은 부모보다 작은 값을, 다른 자식은 부모보다 큰 값을 가져야 한다.

(2) 코드 구현

p.241
Python으로 구현된 코드 → JavaScript로 변환

class TreeNode {
  constructor(data, left_child = null, right_child = null) {
    this.data = data;
    this.left_child = left_child;
    this.right_child = right_child;
  }
}

// 왼쪽 노드와 오른쪽 노드를 만들고
const node_1 = new TreeNode(1);
const node_2 = new TreeNode(10);

// 이를 이용해 루트(가장 상위 노드)를 만든다
const root = new TreeNode(5, node_1, node_2);

console.log(root);
// TreeNode {data: 5, left_child: TreeNode, right_child: TreeNode}

(3) 이진 트리의 연산

• 트리 검색은, 반드시 루트부터 시작해야 한다

pp.242 ~ 257
Python으로 구현된 코드 → JavaScript로 변환

class TreeNode {
  constructor(value, left_child = null, right_child = null) {
    this.value = value;
    this.left_child = left_child;
    this.right_child = right_child;
  }
}

// 트리 노드 생성
const node_1 = new TreeNode(1);
const node_2 = new TreeNode(10);
const root = new TreeNode(5, node_1, node_2);
console.log(root); // TreeNode {value: 5, left_child: TreeNode, right_child: TreeNode}



// 검색 ❗ (찾는 값이 어떤 노드에 있는지를 검색)
function search(value, node) {
  if (node === null || node.value === value) {
    return node;
  } else if (node.value < value) {
    return search(value, node.right_child);
  } else {
    return search(value, node.left_child);
  }
}

const search8 = search(8, root); // 트리 검색은 반드시 '루트'부터 시작해야 함
console.log(search8); // null



// 삽입 ❗
function insert(value, node) {
  if (node.value < value) { // 대소 비교
    if (node.right_child === null) { // 더 이상 자식 노드가 없으면
      node.right_child = new TreeNode(value); // 그 위치에 새 노드 추가
    } else {
      insert(value, node.right_child); // 자식 노득가 있으면 다시 대소 비교
    }
  } else if (node.value > value) { // 대소 비교
    if (node.left_child === null) { // 더 이상 자식 노드가 없으면
      node.left_child = new TreeNode(value); // 그 위치에 새 노드 추가
    } else {
      insert(value, node.left_child); // 자식 노득가 있으면 다시 대소 비교
    }
  }
}

const insert13 = insert(13, root);
console.log(root); // 값이 10인 노드의 오른쪽 자식 노드에 값이 13인 노드가 추가됨



// 🔥 '왜' 재귀 함수를 사용해서 구현하는가? 어떻게 이진 트리의 의미를 안 후에 재귀 함수를 사용해서 구현해야 겠다고 생각할 수 있는 걸까.
// 🔥 테스트 케이스를 추가해 호출 스택을 그림으로 그려서 차근차근 따라가면 이해가 되는 것도 같은데 코드만 보면 막막하다. 결국 이해 안된다는 뜻.
// 삭제 ❗
function remove(valueToRemove, node) {
  // 기저 조건
  if (node === null) {
    return null;
  } else if (valueToRemove < node.value) {
    node.left_child = remove(valueToRemove, node.left_child);
  } else if (valueToRemove > node.value) {
    node.right_child = remove(valueToRemove, node.right_child);
  } else { // 현재 노드가 삭제하려는 노드인 경우
    if (node.left_child === null) {
      return node.right_child;
    } else if (node.right_child === null) {
      return node.left_child;
    } else { // 현재 노드에 자식 노드가 둘이면
      node.right_child = lift(node.right_child, node);
      return node;
    }
  }
}

function lift(node, nodeToRemove) {
  if (node.left_child) {
    node.left_child = lift(node.left_child, nodeToRemove);
    return node;
  } else {
    nodeToRemove.value = node.value;
    return node.right_child;
  }
}

const remove5 = remove(10, root);
console.log(root); // 값이 10인 노드가 삭제되고, 값이 13인 노드가 그 자리에 위치하게 됨

🙋‍♀️ Q1. 위 코드 중 이진 트리의 '삭제' 부분이 이해가 안된다.

(4) 빅 오

1. 검색

   각 단계를 수행할 때마다 대소 비교를 통해 값이 들어 있는 공간 중 반을 제거한다.
   따라서, 이진 트리 검색의 효율성은 O(logN)이다.

   +) 정렬된 배열 검색(이진 검색)의 효율성인 O(logN)과 같다.

2. 삽입

   먼저, 새 노드가 들어갈 올바른 위치를 찾아야 한다.
   각 단계를 수행할 때마다 대소 비교를 진행한다.

   이때, 정렬된 데이터를 트리에 삽입하면, 불균형이 심한 트리가 되고 효율성이 안 좋을 확률이 높다. → 최악의 시나리오 O(N)

   ex) 1 ~ 5를 순서대로 (계속 오른쪽 노드에만) 삽입한 트리에서 5를 검색하기 위해서는 5단계 즉, O(N)이 걸린다.

   반면, 무작위로 정렬된 데이터를 트리에 삽입하면, 대개 균형 잡힌 트리가 되고 효율성이 좋을 확률이 높다. → 평균 시나리오 O(logN)

   ex) 3, 2, 4, 1, 5를 순서대로 삽입한 트리에서 5를 검색하기 위해서는 3단계가 걸릴 뿐이다.

   더 이상 자식이 없는 노드가 나올 때까지 대소 비교를 계속 진행한다.
   더 이상 자식이 없느 노드 즉, 올바른 위치를 찾았으면, 1단계에 걸쳐 삽입을 진행한다. (빅오는 상수 무시)

   따라서, 평균적인 시나리오에서 이진 트리 삽입의 효율성은 O(logN)이다.

   +) 정렬된 배열 삽입의 효율성인 O(N)에 비해 매우 좋다.

   💡 정렬된 배열을 이진 트리로 변환하고자 할 때는, 먼저 데이터 순서를 무작위로 만드는 게 좋다 !

3. 삭제

   삭제할 노드에 자식이 없으면, 그냥 삭제한다

   삭제할 노드에 자식이 하나면, 노드를 삭제하고 그 자식을 삭제된 노드가 있던 위치에 넣는다.

   삭제할 노드에 자식이 둘이면, 삭제된 노드를 후속자 노드로 대체한다.
   후속자 노드란 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.

   단, 후속자 노드에 오른쪽 자식이 있으면, 후속자를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.

   이진 트리 삭제의 효율성은 O(logN)이다.

   +) 정렬된 배열 삭제의 효율성인 O(N)에 비해 매우 좋다.

(5) 효율성 비교

- 배열 VS 연결 리스트

연산	배열	연결 리스트
읽기	O(1)	O(N)
검색	O(N)	O(N)
삽입	O(N)(끝에서 하면 O(1))	O(N)(앞에서 하면 O(1))
삭제	O(N)(끝에서 하면 O(1))	O(N)(앞에서 하면 O(1))

- 정렬된 배열 VS 이진 트리

연산	정렬된 배열	이진 트리
읽기	O(1)	O(N)
검색	O(logN)	O(logN)
삽입	O(N)	O(logN) (정렬된 데이터 삽입 시 O(N))
삭제	O(N)	O(logN)

(6) 이진 트리의 순회

자료 구조 순회란 자료 구조에서 모든 노드를 방문하는 과정을 말한다.
트리 순회의 효율성은 O(N)이다.

[ 예제 ]

'책 제목 리스트를 관리하는 애플리케이션'을 생성한다고 하자
다음과 같은 기능을 구현해야 한다

1. 프로그램이 책 제목을 알파벳 순으로 출력할 수 있어야 함
2. 프로그램이 리스트를 계속해서 바꿀 수 있어야 함
3. 사용자가 리스트에서 책 제목을 검색할 수 있어야 함

→ 리스트가 자주 바뀌지 않는다면, 정렬된 배열을 이용하는 것이 좋다 (삽입, 삭제가 자주 안 일어남, 검색은 빠름)

→ 그러나, 리스트가 수시로 바뀐다면, 이진 트리를 이용해야 한다 (삽입, 삭제가 자주 일어남)

→ 2번과 3번 기능은 앞서 배운 이진 트리의 검색, 삽입, 삭제 코드로 구현이 가능하다.

→ 1번 기능을 구현하기 위해서는 이진 트리의 모든 노드를 방문해야 한다. 이 경우에는 중위 순회를 이용했다.

pp.259
Python으로 구현된 코드 → JavaScript로 변환

🙋‍♀️ Q2. 코드는 매우 간단하지만 이것 역시 이해가 안 간다. 또한, 이진 트리 순회 중에서 이 책에서 다룬 것은 중위 순회 하나이다. 일단 이진 트리 삭제 코드부터 이해한 후 이진 트리 순회에 대해서도 추가로 더 공부할 것!

// 중위 순회 ❗ (왼쪽 )
function traverse_and_print(node) {
  if (node === null) {
    return;
  }
  traverse_and_print(node.left_child);
  console.log(node.value);
  traverse_and_print(node.right_child);
}

🙋‍♀️ 질문

1. 여기 바로가기 (이진 트리 삭제)

2. 여기 바로가기 (이진 트리 중위 순회)

✨ 내일 할 것

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

2. 책 계속 읽기