yunrap 개발블로그

깊이 우선탐색 (Depth-Firtst Search)

깊이우선 탐색이란?

루트노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이라고한다.

즉, 깊게 탐색, 완벽탐색

사용하는경우 

모든 노드를 방문 하고자 하는 경우에 이방법을 선택한다.

특징 

1. 자기자신을 호출하는 순환 알고리즘의 형태를 가지고있다.

2. 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.

원리

위의 그림을 보면서 아래 설명을 봐보자.

1. 시작 정점을 1로 설정

2. 1번 탐색 시작 1번과 연결되었고 방문 안한 정점이 어디지? 2번이 있네. 2번으로 가자.

3. 2번과 연결되었고, 방문 안한것? 3번이네. 3번으로 가자.

4. 3번은? 4번이 있네. 4번으로 가자.

5. 4번은? 없는데..?? 그러면 3번으로 다시 올라가자.

6. 3번은? 방문 안한곳이 없네.. 다시 2번... 다시 1번

7. 1번은? 5번이 있네. 5번으로 가자.

-> 이런 식으로 방문 안한 곳이 없을때까지 반복

이런식으로 쭉 탐색을 한다. 이런식으로하면 한길로 깊이 있게 파고들어가게 된다. 이래서 깊이 우선탐색이라는 말이 나온것이다.

장단점

장점

코드가 직관적이고, 구현하기 쉽다.
-> 사실 일정행동을 계속 반복하는데, 이를 만들어놓고 끝까지 계속 돌려 쓰는 것이기 때문에 비교적 간단하게 코드를 구현할 수 있다.

단점

깊이가 엄청 깊어지면, 메모리 비용을 예측하기 어렵다.
-> 앞서 설명한 것처럼 깊이가 깊어질수록 함수가 하나씩 쌓이는 구조이다. 이 때문에 깊이가 엄청 깊어진다면 스택 메모리가 지나치게 커질 수 있다.

또한 최단 경로를 알 수 없다.

코드

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const DFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...graph[node], ...needVisit];
    }
  }
  return visited;
};

console.log(DFS(graph, "A"));
// ["A", "B", "D", "E", "F", "C", "G", "H", "I", "J"]

function solution(land) {

    for(let i =0; i <=land.length; i++){    //행
        let landVal = 0;
        let landValSum = 0;
        let lengthAr = land[0].length;
        
        for(let j=0; j<=lengthAr-1; j++)   //열
        {
             // 왼쪽 행이랑 겹치는부분 존재한다면
            if(i !== 0 && land[i-1][j] !== 0){
                // 그행의 아래행 계속찾기
                for(let k=j; k<= 500; k++){
                   if(land[i-1][k] == 0){   
                        landValSum = land[i-1][k-1];
                        landValSum ++;
                        break;
                   } 
                }
                 land[i][j]  = landValSum;
            }else{
                if(land[i][j] === 1){
                    land[i][j] = landVal++;
                }
            }
        }
    }
    
    var answer = 0;
    return answer;
}

버그버그버그

프로젝트를 진행하면서 파일첨부기능을 구현하던중 multipart/form-data 에대한 사용이 필요했다

오늘은  정리할겸 HTTP, multipart/form-data 키워드에대해서 알아보고

그중에서 multipart/form-data 에 대해서 알아보자

http란 HyperText Transfer Protocal 이다.

문서를 전송하기위한 프로토콜

즉 서버와 클라이언트의 사이에서 어떻게 메시지를 교환할지를 정해 놓은 규칙이다.

우리가하용하는 웹브라우저에서 인터넷 주소 맨 앞에들어가는 http://가 바로 이프로토콜을 사용해서 정보를 교환하겠다는 표시이다.

 데이터를 교환할때 타입은 두가지가 있다.

요청과 응답이다.

1. 파일 업로드를 구현할 때, 클라이언트가 웹브라우저라면 폼을 통해서 파일을 등록해서 전송한다.

2. 웹 브라우저가 보내는 HTTP 메시지는 Content-Type 속성이 multipart/form-data로 지정되고 정해진 형식에 따라 메시지를 인코딩      하여 전송한다.

3. 이를 처리하기 위한 서버는 멀티파트 메시지에 대해서 각 파트별로 분리하여 개별 파일의 정보를 얻게 된다.

아래가 multipart로 형식으로 담아서 볼낼때의 정보의 예시이다.

POST /save HTTP/1.1
Host: localhost:8080
Content-Type: multipart/form-data; boundary=-----XXX

-----XXX
Content-Disposition: form-data; name="username"

kim
-----XXX
Content-Disposition: form-data; name="age"

20
-----XXX
Content-Disposition: form-data; name="file1"; filename="intro.png"
Content-Type: image/png

12368asdzxc9qwetwga35468asdfzxvczxc....
-----XXX--

