📘 알고리즘 중급 문제

📖 문제 1

---

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

💻 입력

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

📃 출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

예제 입력

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

예제 출력

yes
yes
no
no
no
yes
yes

힌트

7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

풀이
저번에 풀었던 유효한 괄호 문자열인지 찾는 문제와
프로그래머스 올바른 괄호 https://school.programmers.co.kr/learn/courses/30/lessons/12909

문제를 풀었던 queue 방식을 그대로 활용해서 풀어보았다.

function bracketCheck(str) {
  // 여는 괄호를 추가할 배열
  const arr = [];

  // 괄호가 올바르게 열고 닫혔는지 체크하는 객체 check
  const check = {
    "[": "]",
    "(": ")",
  };

  for (let i = 0; i < str.length; i++) {
    const open = str[i];
    // str[i]가 check에 값이 있을 경우 = 열린 괄호인 경우
    if (check[open]) {
      // 열린 괄호(키)의 값(닫힌 괄호)를 판별하고
      // 열린 괄호의 짝이 맞는지 확인하기 위해 arr에 추가
      arr.push(open);
      // 닫힌 괄호인 경우
    } else if (open == "]" || open == ")") {
      // 마지막 열린 괄호의 짝을 확인하기 위해 pop으로 제거하고
      // close에 삽입
      const close = arr.pop();

      // check의 키(close)(여는 괄호)에 대응하는 값(닫는 괄호)인지 판별
      if (check[close] !== open) return "no";
    }
  }

  return arr.length == 0 ? "yes" : "no";
}

📌 Typescript

Typescript 탄생 배경

동적 타입 언어

• JS는 웹 페이지의 동적인 효과를 주기 위해서 만들어진 스크립트 언어

• Node.js의 등장으로 백엔드에서도 JS를 사용할 수 있게 되었다.

백엔드 에러의 위험성

• 프론트단에서의 에러는 사용자가 보는 뷰의 일관성을 해칠 수는 있어도 동작에 피해가 생기지 않는다.

• 백엔드단에서의 에러는 서버가 다운되어 웹 페이지에 접속할 수 없는 심각한 문제를 초래할 수 있다.

타입

• 런타임에서 결정되는 변수 타입

  • 개발자의 실수로 인한 오류를 찾기 쉽지 않다.

  • 런타임 단계에서의 변수 값과 타입을 확인해야하는 번거로움이 있다.

• 약한 타입 체크

  • JS는 let, const 같이 변수/상수 구분 정도만 지원한다.

  • 숫자 타입으로 초기화한 후 문자열을 할당해서 문제가 될 수 있다. -> 디버깅 어려움

• 너무나도 물렁한 객체

  const obj = { latitude: 11.5, longitude: 47.1 };
  const result = obj.latitude * obj.longitute; // 보통은 이런 실수는 컴파일러가 잡아줘야 되는데
  console.log(result) // NaN이라는 엉뚱한 값 출현!

  • 오타 등을 컴파일러가 찾아줘야하지만 그렇지 않다.

  • JS에서는 개발자가 마음대로 객체의 성질을 변화시킬 수 있다.
    -> 없는 속성을 추가하거나 속성의 타입을 변경할 수있다. -> 안정성 저하

Typescript 도입으로 변경점

컴파일 단계에서 타입 체크

JS에서

function add(a,b) {
  return a + b;
}

const result = add(1, "2");
console.log(result); // "12"
console.log("result type: ", typeof result ) // string

TS에서
입력하는 순간 에러 발생

컴파일 단계에서도 에러 발생

코드를 입력하는 순간 에러 발생

• 타입 체크
  

• 정의되지 않은 프로퍼티 연산
  

OOP에서 TS의 메리트

JS에서는 접근 제한자를 사용할 수 없으나

TS에서는 접근 제한자를 사용해서 클래스의 속성을 마음대로 접근하지 못하게 할 수 있다.

class Person {
  private name: string;
  private age: number;
  
  constructor(name: string, age: number) {
    this.name = name;
    this.age = age;
  }
  
  public growOlder(): void {
    this.age += 1;
  }
}

const people = new Person('honggildong', 30);
people.age = 25; 
// Error: Property 'age' is private and only accessible within class 'Person'.
people.growOlder();
console.log(people.age); 
// Error: Property 'age' is private and only accessible within class 'Person'.

외부 모듈의 타입 정보 제공

