[코딩테스트 유형정리/자바스크립트] 코테보기전에 볼 것

코딩테스트 기본 유형 총정리 (핵심 예시 + 풀이 논리)

---

1.문자열 처리

 - 예시 문제

문자열을 뒤집어서 출력하시오.
입력: "hello" → 출력: "olleh"

 

- 풀이 논리

• 문자열은 배열처럼 접근 가능
• JS에서는 split("") → reverse() → join("") 패턴이 기본

 

function reverseStr(s) {

  return s.split("").reverse().join(""); 
}

 

[개념정리]

1.split()

- split 함수는 건네받은 특정 문자열로 구분하여 배열을 반환한다.
  안에 ""로 빈 문자열을 건네면 원본 문자열의 각 문자가 배열의 개별 요소가 된다.

 

2.reverse()
- reverse() 함수는 해당 배열의 순서를 역순으로 정리한다.

 

3.join()

- Array 인스턴스의 join() 메서드는 배열의 모든 요소를 쉼표나 지정된 구분 문자열로 구분하여 연결한 새 문자열을 만들어 반환

- 배열에 항목이 하나만 있는 경우, 해당 항목은 구분 기호를 사용하지 않고 반환된다.

예시)
const elements = ["Fire", "Air", "Water"];
console.log(elements.join());
// Expected output: "Fire,Air,Water"

console.log(elements.join(""));
// Expected output: "FireAirWater"

console.log(elements.join("-"));
// Expected output: "Fire-Air-Water" 

 

번외)

slice() 

slice() 메서드는 어떤 배열의 begin 부터 end 까지(end 미포함)에 대한 얕은 복사본을 새로운 배열 객체로 반환합니다. 원본 배열은 바뀌지 않습니다.

const animals = ["ant", "bison", "camel", "duck", "elephant"];

console.log(animals.slice(2));
// Expected output: Array ["camel", "duck", "elephant"]

console.log(animals.slice(2, 4));
// Expected output: Array ["camel", "duck"]

 

 

---

 

2.피보나치 수열 (DP 기초형)

예시 문제

n번째 피보나치 수를 구하시오.
입력: n = 10 → 출력: 55

 

풀이 논리

• 점화식: f(n) = f(n-1) + f(n-2)
• 단순 재귀 → 시간 초과
• 반복문 DP (Bottom-Up) 방식이 정석

 

