큰 수 연산

숫자가 매우 큰 경우에 사칙연산을 수행하는 경우 변수의 범위를 초과한다.

따라서 문자열로 치환해 연산을 수행해줘야 한다.

각 언어별 큰수연산(정수, 실수) 연산 지원은 다음과 같다.

언어 큰 정수 큰 실수
Java java.math.BigInteger java.math.BigDecimal
Python int decimal.Decimal
Javascript bigint  
C++ cpp_int (boost) cpp_dec_float (boost)

일반적으로 배열의 성질을 이용해 구한다.

덧셈

string bigNumberAdd(string a, string b) {
  int carry = 0;
  string result = "";

  while (!a.empty() || !b.empty() || carry) {
    if (!a.empty()) {
      carry += a.back() - '0';
      a.pop_back();
    }

    if (!b.empty()) {
      carry += b.back() - '0';
      b.pop_back();
    }

    result += ((carry % 10) + '0');
    carry /= 10;
  }

  reverse(result.begin(), result.end());
  return result;
}

뺄셈

bool isSmaller(string a, string b) {
  int lengthA = a.length(), lengthB = b.length();

  if (lengthA < lengthB) {
    return true;
  }
  if (lengthB < lengthA) {
    return false;
  }

  for (int i = 0; i < lengthA; i++)
    if (a[i] < b[i]) {
      return true;
    } else if (a[i] > b[i]) {
      return false;
    }

  return false;
}

string bigNumberSub(string str1, string str2) {
  if (isSmaller(str1, str2)) {
    swap(str1, str2);
  }

  string result = "";
  int n1 = str1.length(), n2 = str2.length();

  reverse(str1.begin(), str1.end());
  reverse(str2.begin(), str2.end());

  int carry = 0;

  for (int i = 0; i < n2; i++) {
    int sub = ((str1[i] - '0') - (str2[i] - '0') - carry);

    if (sub < 0) {
      sub = sub + 10;
      carry = 1;
    } else
      carry = 0;

    result += (sub + '0');
  }

  for (int i = n2; i < n1; i++) {
    int sub = ((str1[i] - '0') - carry);

    if (sub < 0) {
      sub = sub + 10;
      carry = 1;
    } else {
      carry = 0;
    }

    result += (sub + '0');
  }

  reverse(result.begin(), result.end());
  return result;
}

CRA를 사용하지 않고 React 프로젝트 생성하기

CRA (create-react-app)는 매우 편리한 리액트 프로젝트 빌드 도구입니다.

Webpack, Babel 등 설정하기가 까다롭고 시간이 들어가는 작업을 한번에 해주니까요.

그러나 Babel 혹은 Webpack의 설정을 건드려야 할 경우, eject를 통해 숨겨져 있던 설정 파일들을 끄집어 내야 하는 번거로움이 존재합니다.

리액트 프로젝트를 생성할 때 Webpack과 Babel을 어떻게 구성해보는지 알아보기 위해서
한번 직접 리액트 프로젝트를 구성해 봤습니다.

다만 제가 구성한 방법으로는 Debugging에 몇몇 문제가 있어 실제 제작 프로젝트에는
CRA를 이용해 boiler plate를 생성하려고 합니다.

설치

이 프로젝트에서는 yarn을 사용합니다.

최초로 yarn init명령을 실행해 package.json 파일을 생성합니다.

yarn init -y

리액트의 핵심인 모듈들을 설치해줍니다.

이 때 build 이후에 module은 사용하지 않으므로 (개발환경에서만 사용하므로) devDependency로 설치합니다.

yarn add -D react react-dom

그리고 모듈 번들러인 Webpack을 설치합니다.

yarn add -D webpack webpack-cli webpack-dev-server

웹팩에 번들링에 필요한 바벨을 설치합니다.

yarn add -D babel-loader css-loader style-loader file-loader
  • babel-loader : JSX 및 ES6+ 문법을 트랜스파일링
  • css-loader : CSS 파일을 자바스크립트가 이해할 수 있도록 변환
  • style-loader : 변환된 CSS 파일을 style 태그로 감싸서 삽입
  • file-loader : 이미지 및 폰트 등의 파일 로딩

