CSR의 정의

CSR이란 웹페이지의 렌더링이 클라이언트 브라우저에서 발생하는 것으로, 어플리케이션 구동에 필요한 파일 (HTML, CSS, JS 등)을 최초 요청에서 모두 다운로드하여 뷰가 구성된다.

장점

• 서버 부담 / 후속 페이지 로드 시간 감소 최초에 필요한 파일을 모두 받아오기 때문에 사이트의 다른 페이지로 이동 시에 이미 받아놓은 JS 실행을 하기 때문에 서버에 요청할 필요가 없고, 로딩 시간 또한 빠르다.
• 사용자 경험 새로고침이 발생하지 않기 때문에 내부 컨텐츠 변경으로 인한 깜빡임 현상 등이 발생하지 않아 사용자 친화적인 환경을 제공할 수 있다.

단점

• 초기 로딩 속도 느림 초기에 모든 파일을 로드한 후에 뷰를 구성해야하기 때문에 앱의 규모가 커질 수록 초기 구동시간이 크게 느려진다.
• SEO에 불리 웹 페이지의 콘텐츠가 JS를 통해 동적으로 변경되기 때문에, 과거의 검색 엔진 크롤러는 JS 실행을 하지 않아서 빈페이지를 마주하기 때문에 CSR 방식은 SEO에 매우 불리하다.

2. SPA(Single Page Application)로 구성된 웹 앱에서 SSR(Server-side Rendering)이 필요한 이유에 대하여 설명해주세요.

일반적인 SPA 의 렌더링 방식은 CSR을 사용하나, CSR은 SEO에 불리하다는 단점이 있다. 사용자 유입이 중요하여 검색 엔진 최적화가 우선되어야 할 경우, SSR 방식이 적합하다.

SSR은 서버에서 사용자에게 보여줄 페이지를 모두 렌더링하여 전달하는 방식이다. 서버에서 페이지 구성이 모두 이뤄진 뒤 전달되기 때문에 CSR 방식에 비해 SEO에 훨씬 유리하다.

Next.js 프로젝트를 세팅한 뒤 yarn start 스크립트를 실행했을 때 실행되는 코드를 nextjs github 레포지토리에서 찾은 뒤, 해당 파일에 대한 간단한 설명을 첨부해주세요.

(1) PROJECT/package.json

{
    ...
    "scripts" : {
        "dev": "next dev",
          "build": "next build",
          "start": "next start"
    },
      ...
}

create-next-app 를 통해 프로젝트 생성하고, package.json 파일의 scripts 부분을 확인하였다. yarn start 스크립트 실행 시 "next start"가 실행되는 것을 볼 수 있다.

(2) next.js/packages

next.js/packages 폴더에서 next.js 관련 package들이 나뉘어 있는 것을 발견할 수 있었다. 프로젝트 세팅하며 사용했던 create-next-app 패키지 등이 담겨 있다. 여기서 next 내부를 확인해 본다.

(3) next.js/packages/next/lib/commands.ts

export type cliCommand = (argv?: string[]) => void

export const commands: { [command: string]: () => Promise<cliCommand> } = {
  build: () => Promise.resolve(require('../cli/next-build').nextBuild),
  start: () => Promise.resolve(require('../cli/next-start').nextStart),
  export: () => Promise.resolve(require('../cli/next-export').nextExport),
  dev: () => Promise.resolve(require('../cli/next-dev').nextDev),
  lint: () => Promise.resolve(require('../cli/next-lint').nextLint),
  telemetry: () =>
    Promise.resolve(require('../cli/next-telemetry').nextTelemetry),
  info: () => Promise.resolve(require('../cli/next-info').nextInfo),
}

commands.ts 파일에서 command가 나열되어 있는 것을 확인할 수 있었다. 그 중에서 nextStart 확인해보자.

(4) next.js/packages/next/cli/next-start.ts

next-start.ts에 nextStart 라는 함수가 선언되어 있었다. 함수의 구성은 아래와 같다.

1. 옵션 유효성 검사

