codingBear's Study Room

블로그 이전했습니다

Fri, 01 Apr 2022 06:38:37 GMT

아래 주소로 이전했습니다.

https://gdk01.tistory.com

티스토리 블로그

CSS 더 쉽게 하기! with Sass

Fri, 11 Mar 2022 05:19:36 GMT

이번 글은 아래 강의를 토대로 작성하였습니다. CS50's Web Programming lecture 0. HTML & CSS

들어가며

CSS에서 같은 값을 반복해서 입력해야 할 때 불편함을 겪는다. 물론 :root{}를 활용하여 자주 쓰이는 값을 저장해서 호출하는 식으로 처리할 수도 있으나 :root에 저장한 값을 일일이 불러와야 한다는 점에선 불편한 것은 매한가지이다. Sass를 활용하여 CSS를 작성하면 이런 번거로움을 덜 수 있다. 아래 내용을 보며 Sass에 대한 기본적인 지식을 익혀보자.

실전 활용법

설치하기(Windows 10 기준)

npm install sass

complile scss to css

Sass의 확장자는 scss이다. scss 자체로는 웹 브라우저에 읽힐 수 없기 때문에 css 파일로 변환해서 사용해야 한다. compile을 하려면 console 창에 아래와 같이 입력한다.

sass {filename}.scss:{filename}.css

위의 문장을 입력하면 scss에서 compile된 css가 생성된다. 새로 생성된 css 파일을 html 파일에 input하여 사용하면 된다. 허나 scss 파일에서 수정사항이 생기면 매번 compile을 해줘야 하는데 다음과 같이 --watch를 추가하면 scss 파일을 저장할 때마다 자동으로 수정사항이 css 파일에 반영되어 compile을 해야 하는 수고를 덜 수 있다.

sass --watch {filename}.scss:{filename}.css

1. 변수 활용하여 CSS 유지보수 쉽게 하기


    
      unordered item
      unordered item
      unordered item
    

    
      ordered item
      ordered item
      ordered item

위와 같은 html코드를 작성했을 때 ol과 ul에 각각 초록색을 부여한다고 치자. CSS로 색상을 입힌다면 아래와 같이 작성해야 한다.

ul {
  font-size: 14px;
  color: green;
}

ol {
  font-size: 18px;
  color: green;
}

물론 위와 같이 작성해도 전혀 문제될 것은 없다. 허나 코드 길이가 길어져 100개의 요소에 초록색을 부여해야 한다면? 복붙신공을 한다 쳐도 100번은 붙여 넣어야 한다. 더 큰 문제는 값을 수정하기가 까다롭다는 점이다. 위의 예제 코드에서 ul과 ol에 부여된 color값 green을 변수로 만든다면 보다 유지보수하기 쉬운 코드가 될 것이다. 아래는 Sass를 활용하여 green을 변수에 저장한 코드이다.

$color: green;

ul {
  font-size: 14px;
  color: $color;
}

ol {
  font-size: 18px;
  color: $color;
}

Sass에서 변수 선언을 할 땐 변수 앞에 $ 기호를 붙여준다. 작성한 scss 파일을 위에서 살펴본 대로 compile하고, 새로 생성된 css를 html 파일에 link 해주면 기존에 css로 스타일을 부여했을 때와 같은 결과물이 출력된다! 여기서 색상을 blue로 바꾸고 싶다면? 번거롭게 일일이 수정할 필요 없이 변수 $color의 값을 blue로 바꿔주기만 하면 된다.

$color: blue;

ul {
  font-size: 14px;
  color: $color;
}

ol {
  font-size: 18px;
  color: $color;
}

변경된 색상이 잘 반영됐음을 볼 수 있다.

2. nesting


    
      This is a paragraph inside the div.

      List inside the div:
      
        item one
        item two
        item three
      
    

    This is a paragraph outside the div.

    List outside the div:
    
      item one
      item two
      item three

위와 같이 작성된 html 코드가 있고 div 태그의 하위 속성 p와 ul에 각각 색상을 부여한다 하자. css로 색상을 부여한다면 아래와 같이 작성해야 할 것이다.

div {
  font-size: 18px;
}

div p {
  color: blue;
}

div ul {
  color: green;
}

위 코드를 scss로 간소화한다면 아래와 같다.

div {
    font-size: 18px;

    p {
        color: blue;
    }

    ul {
        color: green;
    }
}

따라서 div 태그 하위 요소에 속성을 부여해야 한다면 {} 안에 속성을 부여할 요소를 추가하기만 하면 된다.

inheritance

 
    This is a success message.

    This is a warning message.

    This is an error message.

위 예시처럼 대부분의 속성이 중복되는 요소를 관리할 때도 Sass로써 효율적으로 작성 가능하다.

%message {
    font-family: sans-serif;
    font-size: 18px;
    font-weight: bold;
    border: 1px solid black;
    padding: 20px;
    margin: 20px;
}

.success {
    @extend %message;
    background-color: green;
}

.warning {
    @extend %message;
    background-color: orange;
}

.error {
    @extend %message;
    background-color: red;
}

위처럼 각 요소별 중복되는 속성은 %message에 담고, @extend를 활용하여 앞서 저장한 %message 내 속성들을 불러와서 사용하면 된다.

우아한 테크코스 따라잡기_숫자 야구 게임 Part 1

Sat, 05 Mar 2022 05:18:47 GMT

들어가며

언젠가 도전해봐야지 하며 한참을 미루다 어제부터 착수한 작업! 바로 우아한 테크코스 프론트엔드 과정 프리 코스의 3주치 과제 따라만들기! 그 첫 번째 과제는 바로 숫자 야구 게임이다. 본 과제에서 구현해야 하는 기능 요구사항은 다음과 같다.

🎯 기능 요구사항

