[프로그래머스] 코딩강의-Javascript편 정리

hoya.a·2022년 6월 2일
0

알고리즘

목록 보기
2/10
post-thumbnail

코딩테스트 준비

메모하기

  • 코드에 주석을 달거나 노트에 메모하면서 풀기
  • 헷갈릴때 순서도 그리기

디버깅은 필수

  • 내가 예상한대로 동작이 안된다면 꼭 디버깅을 하자
  • 로직 중간에 console.log를 사용하여 값이 정상적인지 확인
  • 외부IDE 사용이 가능하다면 NodeJS의 디버그 모드를 사용하자

익숙해지기

  • 시간복잡도를 계산하는 것에 익숙해져야 한다.
  • 엣지 케이스를 생각하는 것에 익숙해지기.

좋은코드를 작성하기

좋은 코드란?

  • 변수,함수의 이름을 잘 정하기
  • 중복 코드를 제거했는가?
  • 함수형 프로그래밍도 좋은 방법
  • map, filter, reduce와 같은 고차함수 이용하면 깔끔

가지치기를 했는가?

  • 흔히 백트래킹과 같은 알고리즘에서 사용되지만 그 외 알고리즘에서도 중요하다.
  • 사소한 로직이라면 성능이 크게 개선되지는 않지만 코드 리뷰에서 좋은 평가를 받을 수 있다.

자바스크립트를 잘 이용했는가?

  • 자바스크립트로 코딩테스트를 본다면 문법을 잘 활용해야 한다.
  • 구조분해 할당
  • spread 오퍼레이터

일관성을 유지했는가?

  • 잘 짯더라도 일과성 없는 코드보다 조금 더러워도 일관성있는 코드가 좋다.
  • var와 let을 혼용
  • snake_case 와 camelCase를 혼용
  • 변수명, 함수명을 줄임말로 쓰다가 어딘가에서 전부 적는 경우
  • 제출전에 코드 스타일이나 변수명, 함수명을 꼭 확인하자.

자료구조

메모리를 효율적으로 사용하여 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로 상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다.

문제 상황에 맞지 않는 자료구조를 사용하게 되면 느리고 불안정적으로 데이터를 처리할 수도있다.

알고리즘

특정 문제를 효율적이고 빠르게 해결하는 것이 궁극적인 목표로 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.

자료구조의 종류

단순 구조 : 정수, 실수, 문자열, 논리

선형구조 : 배열, 연결 리스트, 스택, 큐등 한 원소 뒤에 하나의 원소만이 존재하는 형태. 자료들이 선형으로 나열되어 있는 구조를 가진다.

비선형구조 : 그래프, 트리등 원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절하다. 비선형 구조에 해당되는 자료구조는 트리와 그래프 등이 있다.

시간복잡도

프로그램의 성능을 알기 위해서 고려할 것

입력으로 들어오는 데이터의 크기, 하드웨어의 성능, 운영체제의 성능, 컴파일러 최적화 등등..
고려할것들이 너무 많기 때문에 프로그램의 성능을 정확히 파악하는건 불가능하다.

따라서 대략적인 성능을 비교하기위해 만들어진것이 빅오표기법이다.

빅오표기법(Big-O notation)

시간복잡도를 나타내기위한것들중 하나이다.

위 그래프는 빅오표기법의 상대적인 성능을 시각화한 자료

big O 에 쓰인 n이 전부 같은 값이라 가정할때
O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)

O(1) : 상수 실행 시간

  • 입력값과 상관없이 일정한 실행 시간을 갖는다. 가장 이상적인 알고리즘이지만 대부분 불가능하다.

O(log n) : 로그 시간

  • 실행 시간이 입력 크기의 로그에 비례해서 늘어나는 경우이다. 그래프에서 보이는대로 입력 데이터가 늘어 날 수록 실행시간이 늘어나는 폭이 줄어들고 있다.

O(n) : 선형 시간

  • 실행 시간이 입력 크기에 비례하는 알고리즘 입니다.

O(n log n) : 선형 로그 시간

  • 선형 알고리즘과 다항식 알고리즘의 중간

O(n^c) : 다항식 시간

  • 입력 크기가 늘어나면 실행 시간이 빠르게 늘어납니다.

O(c^n) : 지수 시간

  • 입력크기에 따라 실행 시간이 굉장히 빠르게 늘어난다.

O(n!) : 팩토리얼 시간

  • 위 그림에는 없지만 가장 느린 알고리즘이다
  • 여기서 지수시간이나 펙토리얼 시간은 특정한 상황이 아니면 사용되면 안된다.

빅오표기법 계수 법칙 n이 무한에 가까울 수록 k의 크기는 의미가 없다. 때문에 생략하여 표기한다. 물론 k가 클수록 성능에는 영향이 있을 수 있다.

빅오표기법에는 여러가지 법칙은 있지만 표기할때는 두가지만 기억하자!

  1. 상수항은 무시 하자
  2. 가장 큰 항 외엔 무시하자

자바스크립트에서 성능을 측정하는 방법

Date 객체를 이용
시작시간을 구하고 로직을 돌린다음에 끝시간에 시작시간을 빼준다.

인강 출처 : 프로그래머스

profile
TIL 정리

0개의 댓글