const validArgs: arg.Spec = {
    // Types
    '--help': Boolean,
    '--port': Number,
    '--hostname': String,
    '--keepAliveTimeout': Number,

    // Aliases
    '-h': '--help',
    '-p': '--port',
    '-H': '--hostname',
  }
  let args: arg.Result<arg.Spec>
  try {
    args = arg(validArgs, { argv })
  } catch (error) {
    if (isError(error) && error.code === 'ARG_UNKNOWN_OPTION') {
      return printAndExit(error.message, 1)
    }
    throw error
  }

arg의 경우 'next/dist/compiled/arg/index.js'에서 import 해오는데, next [command] [option]의 형태로 받은 입력 및 여러 설정들을 처리한 것으로 보인다. 받은 입력이 정의된 형태로 들어왔는지 검사하는 부분이다.

2. help 옵션에 대한 처리

  if (args['--help']) {
    console.log(`
      Description
        Starts the application in production mode.
        The application should be compiled with \`next build\` first.
      Usage
        $ next start <dir> -p <port>
      <dir> represents the directory of the Next.js application.
      If no directory is provided, the current directory will be used.
      Options
        --port, -p      A port number on which to start the application
        --hostname, -H  Hostname on which to start the application (default: 0.0.0.0)
        --keepAliveTimeout  Max milliseconds to wait before closing inactive connections
        --help, -h      Displays this message
    `)
    process.exit(0)
  }

--help 또는 -h 옵션이 있는 경우, next start에 대한 설명을 로그 찍고 실행을 종료한다.

3. 변수 선언

 const dir = getProjectDir(args._[0])
  const host = args['--hostname'] || '0.0.0.0'
  const port = getPort(args)

  const keepAliveTimeoutArg: number | undefined = args['--keepAliveTimeout']
  if (
    typeof keepAliveTimeoutArg !== 'undefined' &&
    (Number.isNaN(keepAliveTimeoutArg) ||
      !Number.isFinite(keepAliveTimeoutArg) ||
      keepAliveTimeoutArg < 0)
  ) {
    printAndExit(
      `Invalid --keepAliveTimeout, expected a non negative number but received "${keepAliveTimeoutArg}"`,
      1
    )
  }

  const keepAliveTimeout = keepAliveTimeoutArg
    ? Math.ceil(keepAliveTimeoutArg)
    : undefined

dir, host, port 등 서버 실행에 필요한 변수들 선언하고 있다. keepAliveTimeout은 프로세스 유지 시간으로, 값이 유효하지 않을 경우 에러메세지 프린트 후 종료한다.

4. startServer 실행

startServer({
    dir,
    hostname: host,
    port,
    keepAliveTimeout,
  })
    .then(async (app) => {
      const appUrl = `http://${app.hostname}:${app.port}`
      Log.ready(`started server on ${host}:${app.port}, url: ${appUrl}`)
      await app.prepare()
    })
    .catch((err) => {
      console.error(err)
      process.exit(1)
    })

startServer 함수는 start-server.ts 에 정의되어 있다.

    const server = http.createServer((req, res) => {
        return requestHandler(req, res)
      })

    server.on('listening', () => {
      const addr = server.address()
      const hostname =
        !opts.hostname || opts.hostname === '0.0.0.0'
          ? 'localhost'
          : opts.hostname

      const app = next({
        ...opts,
        hostname,
        customServer: false,
        httpServer: server,
        port: addr && typeof addr === 'object' ? addr.port : port,
      })

      requestHandler = app.getRequestHandler()
      upgradeHandler = app.getUpgradeHandler()
      resolve(app)
    })

    server.listen(port, opts.hostname)

createServer를 통해 server라는 웹 서버 객체를 생성했다. next-start.ts 에서 startServer를 호출하며 넘겨준 인자들로 세팅한 server를 실행한다.

HTTP와 데이터 유출 🧐

HTTPS는 HTTP의 보안이 강화된 버전이라고 설명할 수 있다. HTTPS를 설명하기에 앞서 HTTP를 간단히 정리하자면 HTML 같은 리소스들을 교환하기 위한 프로토콜이다. 클라이언트는 서버에 데이터를 요청하고, 서버는 이에 대해 응답하는 구조를 갖는다.

HTTP를 통해 교환하는 데이터들은 텍스트 형태를 갖는다. 즉, 데이터가 전달되는 네트워크의 전송 신호를 인터셉트하면 데이터의 유출이 발생할 수 있다는 것이다. 이런 HTTP의 취약한 보안때문에 이를 막기위한 방법이 필요했고, 그 대안이 HTTPS이다.