같은 수가 같은 자리에 있으면 스트라이크, 다른 자리에 있으면 볼, 같은 수가 전혀 없으면 낫싱이란 힌트를 얻고, 그 힌트를 이용해서 먼저 상대방(컴퓨터)의 수를 맞추면 승리한다.

예) 상대방(컴퓨터)의 수가 425일 때
- 123을 제시한 경우 : 1스트라이크
- 456을 제시한 경우 : 1볼 1스트라이크
- 789를 제시한 경우 : 낫싱
  - 위 숫자 야구게임에서 상대방의 역할을 컴퓨터가 한다. 컴퓨터는 1에서 9까지 서로 다른 임의의 수 3개를 선택한다. 게임 플레이어는 컴퓨터가 생각하고 있는 3개의 숫자를 입력하고, 컴퓨터는 입력한 숫자에 대한 결과를 출력한다.
  - 이 같은 과정을 반복해 컴퓨터가 선택한 3개의 숫자를 모두 맞히면 게임이 종료되고, 재시작 버튼이 노출된다.
  - 게임이 종료된 후 재시작 버튼을 클릭해 게임을 다시 시작할 수 있다.
  - 사용자가 잘못된 값을 입력한 경우 alert으로 에러 메시지를 보여주고, 다시 입력할 수 있게 한다.

💻 실행결과

사실 코드 구현 자체는 javascript를 조금이라도 만져 본 사람이라면 크게 어렵지 않으리라 생각한다. 다만 코드 작성 시에 염두에 두어야 하는 몇 가지 요구사항들이 까다로웠다. 아래는 우아한 테크코스 과제 작업 시 지켜야 할 사항들이다.

✅ 프로그래밍 요구사항

play(컴퓨터의 랜덤 값, 유저의 입력 값) 메서드를 만들어 게임을 진행한다.

play메서드는 String으로 결과값을 return 한다.
- 스트라이크와 볼이 같이 있는 경우 볼을 먼저쓰고, 스트라이크를 쓴다.
index.js에서 아래의 function 또는 class 형태를 활용한다.

export default function BaseballGame() {
  this.play = function (computerInputNumbers, userInputNumbers) {
    return "결과 값 String";
  };
}

export default class BaseballGame {
  play(computerInputNumbers, userInputNumbers) {
    return "결과 값 String";
  }
}

// 예시
play(123, 456); // '낫싱'
play(123, 345); // '1볼'
play(123, 432); // '2볼'
play(123, 312); // '3볼'
play(123, 145); // '1스트라이크'
play(123, 134); // '1볼 1스트라이크'
play(123, 132); // '2볼 1스트라이크'
play(123, 124); // '2스트라이크'

공통 요구사항

외부 라이브러리(jQuery, Lodash 등)를 사용하지 않고, 순수 Vanilla JS로만 구현한다.

자바스크립트 코드 컨벤션을 지키면서 프로그래밍 한다.
indent(인덴트, 들여쓰기) depth를 3이 넘지 않도록 구현한다. 2까지만 허용한다.
- 예를 들어 while문 안에 if문이 있으면 들여쓰기는 2이다.
- 힌트: indent(인덴트, 들여쓰기) depth를 줄이는 좋은 방법은 함수(또는 메소드)를 분리하면 된다.
함수(또는 메소드)가 한 가지 일만 하도록 최대한 작게 만들어라.
변수 선언시 var 를 사용하지 않는다. const 와 let 을 사용한다.
- const
- let
import 문을 이용해 스크립트를 모듈화하고 불러올 수 있게 만든다.
- https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Statements/import
함수(또는 메소드)의 길이가 15라인을 넘어가지 않도록 구현한다.
- 함수(또는 메소드)가 한 가지 일만 잘 하도록 구현한다.

📝 과제 진행 요구사항

미션은 javascript-baseball-precourse 저장소를 Fork/Clone해 시작한다.

기능을 구현하기 전에 javascript-baseball-precourse/docs/README.md 파일에 구현할 기능 목록을 정리해 추가한다.
Git의 커밋 단위는 앞 단계에서 README.md 파일에 정리한 기능 목록 단위로 추가한다.
- AngularJS Commit Message Conventions 참고해 commit log를 남긴다.

위의 요구사항들을 받아들고 난감했다. 여태껏 함수의 깊이라든지, Module화라든지, class니 function이니, commit message니 전혀 신경써본 적이 없었기에 이걸 다 지키면서 만들어낼 수 있을까 막막하기만 했다. 그렇게 각종 문서를 뒤지며 고민하기를 1시간째... 일단 기능부터 구현하고, 추후에 요구사항에 맞춰 수정하기로 가닥을 잡았다! 행동으로 옮기지 않으면 아무 일도 일어나지 않으니까! 아래는 내가 작성한 코드와 기능 구현 결과물이다.

My Solution

# 📁 디렉토리 구조
├─ src
│  ├─ components
│  │  ├─ compareNumbers.js
│  │  ├─ createCPUNumbers.js
│  │  ├─ validateUserNumbers.js
│  ├─ index.js

# index.js

import { compareNumbers } from './components/compareNumbers.js';

const checkButton = document.querySelector('#submit');
export let restartButton = document.querySelector('#game-restart-button');
checkButton.addEventListener('click', handleCheckButtonFunction);
restartButton.style.display = 'none';

function handleCheckButtonFunction(e) {
  e.preventDefault();
  compareNumbers();
}

# compareNumbers.js

import { createCPUNumbers } from './createCPUNumbers.js';
import { validateUserNumbers } from './validateUserNumbers.js';
import { restartButton } from '../index.js';

const CPUNumbers = createCPUNumbers();

