코딩테스트

Franklee·2024년 7월 3일
0

Basic Study

목록 보기
4/8

해시

  • 어떠한 값이 저장되는 위치를 어떤 규칙으로 정할 수 있다면 탐색없이 바로 데이터 찾을 수 있다
  • key 와 data를 저장해서 빠른 데이터 탐색 (일대일 대응), key 통한 접근 1) 단방향, key → data 가능, data → key 불가능 2) 탐색과정 필요없다 O(1). 3) 변환과정 필요, data→index

해시는 주소록 처럼 사용가능, 값에 대한 “해시 테이블”이 존재하고 테이블의 데이터를 “버킷”이라고 한다

사용분야 - 비밀번호 관리, 데이터베이스 인덱싱, 블록체인

Javascript에서는 Map, Set을 사용하여 해시를 이용한다.

  • Map으로 key와 value를 저장
  • Set으로 key 만을 저
  • Key 값은 언제나 유일

순열(순열, 중복 순열, 조합, 중복조합)

  • 서로 다른 n개에서 r개를 뽑아서 순서대로 정렬하는 경우의 수
  • 재귀 표현이 반복된다. ( if → 결과ok → output / if → 결과no → 다시 if)
  • 원 배열, 잔여배열 을 통해 작업 ( [ㄱ,ㄴ,ㄷ] → [ㄱ],[ㄴ,ㄷ] )

재귀를 사용하여 동일한 작업을 하는 반복 루프를 만들어 원하는 결과값이 출력될때까지 재귀를 수행하도록 한다.

조합

  • 순서가 없다. → 순열에서 한 부분만 변경하면 구현 가능하다.

https://velog.io/@rlatp1409/알고리즘-JS-순열과-조합-구현-자바스크립트


탐색

  • 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문

DFS(깊이 우선 탐색)

  • 루트에서 다음 노드로 넘어가기전에 해당 노드에 대한 분기 완벽 파악
  • 모든 노드를 방문하고자 할때, 방문 여부를 반드시 검사해야함 (backtracking)
  • 간단 + 느림

큐를 사용하여 정점(시작점) 넣는다.

시작점과 연결된 [ㄱ,ㄴ,ㄷ]에서 ㄱ을 빼고 ㄱ에 연결된 ㄹ를 맨 앞에 넣는다

[ㄹ,ㄴ,ㄷ]에서 위 행동을 반복하여 큐가 빌때까지 재귀 반복

BFS (너비 우선 탐색)

  • 인접한 노드 먼저 탐색
  • 두 노드 사이의 최단 경로 /임의의 경로 찾고 싶을 때 이 방법 선택
  • 재귀적 동작 no ( 반복문 사용)
  • 어떤 노드 방문 여부를 반드시 검사

큐를 사용하여 정점(시작점) 넣는다.

시작점과 연결된 [ㄱ,ㄴ,ㄷ]에서 ㄱ을 빼고 ㄱ에 연결된 ㄹ를 맨 뒤에 넣는다

[ㄹ,ㄴ,ㄷ]에서 위 행동을 반복하여 큐가 빌때까지 재귀 반복

DFS, BFS 언제 사용?

DFS - 길의 형태 파악 가능, 경로의 특징 이용

BFS - 최단거리 구하기

https://velog.io/@sean2337/Algorithm-DFS와-BFS의-쉬운-개념-JavaScript-구현-방법


DP (Dynamic Programming) 동적 계획법

  • 한번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 (중복여부)
  • 두가지 조건
    • 큰문제를 작은문제로 나눌수 있다
    • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일
  • 구현 방식
    • top-down : 재귀적 구현( + 메모이제이션 )
    • botton-up : 반복문 구현 ( + DP 테이블 )
  • 시간 복잡도

https://gyyeom.tistory.com/116


Divide and conquer (분할 정복)

  • 문제를 2가지 이상으로 나눈뒤 각 문제에 대한 답을 재귀를 이용해 구하고 n가지의 답으로 전체 답을 구하는 방식.
  • 일반 재귀와 차이점 → 분할하여 각 문제에 대한 답을 구한다.
  • 3가지 구성요소
    • 분할(divide)
    • 병합(merge)
    • 분할 불가한 가장 작은 문제(base case)
  • 2가지 조건
    • 문제를 나눌수 있는 방법
    • 문제를 나눈 후의 효율성

https://blog.naver.com/qpghnv/221580612451


GCD (최대공약수, 최소공배수)

  • 최대 공약수 → 두 수의 약수중 가장 큰 정수
let getGCD = (num1, num2) => {
    let gcd = 1;

    for(let i=2; i<=Math.min(num1, num2); i++){
        if(num1 % i === 0 && num2 % i === 0){
            gcd = i;
        }
    }

    return gcd;
}
  • 최소 공배수 → 두 수의 공통 배수 중 가장 작은 수
let getLCM = (num1, num2) =>{
	let lcm = 1;

    while(true){
      if((lcm % num1 == 0) && (lcm % num2 == 0)){
        break;
      }
      lcm++;
    }
  	return lcm
}

유클리드 호제법을 이용한 구현

num1를 num2로 나눈 나머지를 r이라고 했을 때, GCD(num1, num2) = GCD(num2, r)과 같다는 것이다.

  • 최대 공약수
let getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);

  • 최소 공배수
    • lcm = (num1*num2) / gcd

정리

https://velog.io/@devjade/JavaScript로-최대공약수GCD-최소공배수LCM-구하기

function solution(num1, num2) {
    const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
    const lcm = (a, b) => a * b / gcd(a, b);
    return [gcd(num1, num2), lcm(num1, num2)];
}

Array.prototype.sort 정렬

  • 문자정렬 → vanilla 사용
  • 숫자 오름차순 → (a,b)⇒{ return a-b; } / 내림차순은 b-a
  • 비교
    • if a가 b보다 작다면 return -1;
    • if a가 b보다 크다면 return 1;
    • if 같다면 return 0;

https://velog.io/@kim-jaemin420/메서드Array.prototype.sort자바스크립트-정렬함수-sort

profile
복잡한 문제를 쉬운 코드로 해결해 나가는 개발자

0개의 댓글