• @types 라는 패키지를 사용해서 d.ts라는 확장자의 선언 파일을 통해 외부 모듈 타입 정보를 제공할 수 있다.

• JS라이브러리를 TS에서 안전하게 사용하기 위해서 사용한다.

Typescript 배우는 이유

취업 시장의 필수 기술 스택

TS 개발자의 수요 증가

• TS 개발자의 수요가 꾸준히 증가 추세에 있다.

• TS는 프론트엔드, 백엔드를 가리지 않고 알아야하는 기술 스택이 되었다.

JS -> TS로 옮겨가는 흐름

• 대부분의 JS 프로젝트가 TS로 전환하는 추세

• 새로운 프로젝트는 TS를 사용해 개발

줄어드는 테스트 코드

안전성 향상

• JS에 비해 안정성과 가독성이 높아져 개발 및 유지 보수 시간을 절약할 수 있다.

생산성 향상

• 테스트 코드가 줄어들어 비즈니스 로직 작성에 더욱 집중할 수 있어서 개발 속도가 빨라진다.

고급 프로그래밍 개념 학습

• 정적 타입 시스템, 객체 지향 프로그래밍, 디자인 패턴 등 고급 프로그래밍 개념을 학습할 수 있다.

• 전문성이 높은 개발자로 성장 가능, 다양한 프로젝트에서 활용 가능한 지식 획득

컴파일러 그리고 tsc

컴파일러란?

컴파일러는 프로그래밍 언어로 작성된 소스 코드 → 다른 프로그래밍 언어로 변환하는 도구

• 변환 과정에서 컴파일러는 소스 코드의 구문과 구조를 검사하여 문제가 없는지 확인

• 개발자가 작성한 코드에 오류가 있는 경우 미리 알려주어 문제를 해결

Typescript compiler, tsc

타입 검사

• 소스 코드의 정적 타입 검사

• 개발자는 코드에서 타입 관련 오류를 미리 발견하고 수정 가능

코드 변환

• Typescript -> Javascipt 코드변환

• 변환된 코드가 어떻게 실행되는지 예측 가능 -> 디버깅에 도움

최적화

• 코드 최적화 -> 전반적인 애플리케이션 실행 시간이 빨라짐

• 컴파일러가 자동으로 수행

tsconfig.json

tsconfig.json이란?

Typescript 프로젝트의 설정 파일

• 프로젝트의 컴파일 옵션, 입력 파일들을 정의하는 데 사용

옵션

compilerOptions - target 옵션

• Typescript 프로젝트 내 코드들이 어떤 Javascript 버전으로 변환할 지 정하는 옵션

• es5, es2016 등의 컴파일 버전 설정

• 프로젝트 동작 환경을 고려하여 설정

compilerOptions - module 옵션

• Typescript 파일을 컴파일한 후 생성되는 Javascript 모듈의 형식을 지정

• 모듈을 가져오고 보내는 방식을 결정하는 옵션

• target 옵션과는 서로 독립적인 관계 // es5로 설정해도 모듈 방식 사용가능

compilerOptions - outDir 옵션

• 컴파일된 Javascript 파일이 저장될 출력 디렉토리 지정

• "outDir": "dist" -> dist 폴더에 저장

compilerOptions - strict 옵션

• 엄격한 타입 검사 옵션을 모두 활성화하는 옵션 // true

• 실수를 미리 찾아낼 수 있다.

• nullCheck, functionType, noimlicitAny 등이 자동으로 true 설정됨

compilerOptions - sourceMap 옵션

• 컴파일된 Javascript 파일에 대한 소스 맵을 생성하는 옵션

• 소스 맵을 사용하면 에러가 발생했을 때 원래 Typescript 소스 코드의 위치를 확인 가능

• 디버깅에 큰 도움이 되기 때문에 개발 환경에서는 true 설정 권장

 include , exclude 옵션

• tsc가 컴파일할 때 포함하거나 제외할 파일이나 디렉토리를 지정하는 옵션