export function compareNumbers() {
  let userNumbers = validateUserNumbers();

  let strike = 0;
  let ball = 0;

  if (!userNumbers) {
    return;
  } else {
    userNumbers.forEach((value, index) => {
      if (value === CPUNumbers[index]) strike++;
      else if (CPUNumbers.includes(value)) ball++;
    });
  }

  const resultMessage = document.querySelector('#result');
  if (strike === 0 && ball === 0) {
    resultMessage.innerText = '낫싱';
  } else if (strike > 0 && ball > 0) {
    resultMessage.innerText = `${ball}볼 ${strike}스트라이크`;
  } else if (ball > 0) {
    resultMessage.innerText = `${ball}볼`;
  } else if (strike > 0) {
    resultMessage.innerText = `${strike}스트라이크`;
  }

  if (strike === 3) {
    resultMessage.innerText = `🎉정답을 맞히셨습니다🎉

    게임을 새로 시작하시겠습니까?

    `;

    restartButton.style.display = 'block';
  }

  restartButton.addEventListener('click', () => location.reload());
}

# createCPUNumbers.js

export function createCPUNumbers() {
  let CPUNumbersArray = [];

  while (CPUNumbersArray.length <= 2) {
    let randomCPUNums = MissionUtils.Random.pickNumberInRange(1, 9);
    if (CPUNumbersArray.indexOf(randomCPUNums) < 0) {
      CPUNumbersArray.push(randomCPUNums);
    }
  }

  const toStringCPUNumbers = CPUNumbersArray.map((val) => String(val));
  return toStringCPUNumbers;
}

# validateUserNumbers.js

export function validateUserNumbers() {
  const userInput = document.querySelector('#user-input');
  const userNumbers = userInput.value;
  const numberedUserNumbers = +userNumbers;

  if (
    userNumbers.length > 3 ||
    userNumbers.length < 3 ||
    userNumbers.includes(0) ||
    userNumbers.includes(' ') ||
    userNumbers === '' ||
    isNaN(numberedUserNumbers) === true
  ) {
    alert('숫자를 조건에 맞게 다시 입력해주세요!');
    return;
  }

  const userNumberMap = {};
  for (let number of userNumbers)
    userNumberMap[number] = userNumberMap[number] + 1 || 1;

  for (let count in userNumberMap) {
    if (userNumberMap[count] > 1) {
      alert('숫자를 조건에 맞게 다시 입력해주세요!');
      return;
    }
  }
  const splitedUserNumbers = userNumbers.split('');
  return splitedUserNumbers;
}

실행 결과

일단 기능은 완벽하게 구현했다.(고 생각한다...?!) 하지만 앞으로 할 일이 많이 남았다.

향후 계획 1. 기능 단위로 module화하기 2. 요구사항 지키며 코드 수정 3. 다른 사람들이 작성한 코드 참고하며 왜 그런 식으로 작성했을지 한 줄 한 줄 들여다보기 4. class, function, OOP, MVC 등의 개념에 대해 공부하고 실제 코드에 녹여보기

하노이의 탑(Towers of Hanoi)

Thu, 03 Mar 2022 09:55:43 GMT

References

이번 글은 아래 자료들을 참고하여 작성하였습니다.

들어가며

하노이의 탑을 풀기 위해서는 우선 재귀 함수에 대한 이해가 필요하다. 재귀 함수는 javascript의 일반적인 동작 방식인 명령형(Imperative)이 아니라 선언형(declarative)으로 동작한다. 따라서 재귀 함수를 온전히 이해하려면 declarative programming에 대한 감각이 필요하다.

재귀 함수를 짤 때 중요한 것은 두 가지이다.

종료 조건
문제 정의

그럼 위 두 가지를 고려하여 하노이의 탑의 pseudo code를 나열해보자.

종료조건 1.원반이 하나 남으면 끝
문제 정의 선언
1. N개의 원반을 옮기기 위해서는 N-1개의 원반을 temp기둥으로 옮겨야 함.
2. N번째 원반을 목적지 기둥으로 옮긴다.
3. temp기둥에 있는 N-1개의 원반을 목적지 기둥으로 옮긴다.

위의 pseudo code를 바탕으로 코드를 짜면 아래와 같다.

Towers of Hanoi

const route = [];

function hanoi(num, from, to, temp) {
  //원판이 한 개일 때에는 바로 옮기면 됨.
  //종료조건
  if (num === 1) {
    route.push([from, to]);
    return NaN;
  }

  hanoi(num - 1, from, temp, to); // n - 1개의 원반을 temp기둥에 옮김. 따라서 to -> temp, temp -> to 로 변경
  route.push([from, to]); // n번째 원반을 from기둥에서 to기둥으로 옮김. n번째 원반을 막고 있던 n - 1개의 원반을 temp로 다 옮겼기 때문에 가능.
  hanoi(num - 1, temp, to, from); // temp기둥에 있던 n - 1개의 원반을 to기둥으로 옮김. temp -> from, from -> temp 로 변경.
}
hanoi(3, "A", "B", "C");
console.log(route); 
/*
[
 [ 'A', 'B' ],
 [ 'A', 'C' ],
 [ 'B', 'C' ],
 [ 'A', 'B' ],
 [ 'C', 'A' ],
 [ 'C', 'B' ],
 [ 'A', 'B' ]
]
*/
console.log(route.length); // 7

위 코드는 아래와 같은 순서로 실행된다.

실행 과정(7단계)