현재 HTTP는 민감하지 않은 데이터를 다루는 사이트에서 사용되며, 인증이나 전자상거래 등의 데이터는 HTTPS로 다룬다. 그러나 보안에 대한 관심이 증가하여 HTTP를 사용하는 사이트를 브라우저에서 경고 메세지를 띄워주고 있으며, HTTPS로 대부분 전환해가는 추세이다.

HTTPS

그럼 HTTPS는 어떻게 동작하기에 HTTP의 보안을 강화할 수 있었는지 자세히 살펴보자. 일단 HTTPS의 핵심은 공개키 암호화 방식이다. 암호화와 복호화를 할 수 있는 2개의 키가 존재한다. 만약 1번 키로 데이터를 암호화 했다면, 다른 2번 키로만 복호화할 수 있다. 반대로 2번 키로 암호화 했다면, 1번 키로 복호화할 수 있는 방식이다.

생성된 2개의 키 중 하나는 공개 키 저장소에 존재한다. 또한 다른 하나는 서버가 소지하고 있다.

클라이언트가 서버에 데이터 처리를 요청할 때, 공개 키 저장소에 있던 키를 통해 데이터 암호화를 진행한다.

공개 키를 통해 암호화 된 데이터를 포함하는 HTTPS 요청이 들어오면, 서버는 이에 대응하는 다른 키를 통해 복호화를 진행한다.

복호화된 데이터를 가지고 클라이언트의 요청을 처리하고 다시 클라이언트에 서버가 가진 키를 통해 암호화를 진행한 결과를 응답한다. 클라이언트는 이를 다시 공개 키를 통해 복호화를 진행해 데이터를 얻는다.

HTTP가 등장하기 이전의 통신은 불편한 터미널을 통해 텍스트를 주고 받는 정도였다. 지금처럼 예쁜 디자인에 역동적인 애니메이션의 웹 페이지는 상상조차 할 수 없었다.

1989년, HTTP의 등장

Hyper Text Transfer Protocol. WWW 상에서 HTML 문서같은 리소스들의 교환을 위한 프로토콜.

HTTP의 등장으로 터미널을 통한 딱딱한 텍스트 교환을 벗어나, HTML같이 멋진 문서를 주고 받을 수 있게 되었다. 시각적으로 크게 변화하였고, 전달하는 정보량 또한 훨씬 증가하게 되었다.

HTTP의 핵심은 사용자는 URL을 통해 원하는 페이지를 서버에 요청, 서버는 이에 응답한다는 것이다. 즉, URL을 이동하면 사용자의 웹 브라우저는 서버에 해당 URL에 해당하는 웹페이지를 요청한다. 서버가 응답한 HTML 문서를 브라우저가 그려낸다.

🚨 HTTP의 한계

언급했던 HTTP의 핵심 중 URL을 통해 서버에 요청 부분에 집중해보자. 서버에 요청하려면 URL을 이용하는게 당연한거 아닌가? 라는 생각이 들 수 있겠지만 이전에는 지금과 상황이 달랐다. 예를 들어보자면, 회원가입 페이지가 있다.

지금처럼 크롬같은 브라우저를 사용하던 시기가 아닌, 거의 모든 이들이 인터넷 익스플로러를 사용하던 시기의 웹사이트 회원가입 페이지를 떠올려보자. 아이디 중복 검사를 위해 버튼을 누르면, 항상 새로운 창이 생겼던 것이 기억이 날 것이다.

이유는 위에서 언급한 URL을 통해 서버에 요청 한다는 규약 때문이다. 사용자가 URL을 요청한다는 것은, 브라우저에서는 페이지의 이동이 발생함을 의미하는 것이다. 회원가입을 진행하다가 아이디 중복 검사를 하기 위해서 페이지가 이동되면, 돌아와서 모든 정보를 다시 입력해야할 것이다.

꼼수의 등장 🎮