마지막으로 웹팩으로 번들링 할 때 필요한 플러그인들을 설치합니다.

  • html-webpack-plugin : HTML 파일에 번들링된 자바스크립트 파일을 삽입해주고 번들링된 결과가 저장되는 폴더에 옮겨줌
  • clean-webpack-plugin : 번들링을 할 때마다 이전 번들링 결과를 제거함
yarn add -D html-webpack-plugin clean-webpack-plugin

폴더 구조

이 보일러 플레이트에서 사용할 폴더들은 다음과 같습니다.

  • dist : 빌드된 파일들이 생성
  • src : 컴포넌트, 유틸 등 소스 파일들이 위치함
  • public : 빌드할 때 참고할 html 등 정적 파일

여기서 dist 폴더의 경우 build 명령을 수행할 때 자동으로 만들어 주므로 생성하지 않아도 괜찮습니다.

mkdir src public dist

바벨 설정

바벨 설정 파일인 babel.config.js 를 작성합니다.

module.exports = function (api) {
  api.cache(true);

  const presets = ["@babel/preset-env", "@babel/preset-react"];

  const plugins = [];

  return {
    presets,
    plugins,
  };
};

웹팩 설정

웹팩 설정 파일인 webpack.config.js 를 작성합니다.

const path = require("path");
const HtmlWebpackPlugin = require("html-webpack-plugin");
const { CleanWebpackPlugin } = require("clean-webpack-plugin");

module.exports = {
  mode: "development",
  entry: {
    main: "./src/index.js",
  },
  resolve: {
    extensions: [".js", ".jsx"],
  },
  devtool: "eval-cheap-source-map", // source-map을 설정하는 부분
  devServer: {
    contentBase: path.join(__dirname, "dist"), // 이 경로에 있는 파일이 변경될 때 번들을 다시 컴파일
    compress: true, // Enable gzip compression for everything served
    port: 8080, // 각자의 portNumber 작성
    hot: true, // 모듈의 변화된 부분만 자동으로 리로딩하는 HMR(Hot Module Replacement)
    overlay: true, // 에러가 발생했을 때 브라우저에 띄울 것인지
    writeToDisk: true, // 메모리 뿐만 아니라 직접 파일로 만들 것인지
    open: true, // Tells dev-server to open the browser after server had been started. Set it to true to open your default browser.
  },
  module: {
    rules: [
      {
        test: /\.(js|jsx)$/, // 컴포넌트 파일을 읽어오는 규칙입니다.
        exclude: "/node_modules/",
        loader: "babel-loader",
      },
      {
        test: /\.css$/, // 스타일 속성 파일을 읽어오는 규칙입니다.
        use: [{ loader: "style-loader" }, { loader: "css-loader" }],
      },
      {
        test: /\.jfif$/,
        loader: "file-loader",
        options: {
          name: "[name].[ext]",
        },
      },
    ],
  },
  output: {
    path: path.resolve(__dirname, "dist"),
    filename: "bundle.js",
  },
  plugins: [
    new CleanWebpackPlugin(),
    new HtmlWebpackPlugin({
      // index.html에 output에서 만들어진 bundle.js를 적용하여, dist에 새로운 html 파일 생성
      template: `./public/index.html`,
    }),
  ],
};

몇가지 중요한 속성을 살펴보겠습니다.

  • entry : 모듈의 의존성이 시작되는 부분으로 이름을 지정할 수 있고 여러개를 만들 수 있음.
  • resolve : 웹팩이 모듈을 처리하는 방식 정의하는 것으로 확장자를 생략하고도 인식하게 함.
  • devtool : 참고링크 source-map을 설정하는 부분으로 에러가 발생했을 때 번들링된 파일에서 어느 부분에 에러가 났는지를 쉽게 확인할 수 있게 해주는 도구.
  • devServer : webpack-dev-server의 옵션을 설정해주는 부분. 자세한 설명은 주석으로 작성했습니다.

package.json 에 script 추가