hanoi(3, A, B, C); // 4. push A, B: 3번 원반 from(A)에서 to(B)로 이동
    hanoi(2, A, C, B) // 2. push A, C: 2번 원반 from(A)에서 temp(C)로 이동
        hanoi(1, A, B, C) // 1. push A, B: 1번 원반 from(A)에서 to(B)로 이동
        hanoi(1, B, C, A) // 3. push B, C: 1번 원반 to(B)에서 temp(C)로 옮겨서 2번 원반 위에 쌓기
    hanoi(2, C, B, A)  // 6. push C, B: 2번 원반 temp(C)에서  to(B)로 이동
        hanoi(1, C, A, B) // 5. push C, A: 2번 위에 있던 1번 원반 temp(C)에서 from(A)로 이동
        hanoi(1, A, B, C) // 7. push A, B: 1번 원반 from(A)에서 to(B)로 이동하면서 완성.

위 실행 순서를 그림으로 나타내면 다음과 같다.

함께 보기

recursive algorithms

재귀 알고리즘(Recursive Algorithms)

Thu, 03 Mar 2022 05:53:02 GMT

References

이번 글은 아래 자료들을 참고하여 작성하였습니다. Recursive Algorithms on Khan Academy Think Like a Programmer

위 인형은 러시아의 전통 인형 마트료시카이다. 큰 인형을 열면 그보다 작은 인형이 하나 나오고 다시 그 인형을 열면 또 작은 인형이 나오고를 반복하며 점점 크기가 작아진다. 재귀 함수도 이와 마찬가지로 주어진 조건을 충족할 때까지 함수 자신의 크기를 줄여가다 조건을 충족하면 결과값을 반환하는 함수이다.

배열 내 값 모두 더하기

// solution 1.
const numArr1 = [1, 2, 3, 4, 5];

function iterativeArraySum(array, size) {
  let sum = 0;

  for (let i = 0; i < size; ++i) {
    sum += array[i];
  }
  return sum;
}

console.log(iterativeArraySum(numArr1, numArr1.length)); // 15

위 코드는 주어진 배열의 길이만큼 for문으로 주어진 배열을 탐색하여 배열 내 모든 값의 합을 반환하는 함수이다. 이 함수를 살펴보면 배열 index 0부터 끝까지 탐색하며 값을 하나하나 더해나가는 것을 알 수 있다. 일정 조건 하에 반복 작업을 수행하는 함수라면, 반복문 대신 재귀 함수로 바꿔 쓸 수 있다.

위 함수를 완전한 재귀 함수로 바꿔 쓰기 전에 위 반복문은 그대로 놔둔 채 다른 기능을 수행하는 함수를 추가하여 보다 재귀 함수와 가까워지게 작성해보자.

// solution 2.
function iterativeArraySum(array, size) {
  let sum = 0;

  for (let i = 0; i < size; ++i) {
    sum += array[i];
  }
  return sum;
}

function arraySumDelegate(array, size) {
  if (size === 0) return 0;
  // the last number in the array is stored in this local variable
  const lastNum = array[size - 1];
  // the sum of all the other values in the array is computed and this result is stored in this local variable
  const allButLastSum = iterativeArraySum(array, size - 1);
  return lastNum + allButLastSum;
}

console.log(arraySumDelegate(numArr1, numArr1.length)); // 15

주어진 배열의 길이가 0이라면 결과값 0반환.
주어진 배열의 길이가 0보다 크다면 반복문을 호출하여 size의 값이 0이 될 때까지 배열값 더하기 작업 수행

위의 함수를 재귀 함수로 바꾸기 위해서는 iterativeArraySum으로 호출하는 반복문을 지금 실행 중인 함수로 치환하면 된다. 작성하면 아래와 같이 된다.

// solution 3.
const numArr1 = [1, 2, 3, 4, 5];

function arraySumRecursive(array, size) {
  if (size === 0) return 0;

  const lastNum = array[size - 1];
  const allButLastSum = arraySumRecursive(array, size - 1);

  return lastNum + allButLastSum;
}

console.log(arraySumDelegate(numArr1, numArr1.length)); // 15

위의 함수를 실행하게 되면 size의 값이 0이 될때까지 해당 작업을 반복하며 배열 내 값을 모두 더한다. solution 2.에서는 allButLastSum에 해당하는 값으로 다른 반복문을 불러왔다면, 여기서는 자기 자신을 호출함으로써 재귀적 작업을 수행한다.

Recursive Algorithms 활용 예들

The Factorial Function

const factorial = function (n) {
  // base case:
  if (n === 0) {
    return 1;
  }

  return n * factorial(n - 1);
};

console.log(factorial(5)); // 120

위의 함수는 1부터 n까지 자연수의 곱을 계산하는 함수이다. n-1을 설정하여 함수 factorial이 재귀적으로 쓰인 것을 볼 수 있다.

determine palindrome

const firstCharacter = function (str) {
  return str.slice(0, 1);
};

// Returns the last character of a string str
const lastCharacter = function (str) {
  return str.slice(-1);
};

// Returns the string that results from removing the first
//  and last characters from str
const middleCharacters = function (str) {
  return str.slice(1, -1);
};

const isPalindrome = function (str) {
  // base case #1
  if (str.length <= 1) return true;
  // base case #2
  if (firstCharacter(str) === lastCharacter(str))
    return isPalindrome(middleCharacters(str));
  // recursive case
  return false;
};

const checkPalindrome = function (str) {
  console.log("Is this word a palindrome? " + str);
  console.log(isPalindrome(str));
};

checkPalindrome(""); // true
checkPalindrome("a"); // true
checkPalindrome("motor"); // false
checkPalindrome("rotor"); // true

위의 코드는 주어진 문자열이 palindrome인지 판별하는 함수이다. 입력값이 없거나 하나인 경우 palindrome이기 때문에 true를 반환한다. 입력값의 길이가 2 이상인 경우 첫째값과 마지막 값을 잘라내어 일치 여부를 확인하고 나머지 중간값을 반환, 다시 반환된 중간값의 첫째값과 마지막값의 일치 여부를 확인하는 작업을 반복한다. 작업을 마친 후 palindrome이라면 true, 아니라면 false를 반환한다.

