Node.js 의 특징과 한계

🤗 Node.JS 등장하다!!

초기 웹 페이지는 지금처럼 동적이지 않고 정적이었습니다. 그런데 동적으로 좀 움직이면 좋겠는데.. 하고 나온 것이 Javascript 입니다. Javascript Javascript 는 브라우저의 자바스크립트 엔진을 통해 DOM Context 를 제어하며 동적인 웹페이지를 만들 수 있었습니다.

시간이 흘러 2008 년 구글이 크롬을 발표하면서 V8 자바스크립트 엔진을 만들게 됩니다. 이전과는 다르게 상당한 수준의 퍼포먼스를 보이며 자바스크립트를 다른 분야에 적용하자는 의견이 생기기 시작했습니다. 이후 CommonJS 표준이 발표되고 곧바로 CommonJS 와 V8 엔진을 기반으로 Node.js 가 탄생합니다.

😊 Node.js 가 빛나기 시작했어!!

Node.js 는 다음과 같은 특징을 가지고 있습니다.

• None Blocking
• Event Driven
• Data Intensive
• I/O Intensive

사실 위의 특징 모두 Node.js 의 비동기 이벤트 기반 아키텍처 때문입니다.

😃 쓰레드 기반 vs 비동기 이벤트 기반

Node.js 가 개발된 배경과 목적에는 다수의 연결을 효율적으로 관리하고 비용을 최소화 할 수 있는 방법을 제시하는 것이 있었습니다. 이를 설명하기 위해 기존의 Multi Thread 환경에 대해서 알아봅시다.

Multi Thread 기반의 서버는 클라이언트가 웹 서버에 요청을 하게 되면 서버에서는

• 일정한 메모리 공간을 사용해 새로운 Thread 를 생성하거나 또는
• Thread pool 에서 적당한 Thread 를 해당 요청에 할당하게 됩니다.

이 할당된 Thread 는 해당 요청이 완료될 때 까지 이 요청에 할당됩니다. 하지만 실제로 코드가 수행되는 속도와 I/O 장치의 수행 속도가 다르기 때문에 Blocking I/O 에 대한 문제가 생기게 됩니다.

Blocking I/O 자체가 발생시키는 문제는

• I/O 요청을 하고 응답이 올 때까지 아무것도 하지 않고 시간을 낭비하는 것과
• 스케쥴링 처리와 문맥 전환시 CPU 연산이 필요하기 때문에

쓰레드가 많아질 수록 이로 인한 성능 저하가 일어난다는 것 입니다.

Node.js 는 Single Thread 기반으로 작동합니다.

뭐 ?? Single Thread 면 요청 기다리는 동안 아무것도 못하잖아!!

오.. 오해입니다!!

Node.js 는 Single Thread 기반 비동기 처리 방식 으로 구동됩니다.

Node.js 는

• I/O 작업 처리에 대한 응답을 기다리지 않고 바로 다음 작업을 실행합니다.
• 대신 I/O 작업이 종료되면 이벤트를 발생시키고,
• 이 이벤트는 해당 프로세스의 이벤트 큐에 등록되게 됩니다.
• 노드가 이 이벤트 큐를 주기적으로 계속 감지하여 해당 이벤트 이후 수행해야 할 작업을 하게 됩니다.

이벤트 루프 는 작업을 요청하면서 그 작업이 완료되었을 때 어떤 작업을 진행할지에 대한 콜백함수를 지정하여 동작이 완료되었을 때 해당 콜백함수를 실행하는 동작 방식을 말합니다. 만약 HTTP 요청이 서버에 오면 이벤트 루프는 이를 감지하고 적당한 Worker Thread 를 생성하여 해당 요청을 할당한 후 다른 요청을 기다리게 됩니다.

다시 말해 이벤트 루프는 어떤 요청이 발생하면 그 작업에 대해 쓰레드 실행만을 일으킬 뿐입니다. 이후 작업을 할당받았던 해당 쓰레드가 모든 작업을 마치면 미리 전달받은 콜백 함수를 실행하도록 이벤트 루프로 응답하게 되며 이벤트 루프는 이것을 실행하여 클라이언트에게 결과를 응답해줍니다.

🙀 Node.js 의 한계

Node.js : Culculte Intensive 한 분야는 자신 없어!!