webpack-dev-server 에 --progress 옵션을 주는 경우, console에 결과가 나타납니다.

(Output running progress to console)

{
  "scripts": {
    "start": "webpack-dev-server --progress --mode development",

    "build": "webpack --progress --mode production"
  }
}

리액트 컴포넌트 생성

public 폴더에 다음과 같은 index.html 파일을 생성합니다.

<!DOCTYPE html>
<html lang="ko">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <meta http-equiv="X-UA-Compatible" content="ie=edge" />
    <title>리액트 프로젝트 시작</title>
  </head>
  <body>
    <div id="root"></div>
  </body>
</html>

src 폴더에 entry point 파일과 (index.js), 컴포넌트 파일을 생성합니다. (App.jsx)

// index.js
import React from "react";
import ReactDOM from "react-dom";
import App from "./App";

ReactDOM.render(<App />, document.querySelector("#root"));
// App.jsx
import React from "react";

const App = () => {
  return <div>hello world!</div>;
};

export default App;

실행

개발환경의 경우 다음 명령어를 통해 실행해 볼 수 있습니다.

yarn start

빌드

다음 명령어를 통해 빌드해 볼 수 있습니다.

yarn build

타입스크립트 개발 환경 구성해보기

우선 타입스크립트와, 타입 정의 파일들을 설치해야합니다.

yarn add -D typescript @types/react @types/react-dom

타입스크립트 명령어를 사용하면 typescript 설정 파일을 생성할 수 있습니다.

npx typescript --init

tsconfig.json 파일이 자동으로 생성됩니다.

여기서 리액트 jsx 코드를 사용하기 위해서는 compilorOptions의 jsx 속성에 "react" 값을 추가합니다.

{
  "compilorOptions": {
    "jsx": "react"
  }
}

Webpack으로 빌드하기 위해 ts-loader를 설치합니다.

yarn add -D ts-loader

그리고 Webpack 설정 파일에 다음 내용들을 추가합니다.

module.exports = {
  // 엔트리 포인트
  entry: "./src/index.tsx",

  // 빌드 결과물을 dist/main.js에 위치
  output: {
    filename: "main.js",
    path: __dirname + "/dist",
  },

  resolve: {
    // 파일 확장자 처리
    extensions: [".ts", ".tsx", ".js"],
  },

  module: {
    rules: [
      // .ts나 .tsx 확장자를 ts-loader가 트랜스파일
      { test: /\.tsx?$/, loader: "ts-loader" },
    ],
  },
};

'공부' 카테고리의 다른 글

Git Hooks + commitlint를 이용한 커밋 메시지 검사  (0) 2020.08.16

커밋 메시지 자동 검사

Git Hooks와 commitlint를 이용해 작성한 커밋 메시지가 유효한지 검사할 수 있습니다.

다음 글들을 참고하시면 더 많은 정보를 얻으실 수 있습니다.

 

 

Conventional Commits | 쿡앱스 기술 블로그

Conventional Commits 본 포스팅의 완성 된 예제 소스 는 GitHub에 올려져 있습니다. 개요 Conventional Commits 이란 git 으로 commit 시에 일괄된 양식을 유지하고 그 양식을 바탕으로 버전 관리나 Change Log 를 만

blog.cookapps.io

 

 

conventional-changelog/commitlint

📓 Lint commit messages. Contribute to conventional-changelog/commitlint development by creating an account on GitHub.

github.com

Git Hooks

 

 

Git - Git Hooks

It’s important to note that client-side hooks are not copied when you clone a repository. If your intent with these scripts is to enforce a policy, you’ll probably want to do that on the server side; see the example in An Example Git-Enforced Policy.

git-scm.com

프로젝트의 .git 폴더 내부는 다음과 같이 구성되어 있습니다.

├── COMMIT_EDITMSG
├── HEAD
├── ORIG_HEAD
├── config
├── description
├── hooks
├── index
├── info
├── logs
├── objects
└── refs

이 중 hooks 폴더에 들어가면 다음과 같은 sample 파일들을 만나게 됩니다.