Fibonacci Series

function fib(n) {
  if (n < 2) {
    return n;
  }

  return fib(n - 1) + fib(n - 2);
}

console.log(fib(9)); // 34

위 함수는 피보나치 수열을 재귀 함수로 작성한 것이다. 함수를 실행하면 앞의 수와 앞앞의 수를 더하는 작업을 반복하여 입력값 n번째 위치하는 피보나치의 수를 구한다.

함께 보기

Fibonacci Palindromes

퀵 정렬(Quick Sort)

Wed, 02 Mar 2022 07:38:05 GMT

References

이번 글은 아래 자료를 참고하여 작성하였습니다. Insertion Sort on Khan Academy

const partition = function (array, startIdx, lastIdx) {
  let partitonedArr = array,
    partitonedArrStartIdx = startIdx,
    partitonedArrLastIdx = lastIdx;

  const createPartitionedArr = function (
    partitonedArr,
    partitonedArrStartIdx,
    partitonedArrLastIdx
  ) {
    let partitonedRightArrStartIdx = partitonedArr[partitonedArrStartIdx];

    partitonedArr[partitonedArrStartIdx] = partitonedArr[partitonedArrLastIdx];
    partitonedArr[partitonedArrLastIdx] = partitonedRightArrStartIdx;
  };

  let partitonedLeftArrStartIdx = partitonedArrStartIdx;
  for (let s = partitonedArrStartIdx; s < partitonedArrLastIdx; s++) {
    if (partitonedArr[s] <= partitonedArr[partitonedArrLastIdx]) {
      createPartitionedArr(partitonedArr, s, partitonedLeftArrStartIdx);
      partitonedLeftArrStartIdx++;
    }
  }

  createPartitionedArr(
    partitonedArr,
    partitonedArrLastIdx,
    partitonedLeftArrStartIdx
  );

  return partitonedLeftArrStartIdx;
};

const quickSort = function (array, startIdx, lastIdx) {
  if (startIdx < lastIdx) {
    let midIdx = partition(array, startIdx, lastIdx);
    quickSort(array, startIdx, midIdx - 1);
    quickSort(array, midIdx + 1, lastIdx);
  }
};

const array = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6];
quickSort(array, 0, array.length - 1);
console.log(array); // [ 2, 3, 5, 6, 7, 9, 10, 11, 12, 14 ]

quick sort는 배열 정렬의 기준값이 되는 pivot을 기준으로 pivot보다 작은 값을 왼쪽에, 큰 값을 오른쪽에 정렬하는 알고리즘이다. 이때 pivot은 배열의 가장 마지막 값이다. 위 그림에서 pivot의 값은 6인데, 두 번째 줄을 보면 6보다 작은 값은 왼쪽 배열에, 큰 값은 오른쪽 배열에 담겼다. 6을 기준으로 나눈 두 배열에서 다시 끝 값을 pivot으로 삼아 똑같은 방식으로 각 배열의 값을 정렬한다. merge sort와 같이 divide-and-conquer 방식으로 작동한다. merge sort에서는 combine 단계에서 정렬이 이뤄지는 반면, quick sort에서는 divide 단계에서 모든 작업이 이뤄진다.

삽입 정렬(Insertion Sort)

Wed, 02 Mar 2022 06:27:35 GMT

References

이번 글은 아래 자료를 참고하여 작성하였습니다. Insertion Sort on Khan Academy

Insertion Sort

function insert(array, rightIndex, value) {
  // let temp;
  // for (let i = rightIndex; i >= 0; --i) {
  //   if (value < array[i]) {
  //     temp = array[i];
  //     array[i] = value;
  //     array[i + 1] = temp;
  //   }
  // }

  for (let i = rightIndex; i >= 0 && array[i] > value; --i) {
    array[i + 1] = array[i];
    array[i] = value;
  }
}

function insertionSort(array) {
  for (let i = 1; i < array.length; ++i) {
    insert(array, i - 1, array[i]);
  }
  return array;
}

const array = [3, 5, 7, 11, 13, 2, 9, 6];
console.log(insertionSort(array)); // [2, 3, 5, 6, 7, 9, 11, 13]

insertionSort를 통해 주어진 배열을 입력값으로 탐색하면서 rightIndex 범위 내의 값들 중 입력값보다 탐색값이 크다면 탐색값의 index를 1만큼 증가시키고, array[i]에 있던 값을 value로 바꾼다. 이 작업을 반복하면 주어진 배열이 오름차순으로 정렬된다.

합병 정렬(Merge Sort)

Wed, 02 Mar 2022 01:33:26 GMT

References

이번 글은 아래 자료들을 참고하여 작성하였습니다. Section 33. Ack, MergeSort! Merge Sort on Khan Academy

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  }

  const center = Math.floor(arr.length / 2);
  const left = arr.slice(0, center);
  const right = arr.slice(center);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const results = [];

  while (left.length && right.length) {
    if (left[0] < right[0]) {
      results.push(left.shift());
    } else {
      results.push(right.shift());
    }
  }

  return [...results, ...left, ...right];
}

위 그림에서 보듯 재귀함수 mergeSort Function을 거쳐서 주어진 배열의 길이가 1이 될 때까지 left, right로 쪼갠다. 쪼개진 값들을 merge Function을 거치면서 배열 left와 배열 right의 첫 값을 비교하여 작은 값을 왼쪽으로 몰고, 큰 값을 오른쪽으로 보낸다. 위 과정을 모두 거치면 주어진 배열이 오름차순으로 정렬된다.

선택 정렬(Selection Sort)

Tue, 01 Mar 2022 01:39:31 GMT

References

이번 글은 아래 자료들을 참고하여 작성하였습니다. Section 32. Sort By Selection on Udemy Selection Sort on Khan Academy

