TIL 15(멱집합&WindowLocalStorage) (2021.10.21)

-2021.10.21 오늘의 코플릿-
하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴해야 합니다.
arr[i]는 각 부분집합을 구성하는 원소를 연결한 문자열입니다.
arr[i]는 알파벳 순서로 정렬되어야 합니다.
집합은 중복된 원소를 허용하지 않습니다.부분집합은 빈 문자열을 포함합니다.
arr은 사전식 순서(lexical order)로 정렬되어야 합니다.

  // 하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴해야 합니다.
  // arr은 사전식 순서(lexical order)로 정렬되어야 합니다. sort를 진행하면 될 거 같다
  let result = ['', str] // 만드는 걸 다 push한다.
  // str.split()을 사용한다.
  // if arr.includes(s) true면 패스한다.

첫 수도코드 => str를 배열로 만들어서, result에 없는 값만 push를 해주려고 했습니다. 3개로 이뤄진 str의 경우에는 이중 반복문을 통해서 진행을 할 수 있을 거로 생각을 했지만, 더 긴 str을 받게 되면, 진행을 못할 거 같았습니다.

 

이러한 문제를 풀 때 for 문에만 의존을 하다보니 긴 파라미터가 들어올 경우, 해답을 못 찾는 경우가 태반이었습니다.

그래서 오늘은 이러한 문제를 풀 수 있는 방법에 대해서 학습해보도록 하겠습니다.

---

출처

집합론에서, 멱집합(冪集合, 영어: power set)은 주어진 집합의 모든 부분 집합들로 구성된 집합이다.
출처 위키백과

즉, 멱집합을 구하는 함수는 다음과 같이 정의 될 수 있다.

1.함수의 인자: 주어진 집합(배열)

2.함수안의 로직: 주어진 집합에 대한 부분집합을 구하기

3.함수의 리턴값: 멱집합(부분집합들의 집합 === 2차원 배열)

 

부분집합을 구하는 과정

[1, 2, 3] 이란 배열이 주어진 집합이라고 할 때,
[1, 2, 3] 의 모든 부분집합은 아래 8개와 같다.

[] (공집합)
[1] [2] [3]
[1, 2] [1, 3] [2, 3]
[1, 2, 3]

따라서 멱집합은 위의 모든 부분집합들의 집합이므로
[ [], [1], [2], [3],  [1, 2], [1, 3], [2, 3], [1, 2, 3] ]
처럼 2차원 배열로 표현될 수 있다.

컴퓨터에는 다음과 같은 명시가 필요하다.

[O, O, O] => [1, 2, 3]
[O, O, X] => [1, 2]
[O, X, O] => [1, 3]
[O, X, X] => [1]
[X, O, O] => [2, 3]
[X, O, X] => [2]
[X, X, O] => [3]
[X, X, X] => []

명시된 배열의 상태에 따라서 부분집합이 달라지는 것을 볼 수 있다. 그럼 층에따라서 배열의 상태를 달리 해 주면 되지 않을까? => DFS 알고리즘을 적용하자!

 

재귀의 엔딩조건은 층이 3층일때(배열의 길이와 같을 때)다. 탐색하는 방법은 이진트리의 왼쪽과 오른쪽을 탐색하듯이 왼쪽으로 갈때에는 select=true=o를, 오른쪽으로 갈때에는 unselect=false=x를 해주면 된다

 

구현

• flag[]: 재귀의 엔딩조건(가장 깊은 층 = 배열의 길이) 에 도달 했을 때 상태를 저장할 배열
• subSets[]: 최종 리턴 될 멱집합(각각의 부분집합을 담을 배열)
• subSet function: DFS알고리즘을 재귀로 구현한 함수

const getSubsets = function (arr) {
  let flag = new Array(arr.length).fill(false);
  const subSets = [];

  const subSet = function DFS (depth) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (depth === arr.length) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push

      return;
    }

    flag[depth] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(depth + 1); // 트리의 왼쪽에 대해 재귀호출

    flag[depth] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(depth + 1); // 트리의 오른쪽에 대해 재귀 호출
  }
  
  subSet(0); // depth 0 부터 시작
  return subSets;
}

const example = [1,2,3];
const result = getSubsets(example);
console.log(result);

=> 이러한 코드를 통해서 멱집합을 구현할 수 있습니다.

하지만 오늘 코플릿의 경우에는 알파벳 순서대로 정렬을 해야하다보니, 해당 코드로 구현할 경우 문제가 발생합니다.

---

출처

다른 분의 코드를 빌려와 해당 문제에 대해서 학습하도록 하겠습니다.