Flash, ActiveX, 실버라이트 등 영상이나 플래시 게임 등을 하며 봤던 이름들이 여기서 등장한다. 플래시 게임을 하며 클릭 한 번으로 웹 페이지 이동이 한 번씩 발생했기에 아주아주 불편했다. ActiveX 같은 런타임 환경을 플러그인 형태로 제공하여 이런 불상사를 해결했었다. 하지만 근본적인 해결은 아니었기에 새로운 해결 방법이 필요했다.

구글 맵과 AJAX

구글은 2004년과 2005년에 각각 Gmail과 구글 맵을 발표한다. 여기서 화제가 된 것은 두 서비스가 플러그인이 아닌 AJAX라는 기술로 구현되었다는 것이다. 특히 지도 서비스는 필수적으로 ActiveX 같은 플러그인을 통해 구현해왔기에 큰 혁신이었다. 물론 이전에도 비슷하게 구현된 바 있었으나, 본격적으로 사용된 것은 이때부터라고 한다.

AJAX는 HTTP처럼 통신 규약을 지정한 프로토콜은 아니다. HTTP를 효과적으로 사용할 수 있는 기술이다. 때문에 아까 언급한 HTTP 흐름과 유사하다.

먼저 AJAX 이전의 HTTP 통신이다. 요청 페이지에서 확인 버튼을 누르면 브라우저는 서버에 데이터를 전달하고, 서버는 이를 받아 처리한 뒤 새로운 HTML 문서를 브라우저에 전달한다. 이 과정에서 페이지 이동이 발생한다.

AJAX를 활용한 통신 흐름이다. 위와 동일하게 요청 페이지에서 내용을 입력한 뒤 확인 버튼을 누르면 JS는 DOM을 읽고, XMLHttpRequest 객체를 통해 서버에 이를 전달한다. 서버는 받은 요청을 처리하고 XML/JSON 등의 데이터를 다시 XMLHttpRequest 객체에 전달한다. HTML을 교체하는 것이 아닌, DOM을 수정하여 결과 페이지가 만들어진다. 다시 말해 페이지 이동이 발생하지 않고, 페이지 내부의 일부만 변화하는 것이다.

• AJAX는 HTTP를 효과적으로 사용할 수 있는 기술이다.
• HTTP는 브라우저가 서버에 요청하지만, AJAX는 XMLHttpRequest 객체가 요청한다.
• 서버는 HTML 문서가 아닌, XML/JSON 형태를 반환하기에 페이지 이동 없이 페이지 내에서 변경 가능하다.

🚨 AJAX의 한계

AJAX는 현재 사용하는 주 통신 방법인데, 무엇이 문제일까? 예를 들어보자면 채팅이 있다. 채팅은 실시간으로 나에게 온 채팅이 있는지 확인할 수 있어야 한다. 그러나 서버에서 데이터를 보내기 위해서는 클라이언트의 요청이 필수이다. 만약 이를 AJAX(HTTP)로 구현한다면, 몇 초 간격으로 서버에 요청을 보내 확인하거나, 서버에 연결된 시간을 늘리는 등의 방법이 있을 것이다. 하지만 너무 많은 요청은 과부하를 일으키며, 동시에 수많은 사용자의 접속 어려움 등 문제점이 발생하기에 클라이언트의 요청이 없음에도 서버에게 응답을 받을 수 있는 새로운 해결 방안이 필요했다.

WebSocket의 등장 🚀

앞서 살펴본 HTTP(AJAX)는 이러한 구조를 가지고 있다. 클라이언트의 리퀘스트가 발생해 서버가 이를 수신하고 해당 요청을 처리한 뒤, 결과를 다시 클라이언트에 반환하며 연결은 끊어지게 된다.

웹소켓은 이와 조금 다르다. 클라이언트는 요청을 하고, 서버는 응답을 하는 구조는 변하지 않으나, 통신의 흐름이 클라이언트에 의해 결정되었다면, 웹소켓은 양방향 소통이 가능하다. 클라이언트의 요청이 없이도 서버는 언제든 응답을 할 수 있고 응답이 발생한 이후에도 지속적으로 연결을 유지하는 연결 지향형 특성을 갖는다.

• 지속적으로 연결을 유지하며, 연결 지향형이다.
• 클라이언트의 요청없이도 서버가 응답 가능한 양방향 통신 프로토콜이다.
• 접속 확립에는 HTTP가 사용되며, 이후에는 WebSocket이 독자적으로 사용된다.