Selection Sort

// solution 1.
function selectionSort(arr) {
  for (let i = 0; i < arr.length; ++i) {
    let indexOfMin = i;
    // for문 j 돌면서 arr[j]가 arr[indexOfMin]보다 작으면 indexOfMin을 j로 치환한다. 즉, 현재값과 배열 내 값들을 비교하며, 현재 값보다 작은 값의 위치를 기록하는 것이다.
    for (let j = i + 1; j < arr.length; ++j) {
      if (arr[j] < arr[indexOfMin]) {
        indexOfMin = j;
      }
    }
    // 현재 값보다 작은 값이 배열 내 존재했다면 indexOfMin과 i는 같지 않을 것이고 따라서 큰 값인 현재 값과 작은 값의 위치를 서로 바꿔준다.
    if (indexOfMin !== i) {
      let lesser = arr[indexOfMin];
      arr[indexOfMin] = arr[i];
      arr[i] = lesser;
    }
  }

  return arr;
}

// solution 2.
const swap = function (array, firstIndex, secondIndex) {
  let temp = array[firstIndex];
  array[firstIndex] = array[secondIndex];
  array[secondIndex] = temp;
};

const indexOfMinimum = function (array, startIndex) {
  let minValue = array[startIndex];
  let minIndex = startIndex;

  for (let i = minIndex + 1; i < array.length; ++i) {
    if (array[i] < minValue) {
      minIndex = i;
      minValue = array[i];
    }
  }

  return minIndex;
};

const selectionSort = function (array) {
  let temp;

  for (let i = 0; i < array.length; ++i) {
    temp = indexOfMinimum(array, i);
    swap(array, i, temp);
  }
};

두 solution 모두 주어진 배열을 for문으로 탐색하면서 값들을 하나하나 비교하여 작은 값을 임시 변수에 담고, 더 작은 값이 나오면 임시 변수의 값을 치환하는 식으로 작동하는 코드이다.

거품 정렬(Bubble Sort)

Mon, 28 Feb 2022 22:19:54 GMT

References

아래 링크의 강의 중 Section 31. Sorting with BubbleSort의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Bubble Sort

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; ++i) {
    for (let j = 0; j < arr.length - 1 - i; ++j) {
      if (arr[j] > arr[j + 1]) {
        const lesser = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = lesser;
      }
    }
  }

  return arr;
}

Bubble Sort는 주어진 배열 전체를 탐색하며 인접한 두 값의 대소를 비교하여 큰 값을 뒤로 보내고 작은 값을 앞으로 보내 배열 내 값들을 정렬하는 방식이다.

이진 탐색 트리 유효성 검사(Validating a Binary Search Tree)

Mon, 28 Feb 2022 07:41:44 GMT

References

아래 링크의 강의 중 Section 28. Validating a Binary Search Tree의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Validating a Binary Search Tree

function validate(node, min = null, max = null) {
  if (max !== null && node.data > max) {
    return false;
  }

  if (min !== null && node.data < min) {
    return false;
  }

  if (node.left && !validate(node.left, min, node.data)) {
    return false;
  }

  if (node.right && !validate(node.right, node.data, max)) {
    return false;
  }

  return true;
}

recursive function과 if문을 거치면서 입력값이 root값을 기준으로 작다면 왼쪽에 위치하고, 크다면 오른쪽에 놓이게 한다. 여기서 왼쪽 트리를 탐색할 때는 탐색 중인 왼쪽 트리의 값이 max값에 할당되어 그보다 작은 값만 왼쪽 트리에 저장되게끔 제한을 하고, 반대로 오른쪽은 min값이 바뀌어 탐색 중인 오른쪽 트리의 값보다 큰 값만이 오른쪽에 저장되게끔 한다.

이진 탐색 트리(Binary Search Trees)

Mon, 28 Feb 2022 06:32:57 GMT

References

아래 링크의 강의 중 Section 27. My Best Friend, Binary Search Trees의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Binary Search Trees

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  insert(data) {
    // 입력값 data가 this.data보다 작고 this.left에 값이 이미 할당되어 있다면 this.left에 입력값 data을 넣고, this.left가 없는데 입력값 data가 this.data보다 작다면 this.left에 새로운 node를 할당한다. 입력값의 대소비교만을 빼고 this.right의 경우도 마찬가지이다.
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data) {
      this.left = new Node(data);
    } else if (data > this.data && this.right) {
      this.right.insert(data);
    } else if (data > this.data) {
      this.right = new Node(data);
    }
  }

  contains(data) {
    if (this.data === data) {
      return this;
    }
    // 입력값 data가 현재값 this.data보다 크고 this.right에 node가 존재한다면?
    if (this.data < data && this.right) {
      return this.right.contains(data);
    } else if (this.data > data && this.left) {
      return this.left.contains(data);
    }

    return null;
  }
}

binary search trees란 root값을 기준으로 새로 입력하는 값이 작으면 왼쪽, 크다면 오른쪽으로 정렬해놓은 트리이다.

트리의 너비(Tree Width)

Mon, 28 Feb 2022 03:14:52 GMT

References

아래 링크의 강의 중 Section 26. Tree Width with Level Width의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Tree Width

function levelWidth(root) {
  const arr = [root, "s"];
  const widths = [0];

  while (arr.length > 1) {
    const node = arr.shift();

    if (node === "s") {
      widths.push(0);
      arr.push("s");
    } else {
      arr.push(...node.children);
      widths[widths.length - 1]++;
    }
  }

  return widths;
}

각 단계에 포함된 값들을 arr에 넣어서 배열 arr의 길이를 width로서 저장하고, 중간에 stopper 역할을 하는 문자 s를 넣어 탐색 작업 중 문자 s와 만나면 다음 단계로 넘어가게끔 한다.