다음과 같은 상황을 봅시다.

let count = 0;
for (let i = 0; i < 100000000; i++) count++;

감이 오십니까??

다시 말하자면 Node.js 는 Single Thread 기반입니다. 위 상황과 같이 긴 시간이 필요한 연산이 있으면 거기서 Block 이 됩니다.

반면 Multi Thread 기반의 어떤 Thread 가 위와 같은 요청을 받고 연산을 한다해도 여러 Thread 가 있으니 다른 요청을 받을 수 있습니다.

Thread 는 시분할 또는 특정 조건에 해당하는 기간동안 수행되고 Context Switching 을 통해 작업을 미루게 됩니다.

따라서 단순히 연산에 집중적인 분야에 대해서는 Node.js 가 아닌 다른 언어 다른 코드로 작성하는 방법으로 우회하시는게 좋습니다.

😭 마치며

사실 Node.js 환경을 사용하면서, 단순히 백엔드랑 프론트엔드 둘 다 사용가능하니까 !! 라는 지식만 가지고

왜 Node.js 가 무엇을 목적으로 탄생했는지 어떤점에 강점을 가지는지에 대해서는 몰랐던것 같습니다. 생각보다 Performance 도 훌륭하다는 것에 놀랐고 Single Thread 의 비동기 이벤트 기반 수행과정에 다시 놀랐습니다. 최소한 왜 쓰는지 이 환경의 장점이 무엇인지는 아는 것이 중요한 것 같습니다.

Node.js 직군 면접을 보면서 특히 더 많이 느꼇습니다.

추가로, Node.js 도 어떤 부분에서는 Multi Thread 요소를 쓰기도 합니다. 이 부분에 대해서는 다른 내용과 함께 더 좋은 정보를 가지고 다시 찾아뵙겠습니다.!!

출처

• https://zbulletjournal.tistory.com/85
• https://m.blog.naver.com/hhw1990/221394005779
• https://www.youtube.com/watch?v=UCd6LorxpkY&list=PLqq-6Pq4lTTa-d0iZg41U2RDqECol9C5B&index=6
• https://sjh836.tistory.com/149
• https://edu.goorm.io/learn/lecture/557/%ED%95%9C-%EB%88%88%EC%97%90-%EB%81%9D%EB%82%B4%EB%8A%94-node-js

NestJS 블로그 만들기 - 데이터베이스 연결

2. NestJS 블로그 만들기 - 데이터베이스 연결 (Postgresql)과 User 모듈

저는 오늘 포스팅할 분량의 앱을 만든 후 블로그 포스팅하기 때문에 중간에 오류가 생길 수도 있습니다. 오류 내용과 함께 댓글을 달아주시면 저도 알아보겠습니다!!

👌 데이터 베이스 연결하기 !!

PostgreSQL 설치!!

여러분 드디어 데이터베이스에 연결할 시간이 왔습니다!!. 실제 연습할 때는 배열 같은 임의 적인 놈을 만들고 나서 하긴하지만… 바로 연결해보죠!

저희는 Postgresql 을 사용할 겁니다!! 다른 데이터베이스를 사용하셔도 됩니다!!

Postgresql 은 오픈소스 데이터베이스로 SQL 표준을 잘 지원합니다. 일단 무료입니다!! 설치하는 방법은 정식 문서나 타 블로그 포스트를 참조해주세요. postgresql 설치방법

편의를 위해 pgAdmin 툴을 이용하여 postgresql 을 제어하겠습니다.!!

기존의 서버 (PostgreSQL 13 이군요 저는) 를 우클릭하여 데이터베이스를 만듭시다!! 저는 데이터베이스 이름을 nest_blog 라고 했습니다!!

원하시는 서버를 만들고 데이터베이스를 생성하셔도 괜찮습니다.

데이터베이스의 스키마 구조에 대해서는 아직 정의하지 않겠습니다. NestJS가 해줄거거든요!!

TypeORM !!

TypeORM 은 NodeJS 환경에서 사용할 수 있는 ORM (Object Relational Mapping) 라이브러리 입니다!!

ORM 은 간단히 말해 Object 를 Database 스키마에 적절하게 적용시키게 해주는 기능이라 생각하면 편합니다.!!