├── applypatch-msg.sample
├── commit-msg.sample
├── fsmonitor-watchman.sample
├── post-update.sample
├── pre-applypatch.sample
├── pre-commit.sample
├── pre-merge-commit.sample
├── pre-push.sample
├── pre-rebase.sample
├── pre-receive.sample
├── prepare-commit-msg.sample
└── update.sample

각각의 파일들은 쉘 스크립트 파일들이며, .sample을 지울 경우 git의 각 과정에서 작동합니다.

이 중에서 commit-msg 파일을 작성해 commit message 작성 후 convention 검사를 진행할 수 있습니다.

정규표현식을 사용해서 commit 메시지 체크하기

# exit with an error
exit 1

각 과정에서 위와 같은 방식으로 종료할 경우, 그 commit (이 외에 다른 동작들도) 은 자동적으로 취소됩니다.

따라서 다음과 같은 sh 파일을 만들 수 있습니다.

config=commit-msg.config.json

# set variables
enabled=$(jq -r .enabled $config)
revert=$(jq -r .revert $config)
types=($(jq -r '.types[]' $config))
min_length=$(jq -r .length.min $config)
max_length=$(jq -r .length.max $config)

if [[ ! -f $config || ! $enabled ]]; then
    exit 0
fi

regexp="^("

if $revert; then
    regexp="${regexp}revert: )?(\w+)("
fi

for type in "${types[@]}"
do
    regexp="${regexp}$type|"
done

regexp="${regexp})(\(.+\))?: "

regexp="${regexp}.{$min_length,$max_length}$"

msg=$(head -1 $1)

if [[ ! $msg =~ $regexp ]]; then
  echo -e "\n\e[1m\e[31m[INVALID COMMIT MESSAGE]"
  echo -e "------------------------\033[0m\e[0m"
  echo -e "\e[1mValid types:\e[0m \e[34m${types[@]}\033[0m"
  echo -e "\e[1mMax length (first line):\e[0m \e[34m$max_length\033[0m"
  echo -e "\e[1mMin length (first line):\e[0m \e[34m$min_length\033[0m\n"

  # exit with an error
  exit 1
fi
// commit-msg.config.json

{
    "enabled": true,
    "revert": true,
    "length": {
        "min": 1,
        "max": 52
    },
    "types": [
        "build",
        "ci",
        "docs",
        "feat",
        "fix",
        "perf",
        "refactor",
        "style",
        "test",
        "chore"
    ]
}

위 스크립트는 json 파일로 설정을 읽어들여오고 정규표현식을 이용해 검사하는 코드입니다.

huscky & commitlint를 이용한 검사

git hook 을 트리거 하는 용도로 npm 모듈인 huscky를 사용할 수 있습니다.

commitlint의 경우 commit 에 대한 lint를 확인하여 성공/실패를 리턴합니다.

다음 명령을 .git 폴더가 있는 프로젝트의 root에서 실행해주세요

yarn add husky @commitlint/cli @commitlint/config-conventional -D

husky가 githook 을 덮어쓰기 때문에 husky 설정 이전에 repo를 먼저 초기화 해야 합니다.

그리고 package.json에 다음과 같은 내용을 추가합니다.

  "husky": {
    "hooks": {
      "commit-msg": "commitlint -E HUSKY_GIT_PARAMS"
    }
  },
  "commitlint": {
    "extends": [
      "@commitlint/config-conventional"
    ]
  }

위 명령은 husky에서 hooks가 일어났을 때, commit-message에서 commitlint를 검사한다는 내용입니다.

commitlint에서 extends로 node_modules 내부의 @commitlint/config-conventional 에 존재하는 index.js 파일에서 설정을 읽어 오는데요,

설정 파일은 다음과 같습니다.