트리(Tree)

Mon, 28 Feb 2022 02:40:58 GMT

References

아래 링크의 강의 중 Section 25. Building a Tree의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Node

class Node {
  constructor(data) {
    this.data = data;
    this.children = [];
  }
  // node의 입력값 data를 배열로 children에 push
  add(data) {
    const node = new Node(data);
    this.children.push(node);
  }
 // filter() method로써 특정값을 제외한 배열을 반환
  remove(data) {   
    this.children = this.children.filter((node) => {
      return node.data !== data;
    });
  }
}

Tree

class Tree {
  constructor() {
    this.root = null;
  }

  traverseBF(fn) {
    const arr = [this.root];
    while (arr.length) {
      const node = arr.shift();
      // 그냥 node.children을 push하면 array로 들어가서 nested array 되기 때문에 하나씩 꺼내어 push
      arr.push(...node.children);
      //   for (let child of node.children) {
      //     arr.push(child);
      //   }
      fn(node);
    }
  }

  traverseDF(fn) {
    const arr = [this.root];
    while (arr.length) {
      const node = arr.shift();

      arr.unshift(...node.children);
      fn(node);
    }
  }
}

너비 탐색(breadth first search)

위 그림에서 볼 수 있듯 너비 탐색(breadth first search)에서는 linked list의 맨 상위 단계에서 맨 하위 단계로 내려가면서, 각 단계별 첫 값에서 끝 값까지를 탐색한다.

깊이 탐색(depth first search)

위 그림에서 볼 수 있듯 깊이 탐색(depth first search)의 경우 linked list의 맨 상위 단계에서 맨 하위 단계로 내려가면서 각 단계의 맨 첫 값에 하위값이 있다면 그 하위값들부터 우선 탐색을 하고, 다시 상위 단계로 돌아와 하위값들을 탐색하는 과정을 반복한다.

Entire Code

class Node {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  add(data) {
    const node = new Node(data);
    this.children.push(node);
  }

  remove(data) {
    this.children = this.children.filter((node) => {
      return node.data !== data;
    });
  }
}

class Tree {
  constructor() {
    this.root = null;
  }

  traverseBF(fn) {
    const arr = [this.root];
    while (arr.length) {
      const node = arr.shift();

      arr.push(...node.children);
      //   for (let child of node.children) {
      //     arr.push(child);
      //   }
      fn(node);
    }
  }

  traverseDF(fn) {
    const arr = [this.root];
    while (arr.length) {
      const node = arr.shift();

      arr.unshift(...node.children);
      fn(node);
    }
  }
}

끝에서부터 노드 세기(From the Tail)

Sat, 26 Feb 2022 00:41:02 GMT

References

아래 링크의 강의 중 Section 24. Step Back From the Tail의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Solution

function fromLast(list, n) {
  let slow = list.getFirst();
  let fast = list.getFirst();

  while (n > 0) {
    fast = fast.next;
    n--;
  }

  while (fast.next) {
    slow = slow.next;
    fast = fast.next;
  }

  return slow;
}

눈여겨봐야 할 부분은 두 개의 while문의 기능이다.

첫 번째 while문

n이 0보다 클 동안 while문을 돌면서 변수 fast를 한 칸씩 앞으로 전진시킨다. 결과적으로 변수 fast에 할당된 node의 위치는 변수 slow에 할당된 node보다 n만큼 앞서게 된다.

두 번째 while문

fast.next가 true인 동안 변수 slow와 fast 한 칸씩 전진시킨다. fast.next의 값이 null이 되는 지점이 곧 tail을 뜻하므로 이 때의 slow는 곧tail에서 n만큼 떨어진 node와 같다.

순환 리스트(Circular List)

Fri, 25 Feb 2022 23:30:12 GMT

References

아래 링크의 강의 중 Section 23. Circular Lists?의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Solution

function circular(list) {
  let slow = list.getFirst(); // = list.head;
  let fast = list.getFirst();

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}

// --- Examples
//   const l = new List();
//   const a = new Node('a');
//   const b = new Node('b');
//   const c = new Node('c');
//   l.head = a;
//   a.next = b;
//   b.next = c;
//   c.next = b;
//   circular(l) // true

이전에 작성한 중간 노드 찾기와 코드 구성이 유사하다. slow와 fast 변수가 각각 linked list를 탐색하다가 두 값이 모두 똑같은 node를 가리키게 되면 true를 반환하고, 조건을 만족하지 못하면 false를 반환하게 된다.

중간 노드 찾기(Find the Middle Node)

Fri, 25 Feb 2022 14:00:02 GMT

References

아래 링크의 강의 중 Section 22. Find the Midpoint의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Solution

function midpoint(list) {
  let slow = list.getFirst();
  let fast = list.getFirst();

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
}

linked list를 한 칸씩 탐색하는 변수 slow와 두 칸씩 탐색하는 변수 fast를 각각 선언한다. fast로 탐색을 하다 더 이상 탐색값이 없다면(null) while문을 멈추고 linked list의 중간값인 slow를 반환한다.

연결 리스트(Linked Lists)

Fri, 25 Feb 2022 12:08:53 GMT

References

아래 링크의 강의 중 Section 21. Linked Lists의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Solution

class Node {
  // node에다 새로운 instance 생설할 때마다 constructor가 자동으로 실행됨.
  // argument next의 기본값은 null로 설정. tail node에는 next가 없기 때문.
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  insertFirst(data) {
    // 새로이 node를 insert하게 되면 head에 할당되어 있던 기존 값은 next에 할당되고 새 값이 head로 치환됨.
    // this.head = new Node(data, this.head);
    this.insertAt(data, 0);
  }