설치 설치~ nestjs 루트 폴더에서 다음 명령어로 설치해주세요 !!

   $ npm install typeorm @nestjs/typeorm --save

설치가 됬으면 ormconfig.json 이라는 파일을 루트 폴더에 만들어 줍니다. 나중에 TypeORM 모듈이 이 파일을 참고해 데이터베이스에 연결을 시도합니다!!

다음과 같이 입력해주세요!!

{
  "type": "postgres",
  "host": "localhost",
  "port": 5432,
  "username": "postgres",
  "password": 여러분이 설정했던 비밀번호!,
  "database": "nest_blog",
  "entities": ["dist/**/**.entity{.ts,.js}"],
  "synchronize": true
}

• type : 우리가 사용하게 될 데이터베이스 시스템을 나타냅니다.
• host : db 연결 주소입니다. 기본적으로 localhost 를 이용하고 db 를 다른 머신에서 실행한다면 그 머신에 접속하기 위한 주소로 변경해주시면 됩니다.
• port : db 연결 포트 입니다. 기본은 5432 입니다.
• username : 별 다른 설정을 안했다면 postgres 입니다
• password : 설치 과정에서 설정했던 비밀번호를 입력하세요.
• database : 위에서 만들었던 데이터베이스의 이름을 입력하시면 됩니다. 저는 nest_blog 라고 했습니다.
• entities : 반드시 dist 아래의 폴더로 지정해주세요. 안그러면 오류날 수도 있습니다. 이 설정의 경로에 있는 파일을 참고하여 DB 에서 스키마를 설정하게 됩니다.
• synchronize : 이 설정을 true 로 하시면 앱 작동시 DB 스키마가 자동으로 생성되게 됩니다.

자세한 내용은 ormconfig 탐방하기!! 을 참조해주세요~

app 모듈에서 import !! 그리고 실행!!

자 이제 app.moudle.ts 파일로 가서 TypeOrmMoudle 을 import 해줍시다!!

@Module({
  imports: [UsersModule, TypeOrmModule.forRoot()],
  controllers: [AppController],
  providers: [AppService],
})
export class AppModule {}

ormconfig.json 파일을 생성하지 않았다면, forRoot 함수 안에 설정 내용을 적으셔야 합니다.!! 파일로 관리하는게 더 편하겠죠~?

자 이제 루트 폴더에서 다음과 같은 명령어를 수행해봅시다!

$ npm run start

별 다른 오류가 없다면 정상적으로 연결 된겁니다!! 우라하!!! 저희는 아직 Entity에 대해서 설정을 하지 않았기 때문에 테이블에 별 내용은 없습니다.

이후에 Entity 를 만든 후에는 DB 에서 테이블을 삭제하고 다시 연결해주시면 만든 내용이 적용됩니다!

🛴 User Entity 만들기.

톡.

DB 도 연결했겠다.

톡톡.

User Entity Template 도 생성했겠다.

톡톡.

내용만 넣으면 되네?

짝!

src/users 안의 구조를 다음과 같이 해주세요!! spec 파일들은 지금 없어도 됩니다.

users
│  users.repository.ts
│  users.controller.spec.ts
│  users.controller.ts
│  users.entity.ts
│  users.module.ts
│  users.service.spec.ts
│  users.service.ts
│
└─dto
        create-user.dto.ts
        index.ts
        update-user.dto.ts

우리는 User 의 요구사항 맞게 적절히 Entity 를 설계해야 합니다. 왜냐면 이 안에 있는 내용이 데이터베이스 테이블 스키마로 적용될 녀석들이거든요!!

요구사항보기

바로 모든 요구사항을 만족시키기는 복잡하니 할 수 있는거 먼저 채워 나갑시다!!

users.entity.ts 안을 다음과 같이 채워주세요!!

import { BeforeInsert, Column, Entity, PrimaryGeneratedColumn } from "typeorm";
import * as argon2 from "argon2";

@Entity("user")
export class UserEntity {
  @PrimaryGeneratedColumn()
  id: number;

  @Column({ length: 32 })
  username: string;

  @Column({ unique: true })
  email: string;

  @Column()
  password: string;

  @BeforeInsert()
  async hashPassword() {
    this.password = await argon2.hash(this.password);
  }