웹소켓은 채팅처럼 실시간으로 양방향 데이터 통신이 필요하거나, 많은 수의 동시 접속자를 수용해야할 때 사용된다.

캐리와 오버플로우에 대해 한 종류의 레지스터를 바탕으로 자세히 설명해보고자 한다. 레지스터는 프로세서 내부에서 데이터를 일시적으로 저장하는 아주 빠른 기억 장소이다. 다양한 레지스터 중에서, 특수 레지스터인 상태 레지스터를 알아보자.

상태 레지스터

상태 레지스터는 마이크로 프로세서에 탑재되는 레지스터이다. 이미지를 자세히 들여다보면 32개의 비트, 즉 4 byte 크기인 것을 알 수 있다. 각 비트는 다양한 산술 연산 결과 상태를 저장한다. 크게 제어 플래그와 조건 플래그로 나뉘는데, 이중 우리가 집중할 것은 조건 플래그의 오버플로우 플래그와 캐리 플래그이다.

먼저 오버플로우 플래그는 말 그대로 오버플로우 발생 시 Set 될 것이라고 예상할 수 있다. 마찬가지로 캐리 플래그 또한 자리 올림이 발생하면 Set이 될 것으로 예상된다. 2가지 상황의 플래그 상태를 예측해보도록 하자.

플래그 상태 예측하기

🔎 1

첫 번째, 이진수 1111과 0001의 더하기 연산이다. 결과 값은 10000으로 쉽게 계산할 수 있다. 그러나 4 bit 연산인데 결과 값은 5 bit로 표현할 수 있는 범위를 넘겼다. 이는 오버플로우가 발생한 것이므로 레지스터의 상태는 다음과 같이 예측할 수 있다.

🔎 2

두 번째, 이진수 0111과 0001의 더하기 연산이다. 결과 값은 1000으로, 오버플로우는 발생하지 않았다. 대신 자리 올림이 발생했으므로 캐리 플래그가 Set 될 것이다.

진짜 플래그 상태

🔎 1

10000은 표현 범위를 넘겼기 때문에 위에서 오버플로우 플래그 Set으로 예상했지만, 이 경우에는 캐리 플래그가 Set된다.

10000은 1이 무시되지만 캐리가 일어난 것은 맞기 때문에 캐리 플래그가 Set 된다. 하지만 오버플로우 플래그가 Set 되지 않는 것은 결국 결과는 0으로, 하위 4 bit가 알맞은 값을 제대로 표현하고 있기 때문이다. 따라서 이 경우 캐리가 발생한 것이고, 오버플로우는 발생하지 않았다.

🔎 2

0111 + 0001의 연산으로 0이었던 최상단이 1로 바뀌었기 때문에 캐리의 발생으로 오해할 수 있다. 하지만 캐리 플래그는 최상단 비트에서 캐리가 발생했을 때 Set된다. 이 경우에서는 최상단 비트에서는 캐리가 발생하지 않고 있기 때문에 캐리 플래그는 Set되지 않는다. 대신 오버플로우 플래그가 Set되는데, 이유는 부호이다.

양수인 7과 1을 더하는 연산의 결과가 -8이기 때문이다. 4 bit 이진수가 표현 가능한 범위는 7 ~ -8 로, 올바른 결과인 8은 애초에 나타낼 수 없는 값이 아니라서 잘못된 결과가 나타난다. 즉, 부호가 있는 연산에서 최대표현 숫자를 넘어서서 잘못된 결과가 나타난 경우 오버플로우 플래그가 Set 되는 것이다. 오버플로우 여부는 같은 부호를 더했을 때, 다른 부호가 나오는 것으로도 인지할 수 있다.

정리

상태 레지스터의 캐리 플래그는 최상단 비트에서 자리올림 발생 시 Set

상태 레지스터의 오버플로우 플래그는 최대 표현 숫자를 넘기거나, 같은 부호를 더했을 때의 결과가 다른 부호 일 시 Set

먼저 프로세스란 실행중인 프로그램 또는 작업이라고 할 수 있다. CPU가 프로세스를 실행하기 위해서는 프로세스에 대한 정보가 필요한데, 이를 Context라고 한다. 각 프로세스의 Context를 저장한 공간을 PCB라고 한다.