const powerSet = function (str) {
  // TODO: 여기에 코드를 작성합니다.
  let arr = str.split('').sort(); //문자열을 분리해서 배열로 만들어주고 정렬해준다.
  let result = [''] //결과가 담길 배열
  
  let aux = (target, result) => { //result에서 target을 추가한 인자들을 result에 추가해주는 함수
    let copy = result.slice();
    for(let i = 0; i < copy.length; i++){
      copy[i] += target;
      result.push(copy[i])
    }
    return result
  }

  for(let i = 0; i < arr.length; i++){ //arr의 값들을 전부 넣어서 aux함수 실행
    if(!result.includes(arr[i])){ //중복값이 아닌 경우에만 실시
      aux(arr[i], result)
    }
  }
  return result.sort(); //결과를 정렬해서 반환
};

---

레프런스

=> 멱집합 첫 코드에서 넣었던 false 배열은 없이 진행합니다.

const powerSet = function (str) {
  // 정렬
  const sorted = str.split('').sort();

  // 중복 제거
 const deduplicated = [];

 for (let i = 0; i < sorted.length; i++ ) {
   if(!deduplicated.includes(sorted[i])) {
     deduplicated.push(sorted[i])
   }

 }
  let subSets = [];
  const pickOrNot = (idx, subset) => {
    // base case
    if (idx === deduplicated.length) {
      // 마지막 문자까지 검토한 경우
      subSets.push(subset);
      return;
    }

    // recursive case
    // idx번째 문자가 포함되지 않는 경우
    pickOrNot(idx + 1, subset);

    // idx번째 문자가 포함되는 경우
    pickOrNot(idx + 1, subset + deduplicated[idx]);
  };

  pickOrNot(0, '');

  return subSets.sort();
};

실제로 셋 다 코드를 구현해봤는데, 일단은 첫 번째와 세 번째가 조금 더 손에 익는 거 같아서 해당 방법으로 계속 구현을 해볼  예정입니다. 손에 익긴 하지만, 정확하게 구현하는 데에는 어려움이 있어서 지속적인 반복으로 정확하게 구현해낼 수 있도록 노력하겠습니다.

---

어제부터 오늘까지 리액트의 데이터 흐름과 useEffect, fetch에 대해서 학습하고 과제를 풀었습니다.

과제 진행 도중에 

if (typeof window !== "undefined") {
  localStorage.setItem('flight', JSON.stringify(flightList));
}

이러한 코드를 보게 되었고, 이게 어떤 의미인 궁금해서 storage에 대해서 학습하고, 해당 문구가 무엇을 의미하는 지에 대해서 알아봤습니다.

 

출처 MDN

Web Storage API 사용하기

 

Web Storage API는 브라우저에서 쿠키를 사용하는 것보다 훨씬 직관적으로 key/value 데이터를 안전하게 저장할 수 있는 메커니즘을 제공합니다.

 

기본 컨셉

Storage 객체는 단순한 key-value 저장소이며, 이는 객체와 비슷합니다. 하지만 이 데이터들은 페이지 로딩에도 온전하게 유지됩니다. key와 그 value는 항상 문자열입니다. (만약 정수로 키를 사용할 경우 이는 자동으로 string으로 변경됩니다, 자바스크립트 객체의 동작방식을 생각해보세요) 객체를 사용하듯이 쉽게 값에 접근할 수 있으며, 이 때 Storage.getItem() (en-US)과 Storage.setItem() (en-US) 메서드를 사용할 수 있습니다.

 

Web Storage는 두 메커니즘을 가지고 있습니다.

• sessionStorage는 페이지의 세션이 유지되는 동안 사용할 수 있는 각 origin별로 별도의 스토리지를 관리합니다. (페이지 리로딩 및 복원을 포함한, 브라우저가 열려있는 한 최대한 긴 시간 동안)
• localStorage도 같은 일을 하지만, 브라우저가 닫히거나 다시 열리더라도 유지합니다.

이 메커니즘들은 Window.sessionStorage와 Window.localStorage속성(좀 더 정확히 말하자면, 지원하는 브라우저에서Window객체는localStorage 및 sessionStorage속성 사용이 중단되는WindowLocalStorage과WindowSessionStorage로 구현됩니다)으로 사용 가능합니다. 이 중 하나를 호출하면 데이터를 설정, 검색 및 제거할 수 있는Storage객체의 인스턴스가 생성됩니다. 각 Storage 객체는 각 origin 별 sessionStorage나 localStorage로 사용됩니다. 동작도 제각기 동작합니다.

 