  @Column({ default: "" })
  imageLink: string;
}

• @Entity : 이 annotation 이 있으면 nestjs가 보고 있다가 DB 스키마 적용을 위해 참고하게 됩니다!! 이후 repository 클래스에서도 참고할 수 있는 클래스가 됩니다. 괄호안에 넣은 내용이 테이블의 이름이 됩니다.
• PrimaryGeneratedColumn : 이 annotion이 있다면 이 테이블은 해당 필드가 primary key 가 됩니다. 괄호 안에 아무런 내용을 넣지 않으면 id 는 auto increment 가 적용됩니다.

  uuid vs auto increment

• Column : 이 annotion 이 있으면 테이블의 필드로 만들어지게 됩니다. 괄호 안에 여러 옵션을 넣을 수 있습니다. 모든 괄호 안의 옵션 보기
• BeforeInsert : 요 녀석은 데이터베이스에 insert 하기 전에 수행되는 녀석입니다. 비밀번호를 복호화 할 수 없게 hash 함수를 이용해 저장합시다.

아참 해쉬 함수를 쓰기 위해 argon2 를 설치해야 합니다.

$ npm install argon2 --save

🔨 Repository 와 Dto 변경하기!

Repository

Repository 는 우리가 만든 Entity 를 관리(insert, update, delete, load, etc.)해줄 녀석이라고 보시면 됩니다.

users.repository.ts 안의 내용을 다음과 같이 채워주세요!!

import { EntityRepository, Repository } from "typeorm";
import { UserEntity } from "./users.entity";

@EntityRepository(UserEntity)
export class UserRepository extends Repository<UserEntity> {}

엥? 이것만 해도 되는건가??

• 네!!

이렇게 Repository 를 만들어주시면 UserEntity에 대해 기본적인 쿼리를 그냥 쓸 수 있습니다. 복잡한 쿼리는 여기서 만들어주셔도 되고 이후 나올 query builder 로 해당 클래스에서 쓰셔도 됩니다!

DTO

DTO(Data Transfer Object) 는 데이터가 어떤 구조로 전송되는지에 대한 정보를 담고 있는 클래스 입니다.

dto 폴더 안에 create-user.dto.ts 폴더에 다음과 같이 작성해주세요

import { IsNotEmpty } from "class-validator";

export class CreateUserDto {
  @IsNotEmpty()
  readonly username: string;

  @IsNotEmpty()
  readonly email: string;

  @IsNotEmpty()
  readonly password: string;
}

class-validator 는 data 가 전송될 때 해당 필드가 적절한 유효성을 가지는지 검사해주는 라이브러리 입니다.

자 이제 Service 만 바꾸면 됩니다!!

🤗 User Service 변경하기!!

자 구조는 준비 되었습니다. 이제 로직만 잘 작성해주면 됩니다 화이팅!!

먼저 의존성 주입을 위해 UserService 생성자에 다음과 같이 적어줍시다!

constructor(private readonly userRepository: UserRepository) {}

자 이것 만으로 객체가 주입됬습니드어어어!! 얼마나 좋아~!

User create

users.service.ts 파일 내에 create 함수 안을 다음과 같이 바꿔주세요!

  async create(createUserDto: CreateUserDto) {
    const { username, email, password } = createUserDto;
    const getByUserName = getRepository(UserEntity)
      .createQueryBuilder('user')
      .where('user.username = :username', { username });

    const byUserName = await getByUserName.getOne();
    if (byUserName) {
      const error = { username: 'UserName is already exists' };
      throw new HttpException(
        { message: 'Input data validation falied', error },
        HttpStatus.BAD_REQUEST,
      );
    }
    const getByEmail = getRepository(UserEntity)
      .createQueryBuilder('user')
      .where('user.email = :email', { email });

    const byEmail = await getByEmail.getOne();
    if (byEmail) {
      const error = { email: 'email is already exists' };
      throw new HttpException(
        { message: 'Input data validation falied', error },
        HttpStatus.BAD_REQUEST,
      );
    }
    // const thisUser = this.userRepository.findOne({ username: username });
    // const thisEmail = this.userRepository.findOne({ email: email });

    // create new user
    let newUser = new UserEntity();
    newUser.email = email;
    newUser.password = password;
    newUser.username = username;
    const validate_error = await validate(newUser);
    if (validate_error.length > 0) {
      const _error = { username: 'UserInput is not valid check type' };
      throw new HttpException(
        { message: 'Input data validation failed', _error },
        HttpStatus.BAD_REQUEST,
      );
    } else {
      return await this.userRepository.save(newUser);
    }
  }