  insertLast(data) {
    // const last = this.getLast();

    // if (last) {
    //   // There are some existing nodes in our chain
    //   last.next = new Node(data);
    // } else {
    //   // The chain is empty
    //   this.head = new Node(data);
    // }
    this.insertAt(data, this.size());
  }

  size() {
    let counter = 0;
    let node = this.head;

    while (node) {
      counter++;
      node = node.next;
    }

    return counter;
  }

  getFirst() {
    // return this.head;
    return this.getAt(0);
  }

  getLast() {
    // if (!this.head) {
    //   return null;
    // }

    // let node = this.head;
    // // this.head를 while문으로써 한 칸씩 옮겨가며 node.next가 없을 때까지 탐색
    // while (node) {
    //   // next가 없다면 현재 탐색값인 node 반환.
    //   if (!node.next) {
    //     return node;
    //   }
    //   // next가 있다면 node를 node.next로 치환.
    //   node = node.next;
    // }
    return this.getAt(this.size() - 1);
  }

  clear() {
    this.head = null;
  }

  removeFirst() {
    // if (!this.head) {
    //   return;
    // }

    // this.head = this.head.next;
    this.removeAt(0);
  }

  removeLast() {
    // // 아무 node도 없다면?
    // if (!this.head) {
    //   return;
    // }
    // // node가 하나밖에 없다면?(next가 false라면?)
    // if (!this.head.next) {
    //   this.head = null;
    //   return;
    // }

    // let previous = this.head;
    // let node = this.head.next;
    // // next가 존재하는 동안 while 돌리기
    // while (node.next) {
    //   previous = node;
    //   node = node.next;
    // }
    // // while 다 돌고 나면 마지막 값 null로 만들어 삭제
    // previous.next = null;
    this.removeAt(this.size() - 1);
  }

  getAt(index) {
    let counter = 0;
    let node = this.head;

    while (node) {
      if (counter === index) {
        return node;
      }

      counter++;
      node = node.next;
    }

    return null;
  }

  removeAt(index) {
    if (!this.head) {
      return;
    }

    if (index === 0) {
      this.head = this.head.next;
      return;
    }

    const previous = this.getAt(index - 1);

    if (!previous || !previous.next) {
      return;
    }

    previous.next = previous.next.next;
  }

  insertAt(data, index) {
    if (!this.head) {
      this.head = new Node(data);
      return;
    }
    // index 0에 insert할 경우 현재 head(this.head)를 next에 할당하고 this.head의 값으로 insert 값을 치환.
    if (index === 0) {
      this.head = new Node(data, this.head);
      return;
    }

    const previous = this.getAt(index - 1) || this.getLast();
    const node = new Node(data, previous.next);
    previous.next = node;
  }

  forEach(fn) {
    let node = this.head;
    let counter = 0;

    while (node) {
      fn(node, counter);
      node = node.next;
      counter++;
    }
  }

  *[Symbol.iterator]() {
    let node = this.head;

    while (node) {
      yield node;
      node = node.next;
    }
  }
}

module.exports = { Node, LinkedList };

Node

Head & Tail

linked list에 속한 node는 기본적으로 reference를 갖는다. 이 node들 중 마지막 값에 해당하여 reference를 갖지 않는 것이 바로 tail이다. node 안의 data에는 유효한 값이라면 type을 구분하지 않고 저장할 수 있다. linked list class 내에 insert, remove, get 등 다양한 method를 작성하여 linked list 내의 node를 자유롭게 편집할 수 있다. linked list는 단 한 개의 head property만 받는다. 즉, 첫 번째 node만을 인식하고, linked list 안에 현재 node가 몇 개인지, 어떤 data를 담고 있는지 전혀 신경 쓰지 않는다. 따라서 특정한 data를 얻기 위해서는 linked list 전체를 탐색해야 한다.

스택으로 큐 만들기(Create Queue with Stacks)

Thu, 24 Feb 2022 06:44:56 GMT

References

아래 링크의 강의 중 Section 20. Two Become One의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Solution

const Stack = require("./stack");

class Queue {
  // whenever you create an instance of a queue, you will automatically generate two stacks and assign it to this queue class.
  constructor() {
    this.first = new Stack();
    this.second = new Stack();
  }

  add(record) {
    this.first.push(record);
  }

  remove() {
    while (this.first.peek()) {
      this.second.push(this.first.pop());
    }

    const record = this.second.pop();

    while (this.second.peek()) {
      this.first.push(this.second.pop());
    }

    return record;
  }

  peek() {
    while (this.first.peek()) {
      this.second.push(this.first.pop());
    }

    const record = this.second.peek();

    while (this.second.peek()) {
      this.first.push(this.second.pop());
    }

    return record;
  }
}

module.exports = Queue;

기본적인 작동원리는 위 그림과 같다. 선입선출(FIFO)의 원리를 stack에도 적용한다 보면 된다.

함께 보기

큐 큐 합치기 스택

스택(Stacks)

Thu, 24 Feb 2022 06:05:42 GMT

References

아래 링크의 강의 중 Section 19. Stack 'Em Up With Stacks의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Solution

class Stack {
  constructor() {
    this.data = [];
  }

  push(record) {
    this.data.push(record);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }
}
// const s = new Stack();
// s.push(1);
// s.push(2);
// s.pop(); // returns 2
// s.pop(); // returns 1

stack 역시 data를 저장하는 방식 중의 하나이다. 이전에 살펴본 Queue와 차이점이 있다면 선입후출(FILO) 구조라는 것이다. 위 그림에서 보듯 들어오기는 A가 먼저 들어오고 나가는 것은 B가 먼저 나간다. push() method로 이전 값 뒤에 새로운 값을 input하고, pop() method로 가장 최근에 들어온 값을 output하는 구조이다.

함께 보기

Queue