PCB (Process Control Block)

PCB는 운영체제의 커널 내부에 존재한다. 또한, 각 프로세스의 생성과 동시에 생성되며, 프로세스 종료 시 함께 사라진다.

위 이미지는 PCB 구조를 나타내고 있다. PCB는 다음과 같은 정보를 보유한다.

1) 프로세스 식별자(Process ID) 2) 프로세스 상태(Process State) : 생성(create), 준비(ready), 실행 (running), 대기(waiting), 완료(terminated)  3) 프로그램 계수기(Program Counter) : 이 프로세스가 다음에 실행할 명령어의 주소 4) 사용 중인 레지스터 정보 5) CPU 스케줄링 정보 : 우선 순위, 최종 실행시각, CPU 점유시간 등 6) 메모리 관리 정보(Memory limits) : 사용 가능한 메모리 공간 정보 7) 입출력 상태 정보 : 프로세스에 할당된 입출력장치 목록, 사용 파일 목록 등 8) 포인터 : 부모 프로세스에 대한 포인터, 자식 프로세스에 대한 포인터, 프로세스가 위치한 메모리 주소에 대한 포인터, 할당된 자원에 대한 포인터 정보

컨텍스트 스위칭 (Context Switching)

CPU가 실행하는 프로세스가 교체되며 CPU에서 관리하는 Context가 교체되는 것을 컨텍스트 스위칭이라고 한다.

먼저, CPU가 실행중인 프로세스의 Context는 해당 PCB에서 정보를 읽어와 CPU 내부의 레지스터가 관리한다. 그러다가 인터럽트가 발생하게 되면 해당 프로세스의 실행을 중지하게 된다. 인터럽트는 입출력 요청, CPU 사용 시간 만료, 자식 프로세스 생성, 인터럽트 처리 대기 등에 의해 발생하게 된다.

인터럽트가 발생하면 스케줄러에 의해 다음 프로세스가 실행이 되어야 한다. 다음 프로세스에게 차례를 넘겨주기 위해, 레지스터에서 다뤘던 종료될 프로세스의 Context를 PCB에 업데이트하게 된다. 이후에 다음 프로세스의 Context를 PCB에서 메인 메모리로 올리게 되고 CPU가 실행할 수 있게되는 것이다.

컨텍스트 스위칭을 통해 멀티프로세싱, 멀티스레딩을 구현할 수 있다. 그러나 Context 교체를 하는 동안 프로세스가 실행될 수 없으므로, 잦은 컨텍스트 스위칭은 오버헤드를 발생시켜 CPU의 성능을 저하시킬 수 있다.

2학년 1학기, 동아리에서 진행하는 알고리즘 스터디에서 DFS 문제를 선정한 적이 있었다. <여행경로>라는 문제였는데, 많이 헤맸고 결국 일주일 내에 해결하지 못한 것이 기억난다. 그 때 그저 "내 실력이 아직 많이 모자라구나"라고 생각했다. 알고리즘 문제를 풀어본 경험이 적기도 했지만, 알고리즘 공부는 전혀하지 않은 채 무작정 문제만 해결하려고 하니 벅찬 게 당연하다. 그때 풀지 못했던 DFS/BFS 문제를 해결하기 위해 제대로 공부하려고 한다.

DFS와 BFS를 알기전에, 그래프란?

그래프

단순히 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 비선형 자료구조

아주 어려운 말은 아니지만 역시 그림으로 이해하는 것이 빠르다 😋

사진 속 3가지 종류 모두 그래프로, 다양한 형태를 가질 수 있다. 우리가 잘 알고있는 트리 또한 그래프 중 하나이며, 특별한 케이스이다. 즉, 그래프는 연결된 객체 간의 관계를 표현하는 자료구조라고 할 수 있겠다. 방향 그래프와 무방향 그래프로 나눌 수 있는데, 더 자세한 내용은 추가로 포스팅하려고 한다.

그래프 탐색

그래프 탐색이란 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것이다.