module.exports = {
    parserPreset: 'conventional-changelog-conventionalcommits',
    rules: {
        'body-leading-blank': [1, 'always'],
        'body-max-line-length': [2, 'always', 100],
        'footer-leading-blank': [1, 'always'],
        'footer-max-line-length': [2, 'always', 100],
        'header-max-length': [2, 'always', 100],
        'scope-case': [2, 'always', 'lower-case'],
        'subject-case': [
            2,
            'never',
            ['sentence-case', 'start-case', 'pascal-case', 'upper-case'],
        ],
        'subject-empty': [2, 'never'],
        'subject-full-stop': [2, 'never', '.'],
        'type-case': [2, 'always', 'lower-case'],
        'type-empty': [2, 'never'],
        'type-enum': [
            2,
            'always',
            [
                'build',
                'chore',
                'ci',
                'docs',
                'feat',
                'fix',
                'perf',
                'refactor',
                'revert',
                'style',
                'test',
            ],
        ],
    },
};

package.json의 commitlint.extends 부분을 직접 작성한 옵션으로 변경하면, 프로젝트에 적합한 commit convention을 적용할 수 있습니다.

'공부' 카테고리의 다른 글

CRA를 사용하지 않고 React 프로젝트 생성하기  (0) 2020.08.16

최근 제작하려는 프로젝트에 WebRTC 기술을 적용해 보기로 했다.

 

기술 멘토님들과 상의한 결과, 생각보다 기술적으로 해결해야 하는 이슈들이 많았다.

 

따라서 이번 기회에 WebRTC의 기초를 잡아보려고 한다.

 


WebRTC는?

 

  • 웹 어플리케이션(+android & ios) 및 사이트들이 데이터를 브라우져끼리 주고 받을 수 있게 만든 기술
  • 음성, 영상 미디어 혹은 텍스트, 파일 등
  • 별도의 소프트웨어 필요하지 않음
  • p2p로 공유

 

일반적으로 화상 전송 (영상 + 음성) 에 사용한다고 알려져 있지만, 채팅에도 사용할 수 있다.

 

(데이터 형식에 제한이 크지 않다는 의미)

 

www.scaledrone.com/blog/webrtc-chat-tutorial/

 

WebRTC Chat Tutorial

This tutorial will teach you: The basics of WebRTC How to create a 1-on-1 text chat where users can enter their username and be assigned a random emoji avatar How to use RTCDataChannel to send peer to peer messages How to use Scaledrone realtime messaging

www.scaledrone.com

 

WebRTC의 프로토콜

철수와 영희가 연결을 한다고 했을 때 다음과 같은 문제들이 존재한다.

  • 연결을 시도하는 방화벽을 통과해야 한다.
  • 단말에 public IP가 없다면 유일한 주소값을 할당해야할 필요가 있다.
  • 실제 사용자는 private IP를 사용한다. (일반 가정에서)
  • 라우터가 peer간의 직접연결을 허용하지 않을 때에는?

NAT (network address translation)

NAT는 외부망과 분리하고 public 망과 private 망의 IP:Port 를 매핑해주는 것이다

 

IP 변환이라고 생각하면 된다.

앞서 설명한 문제들 중 일부는 우리가 NAT 환경을 사용하기 때문에 발생한다.

 

VoIP 도 그러하지만, WebRTC 역시 Peer 간 연결을 위해서 NAT 환경에 대한 고려가 필요하다.

 

브라우저가 peer를 통한 연결이 가능하도록 하게 해주는 ICE 프레임워크에서는 이러한 작업을 수행하기 위해 다음 서버들을 사용한다. (일부만 사용하기도 함)

 

STUN 서버 (Session Traversal Utilities for NAT)

TURN 서버 (Traversal Using Relays around NAT)

 

STUN 서버

(Simple Traversal of User Datagram Protocol Through Network Address Translators)

STUN은 네트워크 환경에서 Public 관점에서 종단에 Access 가능한 IP:Port를 발견하는 작업이다.

 

IETF RFC 5389에 정의된 네트워크 프로토콜/패킷 포맷으로, 공개 주소(public address)를 발견하거나 peer간의 직접 연결을 막는 등의 라우터의 제한을 결정하는 프로토콜이다.

 

STUN은 IP 종단을 연결하기 위해서

어떤 종단이 NAT/Firewall 뒤에 있는지를 판단하게 해준다.

어떤 종단에 대한 Public IP Address를 결정하고 NAT/FIrewall의 유형에 대해서 알려준다.

 