Multipart란 클라이언트에서 서버로 파일을 보낼 때 사용하는 Content Type이다.

클라이언트에서 보내는 요청을 찬찬히 뜯어보면 boundary=-----XXX 로 되어있는 것을 볼 수 있는데, 이는 각 Form 데이터의 경계를 나타내며, 이 경계를 기준으로 각각의 데이터를 표기하여 여러 타입의 데이터를 섞이지 않고 전달하는 것을 목적으로 만들어진 데이터 전송법이다.

username과 age처럼 일반적인 데이터와 달리, 파일의 경우 Content-Type과 바이너리 데이터를 전송되는 것을 확인할 수 있다. HTTP 요청은 모두 문자열로 이루어지는데, 서버는 해당 요청을 받아 HTTP 스펙에 맞춰 이를 변환하는 작업을 진행해야한다.

http로 웹상에서 프로토콜을 정해 client 와 server 간의 요청응답으로 데이터를 주고받으며

줄때 file upload에서는 multipart 형식으로 요청한다는 것을 간략하게 정리해보았다.

사용자의 로그인 상태를 서버에서 처리하는데 사용할수있는 대표적인 두가지 인증방식이있다.

1. 세션을 기반으로 인증

2. 토큰을 기반으로 인증

1. 세션 기반 인증 시스템

세션을 기반으로 인증 시스템을 만든다는것은 서버가 사용자가 로그인중임을 기억하고 있다는 뜻이다.

직접그려서 글씨체가 이상한건 양해....

세션 기반 인증시스템에서 사용자가 로그인을 하면, 서버는 세션 저장소에 사용자의 정보를 조회하고 세션 id를 발급한다

발급된 id는 주로 브라우저의 쿠키에 저장한다. 그다음에 사용자가 다른 요청을 보낼때마다 서버는 세션 저장소에서

세션을 조회한후 로그인 여부를 결정하여 작업을 처리하고 응답을 한다

세션 기반 인증의 단점은 서버를 확장하기가 번거로워 질 수 있다는 점이다.

만약 서버의 인스턴스가 여러개가 된다면, 모든 서버끼리 같은 세션을 공유해야 하므로 세션 전용 데이터베이스를 만들어야 할 뿐 아니라 신경 써야 할것도 많다.

2. 토큰 기반 인증시스템

토큰은 로그인 이후 서버가 만들어주는 문자열이다. 해당 문자열안에는 사용자의 로그인 정보가 있고, 해당정보에는 서버에서 발급되었음을 증명하는 서명이 들어있다.

서버에서 만들어준 토큰은 해싱 알고리즘을 통해 만들어진 서명이있기때문에 무결성이 보장된다.

사용자가 로그인을 하면 서버에서 사용자에게 해당 사용자의 정보를 지니고 있는 토큰을 발급해주고, 그러면 서버는 해당 토큰이 유효한지 검사하고, 결과에 따라 작업을 처리하고 응답한다.

사용자 쪽에서 로그인 상태를 지닌 토큰을 가지고있으므로 서버의 확장성이 매우 높다.

서버의 인스턴스가 여러개 늘어나도 서버끼리 사용자의 로그인 상태를 공유 하고 있을 필요가 없기때문이다.

이두가지 기능중에서 우선 토큰 기반 인증 시스템을 사용해보겠다.

구현하기 간편하고 사용자들의 인증 상태를 관리하기 쉽기때문이다.

1. 실행 컨텍스트란

실행가능한 자바스크립트 코드 블록이  실행되는 환경이다.

함수가 실행되면 함수 실행에 해당하는 실행 컨텍스트가 생성되고, 자바스크립트 엔진에 있는 콜스택에 차곡차곡 쌓인다.

그리고 가장위에있는 컨텍스트와 관련 있는 코드를 실행하면서, 전체 코드의 환경과 순서를 보장하게 된다.

아래의 예제로 이해보자

let santa = false; // 전역 컨텍스트
var rudolf = false;
function christmas() {	
  let santa = true;

  function givePresent() { 
    let gift = "cat";
    console.log(gift); // cat
    console.log(santa); // false
    console.log(rudolf); // false
  }

  givePresent(); // (2)
}

christmas(); // (1)

이런 코드를 실행하려고 하면 

처음으로 전역 컨텍스트가 호출 스택에 추가된다

실행컨텍스트가 호출스택에 쌓여가는 과정을 그림으로 그려 이해해보자

2. 실행 컨텍스트의 구성

2-1. 전역 컨텍스트의 생성

전역 컨텍스트란

코드가 실행되면 바로 생성되며, 컨텐스트중 제일 먼저 호출스택에 저장되는 컨텍스트이다.

생성단계에서 let으로 선언한 변수인 santa는 선언만되고 초기화는 이루어지지않고,