이 글에서 설명하려는 DFS(Depth-First Search)는 그래프 탐색이다. 추후에 다룰 예정인 BFS(Breadth-First Search) 또한 마찬가지이다. 이외에도 다익스트라(Dijkstra), 플로이드 와샬(Floyd Washall)이 있다. 각 탐색 기법은 상황에 맞춰 적절한 것을 사용한다.

깊이 우선 탐색 DFS(Depth-First Search)

DFS 과정에 대해 자세히 설명하기 전, 이 이미지를 통해 간략히 알아보자. 노드 1을 시작으로 차례대로 노드 9까지 순회한다. 진행되는 방향을 보면 한 가지의 끝까지 탐색하고, 그 다음 가지를 순차적으로 탐색한다. 전체적 위에서 아래로 깊게 탐색이 진행되는 것을 볼 수 있다.

DFS란 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

예를 들면, 미로에서 한 루트로 계속 가다가 막다른 길이면 바로 직전 갈림길로 돌아가 길을 찾는 것이라고 할 수 있다. 깊이 우선 탐색은 전체 노드를 맹목적으로 탐색할 때 사용한다. 깊이 우선 탐색의 구현에서 중요한 것은 스택이다.

과정

위에서 사용한 트리형태의 그래프의 과정을 자세히 설명하고자 한다.

트리의 루트 노드인 노드 1을 기준으로 탐색을 시작한다. 스택 노드 1을 넣는다. 노드 1과 연결된 노드 중 방문하지 않은 노드가 있는지 확인한다.

아직 방문하지 않은 노드 2를 스택에 넣어준다. 다시 노드 2와 연결된 노드 중 방문하지 않은 노드가 있는지 확인한다.

노드 3을 스택에 넣어주고, 연결된 노드 중 방문하지 않은 노드가 있는지 확인한다.

그러나 노드 3과 연결된 노드는 노드 2뿐이며, 이미 방문했으므로 이번 분기의 탐색이 완료된 것이기 때문에 노드 3을 스택에서 빼낸다.

스택의 가장 위에 위치한 노드 2와 연결된 아직 방문하지 않은 노드가 있는지 확인한다. 그러나 존재하지 않기 때문에 노드 2를 스택에서 빼낸다.

앞의 과정을 계속 반복한다. 노드 1과 연결된 노드 중 방문하지 않은 노드 4를 스택에 추가하고, 노드 4와 연결된 노드 5를 다시 스택에 추가한다.

노드 5와 연결된 노드를 확인하고 방문하지 않은 노드 6을 스택에 추가한다.

노드 6와 연결된 노드를 확인한다. 방문하지 않은 노드가 없으므로 스택에서 제거한다. 노드 5도 마찬가지로 스택에서 제거한다. 노드 4와 연결된 또다른 노드를 확인한다.

노드 7을 스택에 추가한다. 연결된 노드 중 방문하지 않은 것이 없으므로 스택에서 제거하고, 노드 4 또한 모두 방문했으므로 스택에서 제거한다.

노드 1과 연결된 마지막 노드 8을 스택에 추가하고, 다음 노드를 탐색한다.

노드 9를 스택에 추가한다. 방문할 노드가 없으며, 노드 8 또한 마찬가지 이므로 스택에서 제거한다.

방문하지 않은 노드가 더이상 존재하지 않기 때문에 노드 1을 스택에서 제거해 탐색을 마친다.

👑 프로그래머스 문제에 적용해보자

프로그래머스의 DFS 문제의 풀이를 가볍게 해보려고 한다. 물론 문제에 대한 해결방법은 다양하니 그 중 하나로 여기길 바란다.

1) 여행경로

주어지는 tickets가 [["ICN","A"],["B","ICN"],["C","B"],["B","C"],["B","ICN"]] 이라면, 아래의 형태로 나타낼 수 있다.

이 문제는 ICN 노드를 루트 노드로 하여, 깊이 우선 탐색을 적용해 모든 티켓을 사용하는 방법을 찾아낼 수 있다. ICN 노드에서 A 노드를 먼저 방문하면 나머지 노드를 방문할 수 없으므로 답이 될 수 없다. 다음 분기에 B 노드를 먼저 방문하여 모든 티켓을 사용할 수 있으므로 ["ICN", "B", "C", "B", "ICN", "A"]가 답이 될 것이다.