function fib(n){
  const dp = [0,1];
  for(let i=2;i<=n;i++){
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}

💬 확장형 예시:
“피보나치 수를 1,000,000,007로 나눈 나머지를 구하시오”
→ (a+b)%1000000007 로 처리

아래 한 줄만 추가

dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;

---

코테에서 “피보나치”, “계단 오르기”, “타일 채우기” 같은 DP 문제 나오면
이 코드 구조 그대로 응용하면 된다.

 

[개념정리]

피보나치 수열이란?

정의:
첫 번째 항은 0, 두 번째 항은 1이고,
그 다음 항부터는 이전 두 항의 합으로 이루어지는 수열

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

규칙식(점화식)

f(n) = f(n-1) + f(n-2)

예를 들어:

• f(0) = 0
• f(1) = 1
• f(2) = f(1) + f(0) = 1
• f(3) = f(2) + f(1) = 2
• f(4) = f(3) + f(2) = 3
• f(5) = f(4) + f(3) = 5

즉,
“앞의 두 숫자를 더하면 다음 숫자가 되는” 규칙

 

2. DP(동적 계획법, Dynamic Programming) 

“한 번 계산한 결과를 저장해두고,
나중에 또 필요할 때 다시 계산하지 않고 바로 가져다 쓰자.”

즉,
중복 계산을 없애는 방법
→ “기억하며 푸는” 방식

 

---

 

3.정렬 (Sort)

예시 문제

배열 [5,2,9,1]을 오름차순으로 정렬하시오.
출력: [1,2,5,9]

 

풀이 논리

• 기본 내장 정렬 사용 가능 (sort((a,b)=>a-b))
• 커스텀 정렬 (내림차순, 문자열 길이순 등) 자주 나옴

 

const arr = [5,2,9,1];
arr.sort((a,b)=>a-b);
console.log(arr); // [1,2,5,9]

 

 

[개념정리]

- sort() 메서드는 배열의 요소를 적절한 위치에 정렬한 후 그 배열을 반환

arr.sort([compareFunction]);

compareFunction Optional

정렬 순서를 정의하는 함수. 생략하면 배열은 각 요소의 문자열 변환에 따라 각 문자의 유니 코드 코드 포인트 값에 따라 정렬됩니다.

 

문자열 대신 숫자를 비교하기 위해 compare 함수는 a에서 b를 뺄 수 있습니다. 다음 함수는 숫자 배열을 정리

 

//오름차순 정렬
arr.sort((a,b)=>a-b);

//내림차순 정렬
arr.sort((a,b)=>b-a);

 

 

 

정렬한 배열. 원 배열이 정렬되는 것에 유의 (복사본 만드는게 아님)

 

const months = ["March", "Jan", "Feb", "Dec"];
months.sort();
console.log(months);
// Expected output: Array ["Dec", "Feb", "Jan", "March"]

const array1 = [1, 30, 4, 21, 100000];
array1.sort();
console.log(array1);
// Expected output: Array [1, 100000, 21, 30, 4]

---

 

4.완전탐색 (Brute Force)

예시 문제

세 수 중 가장 큰 수를 구하시오.
입력: [3, 7, 5] → 출력: 7 

function maxOfThree(a, b, c) {
  return Math.max(a, b, c);
}

// 사용 예
console.log(maxOfThree(3, 7, 5)); // 7

 

또는

“주어진 배열에서 두 수의 합이 target이 되는 경우를 모두 찾으시오.”

function findPairs(arr, target){
  let result = [];
  for(let i=0;i<arr.length;i++){
    for(let j=i+1;j<arr.length;j++){
      if(arr[i]+arr[j]===target)
        result.push([arr[i],arr[j]]);
    }
  }
  return result;
}

 

풀이 논리

• 중첩 for문으로 모든 조합 탐색
• 작은 입력에서는 단순 반복이 제일 안전

 

 

[개념정리]

브루트 포스 알고리즘은 모든 경우의 수를 탐색하여 정답을 찾는 완전탐색 알고리즘입니다. 문제 해결을 위해 복잡한 알고리즘을 고민하기보다, 컴퓨터의 연산 능력을 이용해 가능한 모든 조합을 일일이 대입하는 방식입니다. 

구현이 쉽고 100% 정확성을 보장하지만, 모든 경우의 수를 확인하므로 시간 복잡도가 매우 높다는 단점이 있습니다. 

 

---

 

5.탐색 (Binary Search / DFS / BFS) - 어려움 

 

알고리즘목적사용하는 상황

Binary Search	빠르게 값 찾기	정렬된 배열
DFS	깊게 탐색	그래프/트리 탐색
BFS	넓게 탐색	최단거리 탐색

DFS 

한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것(노드 아래로) -> 스택 또는 재귀함수

 

BFS

시작점에서 가까운 노드부터 먼저 탐색하고, 같은 거리에 있는 노드를 모두 탐색한 후 그 다음 거리의 노드를 순차적으로 탐색하는 방식(같은 노드레벨에서 옆으로) -> 큐

 

 

예시 문제 1 – 이진 탐색

정렬된 배열 [1,3,5,7,9]에서 7의 인덱스를 찾으시오.

풀이 논리

• 중간값 기준으로 반씩 줄이기 → O(log n)

 

function binarySearch(arr, target){
  let left=0,right=arr.length-1;
  while(left<=right){
    const mid = Math.floor((left+right)/2);
    if(arr[mid]===target) return mid;
    else if(arr[mid]<target) left=mid+1;
    else right=mid-1;
  }
  return -1;
}

 

--> arr이 오름차순으로 정렬되어있다는 선제 조건이 충족되어야 해당 함수가 유효하다. 

정렬이 안되어 있다면 먼저 arr.sort((a,b) => a-b); 로 오름차순 정렬이 필요하다

 

- 정렬된 배열 [1,3,5,7,9]에서 7의 인덱스를 찾으시오.  --> 브루트 포스(순차탐색) 방식으로는 

function findIndex(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1; // 찾지 못했을 때
}

console.log(findIndex([1,3,5,7,9], 7)); // 👉 3

 

- 그냥 findIndex함수 사용 해도됨(근데 알고리즘 만드는거니 이건 아니겠죠?)

--> findIndex은 내부적으로 처음부터 끝까지 탐색하는 선형탐색이라 for문이랑 다를바 없다.

const arr = [1, 3, 5, 7, 9];
const index = arr.findIndex(num => num === 7);

console.log(index); // 👉 3

 

 

예시 문제 2 – DFS/BFS

그래프(혹은 미로)에서 특정 노드까지 도달 가능한지 판단

• DFS: 재귀 (깊게 파고듦)
• BFS: 큐 (넓게 탐색, 최단거리용)

 

풀이 논리

function dfs(node, visited, graph){
  visited[node]=true;
  for(let next of graph[node]){
    if(!visited[next]) dfs(next, visited, graph);
  }
}

 

[세부설명]

const graph = [
  [1,2], // 0번 노드와 연결
  [0,3], // 1번 노드와 연결
  [0,4], // 2번 노드와 연결
  [1],   // 3번 노드와 연결
  [2]    // 4번 노드와 연결
];

 

그림으로 그리면 아래와 같음 

      0
     / \
    1   2
    |    \
    3     4

즉, graph[2] = [0,4] --> 2번 노드는 0번노드와 4번 노드와 연결됨 

 

문제 예시2

 

 

문제:
1번부터 7번까지 노드가 있는 그래프가 있습니다.
아래와 같이 연결되어 있습니다.

• 1번 → 2, 3
• 2번 → 1, 4, 5
• 3번 → 1, 6, 7
• 4,5,6,7는 각각 자기 부모와만 연결

1번 노드에서 7번 노드까지 도달할 수 있는지 판단하세요.

문제 해석

• 노드 = 1~7 → 그래프에서 점
• 간선(Edge) = 연결 정보
• 목표 = start = 1, goal = 7
• 요구사항 = “도달 가능 여부” → boolean 반환

그래프 표현 (인접 리스트)

const graph = [
  [],        // 0번 인덱스는 사용 X (1번부터 시작)
  [2,3],    // 1번 노드 연결
  [1,4,5],  // 2번 노드 연결
  [1,6,7],  // 3번 노드 연결
  [2],      // 4번 노드 연결
  [2],      // 5번 노드 연결
  [3],      // 6번 노드 연결
  [3]       // 7번 노드 연결
];

 

DFS 코드로 구현 

function dfs(node, visited, graph, goal) {
  if(node === goal) return true;       // 목표 도달
  visited[node] = true;                // 현재 노드 방문

  for(let next of graph[node]){        // 연결된 노드 탐색
    if(!visited[next]){
      if(dfs(next, visited, graph, goal)) return true;
    }
  }

  return false;                        // 연결된 노드 다 탐색했는데 목표 없음
}

const visited = Array(8).fill(false);  // 0~7번 노드 방문 체크
const start = 1, goal = 7;

console.log(dfs(start, visited, graph, goal)); // true

 

 

[개념정리]

노드(Node)란?

• 그래프를 구성하는 기본 단위
• 흔히 “점”이나 “정점”이라고 부름
• 서로 연결될 수 있음(Edge)
• 즉, 연결 관계를 나타내는 대상

1) 도시 지도