var로 선언된 rudolf는 선언과 동시에 undefined로 초기화가 이루어진다.

christmas() 도 함수선언문으로 선언되어서 호이스팅이 일어나 생성단계에서 전역컨텍스트에 기록된다

2-2. 전역 컨텍스트의 실행

전역컨텍스트가 실행단계로 들어간다. 이과정에서 함수 호출, 식별자 할당 등이 이루어진다.

초기화 되지 않아 아무 값이 없던 santa가 false로 할당 된다.

2-3. 함수 컨텍스트의 생성 christmas()

전역컨텍스트가 생성된이후 가장 먼저 호출되는 함수는 christmas() 이다.

따라서 호출스텍에 전역 컨텍스트 다음으로 christmas() 함수 컨텍스트가 쌓이게된다.

2-3. 함수 컨텍스트의 생성 givePresent()

christmas 함수 내부에서 givePresent 함수를 선언하고 호출한다.

따라서 givePresent 함수 컨텍스트가 호출 스택에 쌓이게 된다.

여기서 의문점?

let santa = false; // 전역 컨텍스트
var rudolf = false;
function christmas() {	
  let santa = true;

  function givePresent() { 
    let gift = "cat";
    console.log(gift); // cat
    console.log(santa); // false    -------->>>>>> 어떻게 호출??
    console.log(rudolf); // false  ------->>>>>> 어떻게 호출??
  }  

  givePresent(); // (2)
}

christmas(); // (1)

이해하던도중 그렇다면  givePresent 컨텍스트를 실행할때 어떻게 chrismas에있는 컨텍스트에 있는 santa를 호출할수있었을까??

라는 의문점이 든다.

이것을 이해하려면 실행컨테스트에 특수한객체인 outer를 이해해야한다.

3. outer 

console.log(gift)

1. gift의 값을 가져오기위해 givePresent 함수 컨텍스트의 환경 레코드를 참조한다.

2. givePresent 함수 컨텍스트의 환경 레코드에서 gift의 정보를 찾았기 때문에 console.log()를 문제없이 호출한다.

console.log(santa)

1. santa 의 값을 가져오기위해 givePresent 함수 컨텍스트의 환경 레코드를 참조한다.

2. 환경레코드에서 santa의 값을 찾지 못한다.

3. outer를 이용해 외부 렉시컬 환경인 chrismas 함수 컨텍스트로 이동후 환경레코드를 탐색한다.

4. santa 값을 찾으며 console.log()를 문제없이 호출한다.

console.log(rudolf)

1. rudolf의 값을 가져오기 위해 givePresent 함수 컨텍스트의 환경 레코드를 참조한다.

2. 환경레코드에서 rudolf의 값을 찾지 못한다.

3.  outer를 이용해 외부 렉시컬 환경인 chrismas 함수 컨텍스트로 이동후 환경레코드를 탐색한다.

4. 환경 레코드에서 rudolf를 찾지못해 outer를 이용하여 전역 컨텍스트로 이동한다.

5. 환경레코드를 탐색하여 rudolf를 찾고 console.log()를 문제없이 호출한다.

4. 스코프 체인(scope chain)

위에서 자바스크립트 엔진이 해당 영역에서 식별자를 찾는데 발견하지 못했을때 outer를 이용해여 외부 렉시컬 환경, 즉

외부 영역으로 이동하여 식별자를 찾는다는 것을 알 수 있었다.

이렇게 식별자를 찾기위해 외부스코프로 이동하여 탐색하는 현상을 스코프 체인이라고 한다.

문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

array commands return

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.

[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.

[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

// 풀이과정
// 변수 : 새로운배열 k, 정렬후 자리수선택 배열 d
// 필요 : 1반복분(commands 개수),  정렬(버블)

function solution(array, commands) {
  var reArray = [];
  var answer = [];

  for (var i = 0; i < commands.length; i++) {
    var fromVar = commands[i][0];
    var toVar = commands[i][1];
    for (fromVar; fromVar <= toVar; fromVar++) {
      reArray.push(array[fromVar - 1]);
    }

    // 버블정렬
    for (var j = 0; j < reArray.length; j++) {
      for (var z = j + 1; z < reArray.length; z++) {
        if (reArray[j] > reArray[z]) {
          var tmp = reArray[z];
          reArray[z] = reArray[j];
          reArray[j] = tmp;
        }
      }
    }
    // console.log(reArray + "정렬후배열");

    answer.push(reArray[commands[i][2] - 1]);
    reArray = [];
  }
  // console.log(answer + "정답!");
  return answer;
}

solution(
  [1, 5, 2, 6, 3, 7, 4],
  [
    [2, 5, 3],
    [4, 4, 1],
    [1, 7, 3],
  ]
);