다음 그림을 보면 과정을 이해할 수 있다.

 

A 클라이언트는 A 클라이언트의 공개주소와 라우터의 NAT 뒤에 있는 클라이언트가 접근가능한지에 대한 답변을 위한 요청을 STUN서버에 보낸다.

 

STUN 은 다음 로직에 따라서 방화벽의 종류를 결정한다고 한다.

 

내부적으로 판별하는 로직

위 로직을 보면 알겠지만, UDP 프로토콜을 사용하는 것을 알 수 있다.

UDP는 연결을 설정하지 않고 수신자가 데이터를 받을 준비를 확인하는 단계를 거치지 않고 단방향으로 정보를 전송한다. (일단 전송해본다)

 

STUN서버는 패킷의 IP 헤더와 UDP 헤더의 값(클라이언트의 공인 주소)과 STUN 메시지 안에 있는 STUN 클라이언트의 IP 주소와 UDP 포트 넘버 (클라이언트의 사설 주소)를 비교한다.

 

STUN 서버는 두 개의 서로 다른 주소에 대한 바인딩 테이블을 생성해 연결을 맺어준다.

 

TURN (Traversal Using Relays around NAT)

Peer간 직접 통신이 실패할 경우 종단점들 사이에 데이터 릴레이를 수행하는 TURN 서버들을 사용해 우회한다.

 

직접 연결이 불가능해 TURN 서버를 통해 통신하는 구조

TURN 서버와 연결하고 모든 정보를 그 서버에 전달하는 것으로 Symmetric NAT 제한을 우회한다.

 

  1. 이를 위해 TURN 서버와 연결을 한 후
  2. 모든 peer들에게 저 서버에 모든 패킷을 보내고
  3. 다시 나에게 전달해달라고 요청한다.

이는 오버헤드가 발생하므로 이 방법은 다른 대안이 없을 경우만 사용하는 방식이다.

 

TCP / UDP

RTCDataChannel은 UDP와 유사한 신뢰성 없는 방식(mode)과 TCP와 유사한 신뢰성 있는 방식 둘 중 하나로 동작할 수 있다.

 

UDP Hole Punching

앞서 말한 NAT 환경에서 연결을 위해 사용하는 방법 중 하나이다.

 

방법 중 하나로 STUN을 사용하기 때문에 앞서 STUN과 TURN 을 설명했다.

 

Hole-Punching 기술 유형은 다음과 같다

기술 설명
Relaying Client 1 → NAT A → Server → NAT B → 2
C-S 모델 연동
Connection Reversal 1 → 2 시 NAT
2 → 1 시 R서버
STUN 서버로부터 Client에 맵핑된 공인 IP 정보 수집
Hairpin 기법 Client A, B는 Server에 NAT 정보 저장
통신 시 A → NAT → B로 전송
Internal 네트워크 Client A, B는 Server에 NAT 정보 저장
통신 시 A → Local Broadcast → B

대규모 연결

사실 WebRTC 방식으로 P2P로 사용자들끼리 연결하는 경우에 소규모인 경우는 문제가 없다.

 

그러나 만약  p2p로 여러 사용자를 연결하는 모두 경우에는 각 peer당 연결해야 되는 peer의 수가 많아져 높은 부하 (인코딩 등)를 감당하게 된다.

Server based
full mesh p2p

그래서 실제 서비스를 운영할 때는 위 두 방식을 부분적으로 조합해 사용한다.

 

전부 연결되었지만, 간선의 수가 full mesh보다 적다

 

 


최큰 카카오 엔터프라이즈가 리모트 몬스터라는 기업을 인수했다.

 

https://www.hankyung.com/it/article/2020052682471

 

카카오엔터, 56억에 리모트몬스터 인수

카카오엔터, 56억에 리모트몬스터 인수, 홍윤정 기자, 산업

www.hankyung.com

리모트몬스터는 WebRTC 방송통신 기술 전문 기업이다. 역으로 말하면 WebRTC 기술을 사용할 때 부하 등 인프라 구조에 대한 깊은 이해도가 필요하다는 의미일것이다.

 

 