• 도시 = 노드
• 도로 = 간선(Edge)
• “서울 → 부산 → 대구” 이런 연결을 그래프로 표현 가능

2) SNS 친구 관계

• 사람 = 노드
• 친구 관계 = 간선
• “철수-영희-민수” 친구 관계도 그래프 + 노드

3) 컴퓨터 구조

• 컴퓨터/서버 = 노드
• 네트워크 연결 = 간선

 

---

 

6.그리디(Greedy, 탐욕법)

예시 문제

거스름돈 4720원을 동전 [500,100,50,10] 으로 최소 개수로 거슬러주기

풀이 논리

• 매 단계에서 가장 큰 단위 먼저 사용
• 동전, 회의실 배정, 로프문제 등에서 자주 나옴

 

function changeMoney(n){
  const coins=[500,100,50,10];
  let count=0;
  for(let c of coins){
    count += Math.floor(n/c);
    n %= c;
  }
  return count;
}

 

[개념정리]

 - const coins=[500,100,50,10];

    --> 무작위 순서로 나오면 아까 말한 coins.sort((a,b) => b-a)로 내림차순 정렬

 - for(let c of coins)

    --> for ~ of 문 c는 coins의 순차적인 값들 -> 500, 100, 50, 10 

 - count += Math.floor(n/c); --> n을c로나눈값

   --> Math.floor(계산식) -> 결과 값의 소수점 이하를 버리고 정수를 리턴