먼저 username 과 email 은 유일해야 하기 때문에 이를 검사해보죠!!

먼저 살펴볼 것은 createQueryBuilder 입니다. typeorm 은 createQueryBuilder 라는 함수를 통해 코드 안에서 SQL 문을 작성할 수 있게 해줍니다. 이 코드로 인해 작성된 sql 문은 바로 실행되는 것이 아니라 실질적으로 DB 와 데이터 교환이 일어나면 실행 됩니다.

맨 처음 만든 SQL 문은

const byEmail = await getByEmail.getOne();

여기서 수행 됩니다. DB 의 쿼리 속도와 우리가 만든 백엔드 서버에서 코드를 실행하는 속도 차이가 많이 나기 때문에 비동기 식으로 수행했습니다.

마찬가지로 username 도 검사해줍시다!!

사실 이 기능은 createQueryBuilder 를 안써도 됩니다. Repository 를 작성했으므로 기본적인 기능은 이미 지원이 되기 때문입니다. 예들 들어 username 을 기준으로 가져오고 싶다면 다음과 같이 적으면 됩니다.

const user = this.userRepository.findOne({ username: username });

이해를 돕고자 createQueryBuilder 를 사용했습니다

마찬가지로 findByEmail 함수를 다음과 같이 사용하시면

  async findByEmail(email: string) {
    return await this.userRepository.findOne({ email });
  }

email 기준으로 유저를 찾을 수 있습니다!!

🔨 Module 에 import 해주기!!

자 거의 다 왔습니다!!

users.module.ts 파일 안에 imports 부분에 다음과 같이 모듈을 import 해줍시다!!

@Module({
  imports: [TypeOrmModule.forFeature([UserRepository])],
  controllers: [UsersController],
  providers: [UsersService],
  exports: [UsersService],
})
export class UsersModule {}

😃 이제 실행된다!!

$ npm run start

위 명령어를 통해 어플리케이션을 실행을 합시다. 오류가 없다면 다음과 같이 로그가 뜹니다!!