출처

http://www.authorstream.com/Presentation/kangsik-3609452-webrtc/

 

하이퍼커넥트-스타트업 핵심기술로서의 Webrtc(�

2018년 11월 1일, RTC KOREA 2018 컨퍼런스에서 하이퍼커넥트가 발표한 내용입니다.- authorSTREAM Presentation

www.authorstream.com

https://alnova2.tistory.com/1110

 

[WebRTC] STUN 과 TURN 에 대하여 #1 - 개요

 VoIP 도 그러하지만, WebRTC 역시 Peer 간 연결을 위해서 NAT 환경에 대한 고려가 필요하다. 이를 위해서 IETF에서 표준을 정의한 것이 바로 STUN과 TURN, 그리고 ICE 이다. 1. NAT에 대하여 NAT는 외부망과 ��

alnova2.tistory.com

https://www.slideshare.net/nurinamu/web-rtc-in-2014

 

WebRTC in 2014

Review the WebRTC issues & news and forecast the future WebRTC industry. This slide is used in GDG Seoul Monthly Meetup at 22th Jan, 2014.

www.slideshare.net

 

7699. 수지의 수지 맞는 여행

링크

난이도 : d4
정답률 : _51%

설계

자료구조

이미 방문한 알파벳은 방분하지 않으므로 visited['Z' - 'A'] 를 만들어 사용한다.

backtracking

이미 정답의 max를 구한 경우, 더이상 탐색하지 않아도 된다.

가능한 max의 경우는 입력된 지도의 알파벳 종류 + 1이다.

따라서 dfs 함수에 다음 코드를 추가해준다

if (answer > MAX) {
  return;
}

정리

내 코드 빠른 코드
18 ms 18 ms

내 코드가 제일 빠른 코드이다.

고생한 점

처음에 BFS로 풀려고 한 경우 계속 시간초과가 발생했다.

DFS로 바꾼 뒤 완전탐색을 수행했을 때 약 3초정도의 시간이 걸렸다.

코드

#include <algorithm>
#include <iostream>

using namespace std;

struct axis {
  int y, x;
};

axis moves[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char map[20][20];
int answer, R, C, MAX;
bool visited['Z' - 'A'];

void clear() {
  for (int i = 0; i < 'Z' - 'A'; i++) {
    visited[i] = 0;
  }
  answer = 1, MAX = 0;
}

void dfs(axis current, int count) {
  answer = max(answer, count);

  if (answer > MAX) {
    return;
  }

  visited[map[current.y][current.x] - 'A'] = 1;

  for (int dir = 0; dir < 4; dir++) {
    axis next = current;
    next.x += moves[dir].x;
    next.y += moves[dir].y;

    if (next.y < 0 || next.y >= R || next.x < 0 || next.x >= C ||
        visited[map[next.y][next.x] - 'A']) {
      continue;
    }

    dfs(next, count + 1);
  }

  visited[map[current.y][current.x] - 'A'] = 0;
}

void solution(int test_case) {
  clear();
  cin >> R >> C;

  bool alphabets['Z' - 'A'] = {
      0,
  };

  for (int y = 0; y < R; y++) {
    for (int x = 0; x < C; x++) {
      cin >> map[y][x];
      alphabets[map[y][x] - 'A'] = 1;
    }
  }

  for (bool b : alphabets) {
    b ? MAX += 1 : MAX;
  }

  dfs(axis{0, 0}, 1);

  cout << "#" << test_case << " " << answer << "\n";
}

int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int T;
  cin >> T;

  for (int test_case = 1; test_case <= T; test_case++) {
    solution(test_case);
  }

  return 0;
}

'공부 > 알고리즘 문제풀이' 카테고리의 다른 글

백준.1197.최소 스패닝 트리  (0) 2021.01.24
큰 수 연산 (Big Integer)  (0) 2021.01.04
삼성 9088. 다이아몬드  (0) 2019.12.27
삼성 8458. 원점으로 집합  (0) 2019.12.03
삼성 8934. 팰린드롬 공포증  (0) 2019.12.02

+ Recent posts