- n %= c; 
   --> 대입연산자: 오른쪽 피연산자의 값을 왼쪽 피연산자의 값에 대입

   --> %= : n을 c로 나눈 나머지
    // 4720 % 500 = 220 → 다음 단계에서 100원 동전으로 처리
    

---

 

7.스택 / 큐

예시 문제

괄호 문자열의 유효성을 판단하시오.(괄호가 올바르게 짝을 지엇는지)
입력: "(()())" or "(())" → 출력: true  
입력: "(())(" → 출력: false

풀이 논리

• 여는 괄호 → push
• 닫는 괄호 → pop
• 끝났을 때 스택이 비었는지 확인

 

function validParentheses(s){
  const stack=[];
  for(let ch of s){
    if(ch==='(') stack.push(ch); 
    else {
      if(!stack.length) return false;
      stack.pop();
    }
  }
  return stack.length===0;
}

 

[개념정리]

- if(ch==='(') stack.push(ch)

  --> 현재 (이면 마지막 새항목 배열(오른쪽)에 새로 값을 넣는다.
 

- if(!stack.length) return false; 

  --> (이 아닌데 stack에 값이 없으면 짝없으니 false
- stack.pop(); 

  --> ch가 )일때 짝인 (를 오른쪽부터 뺀다.
 

- return stack.length===0; 

  --> 다빼면 짝이 맞는거니 true 리턴하면서 종료 

---

 

8.해시 / 카운팅 문제

예시 문제

배열에서 가장 많이 등장한 숫자를 출력하시오.
입력: [1,3,2,3,4,3] → 출력: 3

풀이 논리

• Map 혹은 객체를 사용해 빈도 수 집계
• 최빈값, 중복 체크 등에 자주 활용

 

function mostFrequent(arr){
  const map = {};
  for(let n of arr){
    map[n] = (map[n]||0)+1;
  }
  return Object.entries(map).sort((a,b)=>b[1]-a[1])[0][0];
}

 

[개념정리]

• map 객체를 만들어서 각 숫자의 등장 횟수를 저장
• (map[n] || 0) + 1 →
  • map[n]이 존재하면 기존 값 + 1
  • 존재하지 않으면 0 + 1 → 처음 등장하면 1로 시작

예시: arr = [1,2,1,3,1,2]

 

n map 상태

1	{1: 1}
2	{1: 1, 2: 1}
1	{1: 2, 2: 1}
3	{1: 2, 2: 1, 3:1}
1	{1: 3, 2: 1, 3:1}
2	{1: 3, 2: 2, 3:1}

 

• Object.entries(map) → [[key, value], ...] 배열로 변환
• .sort((a,b) => b[1] - a[1]) → 등장 횟수 기준 내림차순 정렬
• [0][0] → 가장 많이 나온 값(최빈값) 가져오기

예시: map = {1:3, 2:2, 3:1} → entries → [[1,3],[2,2],[3,1]]

• 정렬 후 [0][0] = 1 → 최빈값 1

 

---

정리 요약표

유형키워드핵심 포인트난이도

문자열 처리	split/reverse	기본 문법 숙지	⭐
피보나치/DP	점화식, 메모이제이션	중복 제거, O(n)	⭐⭐
정렬	sort, 커스텀 비교	내장함수 이해	⭐
완전탐색	2중 for문	단순하지만 기본기	⭐
탐색	DFS, BFS, Binary	재귀/큐/이진개념 숙지	⭐⭐⭐
그리디	항상 최선 선택	코인, 회의실 배정 등	⭐⭐
스택/큐	push/pop	괄호문제, 순서제어	⭐⭐
해시	빈도수, Map	중복, 카운팅	⭐⭐

---

👉 추천 복습 순서
1️⃣ 피보나치(DP)
2️⃣ 스택/큐 (괄호)
3️⃣ 정렬
4️⃣ 해시
5️⃣ 그리디
6️⃣ 완전탐색
7️⃣ DFS/BFS (여유 있으면)