[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [NestFactory] Starting Nest application...
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [InstanceLoader] TypeOrmModule dependencies initialized +97ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [InstanceLoader] AppModule dependencies initialized +1ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [InstanceLoader] TypeOrmCoreModule dependencies initialized +213ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [InstanceLoader] TypeOrmModule dependencies initialized +1ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [InstanceLoader] UsersModule dependencies initialized +1ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [RoutesResolver] AppController {}: +14ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [RouterExplorer] Mapped {, GET} route +18ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [RoutesResolver] UsersController {/users}: +10ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [RouterExplorer] Mapped {/users, POST} route +7ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [RouterExplorer] Mapped {/users, GET} route +3ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [RouterExplorer] Mapped {/users/:email, GET} route +1ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [RouterExplorer] Mapped {/users/:id, PUT} route +11ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [RouterExplorer] Mapped {/users/:id, DELETE} route +1ms
[Nest] 33080   - 2021-02-01 2:36:58 ├F10: PM┤   [NestApplication] Nest application successfully started +2ms

우후 우후~ 우후~ 우후~ 성공!! 고생하셨습니다.

🤣 아직 테스트가 남았다!!!

저는 Rest Client 라는 vscode extension 을 이용하여 테스트를 진행했습니다. postman, curl 여러분이 편하신 툴을 이용해주세요!!

자 다음과 같이 요청을 하면!

    POST http://localhost:3000/users HTTP/1.1
    Content-Type: application/json

    {
        "username": "manynang",
        "email" : "nono@cat.co.kr",
        "password" : "manyang"
    }

다음과 같이 데이터가 출력이 됩니다!!

    HTTP/1.1 201 Created
    X-Powered-By: Express
    Content-Type: application/json; charset=utf-8
    Content-Length: 179
    ETag: W/"b3-G/i5vHuN9KZDYAV9wTSwyMToetE"
    Date: Mon, 01 Feb 2021 05:41:10 GMT
    Connection: close

    {
    "email": "nono@cat.co.kr",
    "password": "$argon2i$v=19$m=4096,t=3,p=1$LthoEnjA4KlaeaE/8YhMPg$2bNUqzjlCqbomBtDTkcYzTHjibaSrjefgJDzJWTvGFQ",
    "username": "manynang",
    "id": 1,
    "imageLink": ""
    }

웁스 .. 비밀번호가 나오는군요… 이래서 테스트가 중요한겁니다.

저희는 유저 id만 가져오도록 하겠습니다. UserCreate save 하는 부분을

return await this.userRepository.save(newUser).then((v) => v.id);

이와 같이 바꿔줍시다.

    HTTP/1.1 201 Created
    X-Powered-By: Express
    Content-Type: text/html; charset=utf-8
    Content-Length: 1
    ETag: W/"1-NWoZK3kTsExUV00Ywo1G5jlUKKs"
    Date: Mon, 01 Feb 2021 05:50:44 GMT
    Connection: close

    1

자 성공!

자 다시 위에 POST 관련 문을 다시 보내면?

    HTTP/1.1 400 Bad Request
    X-Powered-By: Express
    Content-Type: application/json; charset=utf-8
    Content-Length: 92
    ETag: W/"5c-j/u2GjtMeXEpPJw+5WWgYELKwpM"
    Date: Mon, 01 Feb 2021 05:54:56 GMT
    Connection: close

    {
    "message": "Input data validation falied",
    "error": {
        "username": "UserName is already exists"
    }
    }

성공~~!!!! 중복된 username 을 걸렀습니다 ㅜㅜ!!

고생했습니다 ㅜㅜ!!!!

다음에는 위 코드를 Refactor 하는 과정으로 찾아뵙도록 하겠습니다!! 오늘도 즐거운 하루 보내세요!!

피드백은 항상 환영입니다.

leetcode Jump Game II 문제풀기

#[leetcode][45] Jump Game II 문제풀기!

• 문제풀러가기✈

👓 문제 요약

처음 인덱스에서 마지막 인덱스에 도달하려면 몇 번 점프해야할까? 해당 인덱스에서 최대 얼마나 뛸 수 있는지는 알려줄게!

자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기

🔑 문제 풀이

주어지는 인풋의 길이가 최대 30,000 이기 때문에 최소 O(nlgn) 기법을 써야 합니다!

저는 탐욕 기법으로 해당 인덱스에서 뛰었을 때 최대로 가는 놈만 골라서 그냥 뛰었습니다!

🥽 소스코드 및 소스해석

var jump = function (nums) {
  if (nums.length === 1) return 0;
  if (nums[0] >= nums.length - 1) return 1;
  let nowPos = 0;
  let count = 0;
  for (let i = 0; i < nums.length; ) {
    let maxNum = 0;
    for (let dist = 1; dist <= nums[i]; dist++) {
      if (maxNum <= dist + nums[i + dist] || dist + i >= nums.length - 1) {
        maxNum = dist + nums[i + dist];
        nowPos = i + dist;
      }
    }
    i = nowPos;
    count++;
    if (nowPos >= nums.length - 1) {
      break;
    }
  }
  return count;
};

🔨 문제 후기

왜 hard 난이도 인지 알 수 없는 문제!! 끄앗!!!

leetcode Wildcard Matching 문제풀기

#[leetcode][44] Wildcard Matching 문제풀기!

• 문제풀러가기✈

👓 문제 요약

간단한 정규식 패턴을 줄게.

• ’?’ 이건 하나의 문자를 대체할 수 있는 놈이야.
• ’*‘ 임마 이거는 빈 문자를 포함해서 문자열을 대체할 수 있는 놈이야.

자 이제 내가 문자열을 줄테니까 이전에 준 패턴으로 만들 수 있는 놈인지 판단해줘!

자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기

🔑 문제 풀이

문제에서 문자열의 길이와 패턴의 길이가 최대 2,000 이기 때문에 O(n^2) 으로도 가능한 문제입니다!!

저는 DP 기법으로 풀었습니다.

dp[i][j] 는 0 ~ i - 1 까지의 패턴으로, 0 ~ j - 1 까지의 문자열을 만족할 수 있는지에 대한 정보를 나타냅니다.

이 문제의 경우 패턴의 인덱스가 0 이거나 문자열의 인덱스가 0 인 경우에 대한 처리가 복잡해질거 같아서

인덱스를 하나씩 더 써서 사용 했습니다. 즉 dp[0][0] 은 패턴 0개, 문자열 0개를 사용했을 때를 나타냅니다.

검사하려는 i - 1 의 패턴이 ’*‘ 인 경우와 ’?’ 또는 알파벳문자 인 경우로 나누었습니다.

• ’*‘ 인 경우 : 이 경우는 즉 현재 패턴을 뺀 경우 또는 현재 검사하려는 문자열에서 마지막 문자를 뺀 경우가 만족하면 true 입니다. -> dp[i - 1][j] 또는 dp[i][j - 1] 가 true 이면 dp[i][j] 는 true
• ’?’ 또는 알파벳문자 인 경우 : 이 경우는 현재 패턴과 검사하려는 문자열의 마지막 문자를 뺀 경우 만족하면 true 입니다. -> dp[i - 1][j - 1] 가 true 이면 dp[i][j] 는 true

🥽 소스코드 및 소스해석

var isMatch = function (s, p) {
  //remove consecutive star e.g) **
  if (p.length === 0 && s.length === 0) return true;
  if (p.length === 0) return false;
  let patternTemp = new Array();
  for (let i = 0; i < p.length; i++) {
    while (i + 1 < p.length && p[i] === "*" && p[i + 1] === "*") i++;
    patternTemp.push(p[i]);
  }

  p = patternTemp;
  // dp[i][j] measn from p[0] ~ p[i]
  let dp = new Array(p.length + 1);
  for (let i = 0; i <= p.length; i++) {
    dp[i] = new Array(s.length + 1);
    dp[i].fill(false);
  }
  //dp[pattern][string]

  dp[0][0] = true;
  dp[1][0] = p[0] === "*" ? true : false;

  for (let patternIdx = 1; patternIdx <= p.length; patternIdx++) {
    for (let stringIdx = 1; stringIdx <= s.length; stringIdx++) {
      if (p[patternIdx - 1] === "*") {
        dp[patternIdx][stringIdx] =
          dp[patternIdx][stringIdx - 1] || dp[patternIdx - 1][stringIdx];
      } else if (
        p[patternIdx - 1] === "?" ||
        p[patternIdx - 1] === s[stringIdx - 1]
      ) {
        dp[patternIdx][stringIdx] = dp[patternIdx - 1][stringIdx - 1];
      }
    }
  }

  return dp[p.length][s.length];

🔨 문제 후기

처음에 패턴이 0 인 경우 문자열이 0 인 경우 다 나누고 있다가 이게 뭔 짓이람 하고 인덱스를 하나 늘려서 그냥 저장했더니 더 간결해졌다.

항상 알고리즘이 동일하다면 더 간결하게 쓰기 위해 노력해야겠다!!

Elasticsearch search query 집중탐구 - 1

#[🌎elasticsearch] search query 집중탐구 - 1 전처리 과정

• Elasticsearch 가이드북 ✈

• Elasticsearch 홈페이지 가기 ✈

🧡 ElasitcSearch Full-Text-Search 의 원리

🙂Inverted Index

Elasticsearch 는 “text” 로 매핑된 필드의 경우 그 안에 데이터를 Inverted Index 라는 구조로 저장합니다.

직역하자면 역 색인, 반대 색인 이런 뜻인데 대충 감이 오시나요??

예들 들어보겠습니다. 아래와 같은 데이터가 있다고 합시다.

일반적인 DBMS 에서는 “athletic” 을 검색하고 싶다하면 1번 ,2번, 3번, 4번 순서로 검색해서 “athleti” 이 있구나 Id 4를 보여줘야지. 라고 할 겁니다.

Inverted Index 는 조금 다릅니다. 토큰마다 값을 가지는데, 이 값은 “이 문서에 이 토큰 값이 포함되어 있어.”를 저장합니다. 위의 테이블을 아래와 같은 식으로 저장합니다.

이 같은 경우 “athletic” 토큰이 포함된 4번 문서만 보면 됩니다. 다만 토큰을 빨리 찾기 위해 저장하는 자료구조는 좀 복잡해질겁니다. 괜찮습니다. Elasticsearch 가 대신해줄거거든요!!

🛑🛑 단 이렇게 저장되는 건 오직 필드가 text 타입일 때만 적용됩니다. 다른말로 하자면 text 필드가 아니면 전문검색 기능을 쓸 수 없습니다!!

🙂Analizer

위의 예시에서 눈치채신 분도 계시겠지만, 처음 테이블의 내용을 Inverted Index 방법으로 저장할 때 전부 소문자로 바뀌어서 저장이 되었습니다. 그리고 저장되지 않은 단어들도 있군요. 이 과정을 Text Analysis 라고 합니다. 이 과정을 거치지 않고 진행하게 되면 검색에 필요 없는단어 가령 “is”, “too” 까지 저장해야합니다.

우리가 “dOG” 라고 검색해도 “Dog” 가 포함된 문서를 보고 싶다면 토큰화하는 과정에 전처리 과정을 수행해야합니다.

1. Character Filter

Character Filter 는 전처리과정에서 가장 먼저 수행되는 과정입니다. Character Filter 에는 HTML Strip, Mapping, Pattern Replace 세 가지가 존재합니다.

• HTML Strip : 문장에 HTML 태그들을 없애주는 Filter 입니다. 예를들면, <p>I&apos;m so <b>happy</b>!</p> 라는 문장을 I'm so happy! 로 바꿔줍니다.
• Mapping : 특정 문자열을 내가 원하는 값으로 대체할 수 있습니다.
• Pattern Replace : 특정 정규식 패턴을 내가 원하는 값으로 대체할 수 있습니다.

2. Tokenizer Filter

Tokenizer Filter 는 문자열을 받아 단어들을 토큰화하는 과정입니다. Tokenizer Filter 는 많은 종류가 있는데 대표적인 3가지를 먼저 알아보겠습니다.

• Standard : 토큰화 할 때 공백과 hyphen(-)을 기준으로 토큰화를 수행하며, 일부 특수문자를 제거합니다.
• Letter : 토큰화 할 때 문자열 이외를 기준으로 토큰화를 수행합니다. 예들 들어 Brown-Foxes dog's 같은 문자열은 [Brown, Foxes, dog, s] 로 토큰화를 수행합니다.
• Whitespace : 공백 을 기준으로 토큰화를 수행합니다. 공백, 줄바꿈, 탭 모든 공백을 포함합니다.

Email, URL, Path 와 특수 목적용 Tokenizer 들이 많으니 자세한 정보는 Tokenizer Document 를 참조해주시와요.!!

3. Token Filter

Token Filter 는 각 Tokenizer Filter 에 의해 만들어진 Token 들에 대한 후처리 작업을 수행합니다. 가장 대표적인 Lowercase Token Filterr 로 Stop Token Filterr 가 있습니다.

• Lowercase : 말 그대로 토큰들을 소문자로 바꾸는 Token filter 입니다.
• Stop : Search 기능에 필요 없는 단어들 예를 들면 is, be, to, a, as 등을 없애는 필터입니다.

더 많은 Token filter 를 보고 싶으면 Token Filters 를 참조해주세요!! 오른쪽 메뉴바에 다양한 Token filters 가 있습니다.

4. Stemming

또한 각 토큰들은 그 원형을 유지할 필요가 있습니다. 예를 들면 working 에서 ing 는 필요 없는 부분이며 우리는 work 만 검색하면 됩니다. 이러한 과정을 Stemming 이라고 합니다.

ETC

우리가 문서에 영어만 쓰는 것은 아닙니다. 대부분 그 나라에서는 그 나라 언어를 많이 쓸 것입니다. ElasticSearch 에 내장된 언어분석기가 없다면, Full-Text-Search 에 난항을 겪을지도 모릅니다. 다행이도 한글의 경우는 Nori 한글 형태소 분석기를 이용하여 이 과정을 수행합니다.

자세한 내용은 Elasticsearch Document 를 참고해주세요!! Nori Analysis Plugin 구경하기

위 과정을 통해 저장된 토큰들을 통해 Search API 기능들을 수행합니다.

다음에는 query 를 통해 실제 예제로 찾아뵙겠습니다.

피드백은 항상 환영입니다.