예를 들면, 문서에서 localStorage를 호출하면 Storage 객체를 반환합니다. 문서에서 sessionStorage를 호출하면 다른 Storage 객체를 반환합니다. 둘 다 같은 방법으로 조작할 수 있지만, 서로 다릅니다.

---

Window.localStorage

localStorage 읽기 전용 속성을 사용하면 Document 출처의 Storage 객체에 접근할 수 있습니다. 저장한 데이터는 브라우저 세션 간에 공유됩니다. localStorage는 sessionStorage와 비슷하지만, localStorage의 데이터는 만료되지 않고 sessionStorage의 데이터는 페이지 세션이 끝날 때, 즉 페이지를 닫을 때 사라지는 점이 다릅니다. ("사생활 보호 모드" 중 생성한 localStorage 데이터는 마지막 "사생활 보호" 탭이 닫힐 때 지워집니다.)

 

localStorage에 저장한 자료는 페이지 프로토콜별로 구분합니다. 특히 HTTP(http://example.com)로 방문한 페이지에서 저장한 데이터는 같은 페이지의 HTTPS(https://example.com)와는 다른 localStorage에 저장됩니다.

키와 값은 항상 각 문자에 2바이트를 할당하는 UTF-16 DOMString의 형태로 저장합니다. 객체와 마찬가지로 정수 키는 자동으로 문자열로 변환합니다.

 

구문

myStorage = window.localStorage;

값

현재 출처의 로컬 저장 공간에 접근할 수 있는 Storage 객체.

 

예외

SecurityError요청이 정책의 결정을 위반했거나, 출처가 유효한 스킴/호스트/포트 튜플이 아닌 경우. 유효하지 않은 튜플은 출처가 file:이나 data: 스킴을 사용했을 때 발생할 수 있습니다. 예외의 예를 들자면 사용자가 특정 출처의 지속성 데이터를 거부하도록 브라우저를 설정하는 경우가 있습니다.

 

예제

아래 코드는 현재 도메인의 로컬 Storage 객체에 접근한 후, Storage.setItem() (en-US)을 사용해 항목 하나를 추가합니다.

localStorage.setItem('myCat', 'Tom');

위에서 추가한 localStorage 항목을 읽는 법은 다음과 같습니다.

const cat = localStorage.getItem('myCat');

그리고 제거는 아래와 같습니다.

localStorage.removeItem('myCat');

localStorage 항목의 전체 제거 구문입니다.

localStorage.clear();

---

현재 이를 통해서 storage의 이론을 학습하긴 했지만, 정확한 사용 방법에 대해서는 학습이 이뤄지지 않았습니다. 추가적인 학습을 통해서 storage에 대해서 이해하고 활용할 수 있도록 하겠습니다.

 

그렇다면,

if (typeof window !== "undefined") {
  localStorage.setItem('flight', JSON.stringify(flightList));
}

여기에서 나오는
typeof window !== "undefined" 는 무슨 의미인가?

왜 이런 문구가 사용되는 건지 알아보겠습니다.

This can be used to detect whether code is running in a typical browser environment (e.g. an environment with a browser DOM) or in some other JS environment since the 
window
 object exists in a typical browser JS, but does not exist in something like node.js or even a webWorker in a browser.

이것은 window 객체가 일반적인 브라우저 JS에 존재하지만 node.js와 같은 것에 존재하지 않기 때문에 코드가 일반적인 브라우저 환경(예: 브라우저 DOM이 있는 환경)에서 실행되고 있는지 또는 일부 다른 JS 환경에서 실행되고 있는지 감지하는 데 사용할 수 있습니다. 또는 브라우저의 webWorker.(자동번역)

출처

In a webpage, there are several intrinsic objects, such as window, other environments (like Node.js) won't have window but might have other objects like console (well, console now exists in most browsers now, but it wasn't originally).

웹페이지에서는, window와 같은 몇가지 고유한 객체가 있는데, node.js와 같은 다른 환경은 window는 없지만 console과 같은 다른 객체를 가지고 있습니다.(지금은 대부분의 브라우저에서 console이 존재하지만, 원래 그랬던 것은 아니다.)
(작성자 번역)

출처

 

해당 문구의 purpose에 대해서 구글링을 한 결과, 스크립트가 웹 브라우저 내부의 웹 페이지에서 실행되고 있는지 여부를 확인하는 관용적 검사라는 것을 확인할 수 있었습니다. window.localstorage를 활용하기 위해서 window 객체 여부를 확인하는 것이라 생각합니다.

 

=> 해당 블로그를 읽으시다가 잘 못 이해하고 작성한 부분이 있다면 편리하게 의견 남겨주세요! 아직 내용이 많이 부족한데, 추가적인 학습 후 업데이트하도록 하겠습니다.