• “include": ["src/*/"]

• "exclude": ["node_modules", "dist"]

.d.ts 파일

Javascript 라이브러리도 Typescript 코드에서 사용할 수 있게 해준다.

• Typescript 타입 정의 파일이다

.d.ts 파일로 tsc가 알 수 있는 것들

• 외부 라이브러리의 함수 타입 정보

• 외부 라이브러리 클래스 타입 정보

• 외부 라이브러리 객체 타입 정보

• 외부 라이브러리의 타입 추론 -> 명시적 타입이 아닐 경우 추론하는 것

@types 라이브러리

• @types 라이브러리를 통해 외부 라이브러리에 대한 타입 정도를 제공한다

• Typescript 프로젝트에서도 Javascript 라이브러리를 한 줄도 수정하지 않고 그대로 사용할 수 있다

타입의 중요성

타입

• 변수는 데이터를 저장하는 공간

• 저장되는 데이터는 여러가지 타입이 존재

• 타입을 올바르게 사용하면 가독성, 안정성이 향상

타입에 따른 오류 방지

• 잘못된 타입을 사용하거나 예상치 못한 타입으로 인해 오류가 발생

• JS에서는 런타임에서 오류가 발생하기 때문에 찾기 어렵다

• 타입을 제대로 사용하면 오류를 미리 방지할 수 있다

안정성 그리고 품질

• 타입 안정성은 코드가 예상한 타입대로 동작함을 보장한다

• 타입 안정성이 높을 수록 런타임에 발생할 수 있는 오류를 줄일 수 있다

• 코드의 안정성이 향상되어 테스트와 디버깅 시간을 줄일 수 있다

원활한 협업

• 타입을 명확히 명시하면 가독성이 향상된다

• 다른 개발자가 이해하기 쉽기 때문에 유지 보수가 용이해진다

기본 타입

boolean

• 2가지의 상태를 표현하고 싶은 경우 사용

• true || false

• 조건문, 비교 연산 등에 사용

number

• 모든 숫자 타입

• Typescript에서는 모든 수치 연산에 사용되는 값은 number로 명시

string

• 텍스트 데이터 타입

• 작은 따옴표(’), 큰 따옴표(”), 백틱(` 템플릿 리터럴) 를 사용하여 문자열을 표현

Array

• 기본 타입에 []가 붙은 형태

• 참조 타입

const testScores: number[] = [90, 85, 78, 92, 88];

튜플(tuple)

• 서로 다른 타입의 원소를 순서에 맞게 가질 수 있는 특수한 배열

• 정의된 데이터 타입의 개수와 순서에 맞추어 저장을 하는 것이 필수

const person: [string, number, boolean] = ['Spartan', 25, false];
const person2: [string, number, boolean] = [25, 'Spartan', false]; // 오류!

enum

• 열거형 데이터 타입

• 명확하게 관련된 상수 값들을 그룹화할 때 사용

• 각 요소는 값이 설정되어 있지 않으면 숫자 0으로 시작

const, readonly

let

• let 키워드를 사용해서 변수를 선언할 수 있다

• let으로 선언된 변수는 값을 재할당(변경)할 수 있다

const

• const 키워드를 사용해서 상수를 선언할 수 있다

• const로 선언된 상수는 값을 재할당(변경)할 수 없다

readonly

• Typescript에서 객체의 속성 불변을 만드는데 사용하는 키워드이다

• 클래스의 속성이나 인터페이스의 속성을 변경할 수 없게 만들 때 사용한다

• 클래스의 속성에는 const 키워드를 사용할 수 없다

any와 unknown, union

어쩔 수 없이 가변 타입의 데이터를 저장하고 싶다면 unkown을 사용
일일이 정의할 수 있다면 union을 사용

• Typescript를 사용하면서 여러 타입을 하나의 변수로 해결하려는 생각은 가급적 지양해야 한다

any

• Typescript에서 any 타입은 모든 타입의 슈퍼 타입이다

• Javascript에서 object 타입처럼 최상위 타입

• Typescript에서는 가급적 사용하지 않아야 한다

unknown

• any 타입과 유사하지만 더 안전한 방식으로 동작한다

• unknown 타입의 변수를 다른 타입의 변수에 할당하려면 명시적으로 타입을 확인해야한다

let unknownValue: unknown = '문자열타입';

let stringValue: string;
stringValue = unknownValue; // 에러 발생! 
stringValue = unknownValue as string; // Type Assertion(타입 단언)

• typeof를 사용하여 타입 체크를 미리 한 후 unknown 타입의 변수를 다른 타입의 변수에 할당할 수 있다

union

• unknown 타입도 재할당이 일어나지않으면 타입 안전성이 보장되지 않는다

• union은 여러 타입 중 하나를 가질 수 있는 변수를 선언할 때 사용한다

• | 연산자를 사용하여 여러 타입을 결합하여 표현한다

type StringOrNumber = string | number;