코딩테스트를 형식적인 암기라고 생각할 수도 있는데요. 근데 뭐 본인이 어떻게 바라보냐의 차이라고 생각해요. 저는 다음과 같은 목적이 있다고 생각해요.

1. 문제해결 능력 검증 ( 자료구조, 알고리즘 )
2. 한가지 언어 이해도 검증 ( 문법 )
3. 성능최적화 고려(시간복잡도, 공간복잡도) 능력 검증
4. 함수 이름, 변수 네이밍, 클린코드, 안티패턴 습관, 가독성 등등 코드품질 검증
5. 시간 배분 능력 검증
6. 예외 처리 검증

그래서 코딩테스트를 잘 하는 사람이 일을 잘 확률도 높다라는 건데요. 그래서 조직에서는 리스크를 줄이기 위해 성공확률에 배팅하는 거라고 봐요. 기술적 역량 말고도 소통 역량도 중요한데 해당 역량은 면접에서 검증을 하면 되니깐요.

근데 코딩테스트하고 면접보고 하면 사람 뽑는데 수개월은 금방 지나가니 스타트업은 인재를 쟁취하기 위해 어느정도 포트폴리오로 검증되면 커피챗으로 서로 협의하고 바로 뽑는 경우도 많더라고요.

거두절미하고 그래서 이번 글에서는 어떻게 코딩테스트를 접근해야 할지 기술하겠습니다. 비단 코딩 테스트 뿐만 아니라 회사에서 일을 할 때도, 인생에 있어서도 다음과 같은 프로세스를 적용하면 훨씬 성장 속도가 빨라질 것이라 생각해요.

1. 해결하려고 하는 문제를 완벽하게 인지부터 해야 합니다. 어떤 문제를 해결 해야 하는지 파악해야해요. 핵심적인 본질을 파악 해야해요. 이때 추상화의 과정을 거쳐야 합니다. 추상화라는 것은 핵심적인 본질만 추출하는 거에요. 본인만이 아는 익숙한 용어로 문제를 재정의해도 좋아요. 복잡한 문제라면 문제자체를 이해하는데 어려울 수 있어요. 그 때는 문제를 세부적으로 쪼개어 이해하는 연습을 해야 합니다. 뇌에 머물러 있는 생각들은 구름마냥 둥둥 떠다니기 때문에 메모를 해서 확실하게 정리해놓는게 좋아요.

2. 한정된 시간에 정해진 문제들을 풀기위해 시간 배분을 해야 합니다. 예를들어 총 해결 할 문제가 5문제면 난이도에 따라 10분, 20분 기준을 세워놓고 정해야합니다. 해당 시간을 초과하면 체크해놓고 넘어가세요.

3. 자료구조와 알고리즘을 기반으로 어떻게 문제를 해결할지 계획을 세웁니다. 자료구조 알고리즘이라 하니깐 뭔가 거창하게 보이는데요, 생각하기 싫으면 직감적으로 떠올리는 대로 해결 해버리세요. 때로는 계획을 세우지 않고 무지성으로 바로 실행하는게 정답일 때도 있어요. 다만 연습 할때는 계획을 세우는게 좋다고 봐요. 우선 예전에 풀었던 비슷한 문제를 떠올려보는게 좋아요. 그리고 생각이란게 한가지 생각만 하면 고여있게 되므로 단순하게 생각하고, 순서도를 그리든지, 문제 해결 순서를 바꿔보든지, 생각안나면 이것저것 생각을 바꿔해보는 습관을 가집니다.

4. 이때 수도코드 작성을 권장 드립니다. 문제 해결 계획을 단계적으로 쪼개어 놓고 해당 단계를 점진적으로 해결하며 검증(디버깅) 해야합니다. 문제 해결 과정을 단계적으로 검증하지 않으면 나중에 문제를 해결하고 제출 했는데 틀려버리면 문제 해결 계획을 다시 세워야 하기 때문입니다. 접근을 잘못했다는 거에요. 이러한 일의 방식은 폭포수 vs 애자일과 비슷합니다. 모듈별로 개발하고 테스트를 할 것인지, 모든 개발을 마무리 하고 테스트를 할 것인지의 차이입니다.

5. 최종적으로 문제를 해결하고 검증(테스트)를 하고 제출합니다.

6. 위의 효율적인 과정을 거치는 것보다 비교도 안될정도로 훨씬 중요한게 일단 방법이야 어찌 됐던지간에 실행으로 옮기는 행동이 훨씬 중요합니다.

• 그리고 코딩 테스트가 암기의 역량도 필요해서요. 시험 치기 전에 1달 바짝 공부하는게 점수 편차가 클겁니다. K-벼락치기 아시죠?

• 문제 유형 정리표

• 배열(Array) 관련 함수

• 문자열(String) 관련 함수

• 수학(Math) 관련 함수

JavaScript 알고리즘 문제 유형별 정리

1. 문자열 (String)

1-1. 대소문자 변환

function toUpperCase(str) {
  return str.toUpperCase();
}

function toLowerCase(str) {
  return str.toLowerCase();
}

1-2. 문자열 정렬 (문자들을 오름차순 정렬)

function sortString(str) {
  return str.split("").sort().join("");
}

1-3. 문자열 비교

function compareStrings(str1, str2) {
  return str1 === str2;
}

1-4. 문자 갯수 세기 (빈도수 구하기)

function countCharacters(str) {
  const count = {};
  for (let char of str) {
    count[char] = (count[char] || 0) + 1;
  }
  return count;
}

1-5. 회문 검사

function isPalindrome(str) {
  const cleaned = str.replace(/[\W_]/g, "").toLowerCase();
  return cleaned === cleaned.split("").reverse().join("");
}

1-6. 아나그램 검사

function isAnagram(str1, str2) {
  const sortStr = s => s.replace(/[\W_]/g, "").toLowerCase().split("").sort().join("");
  return sortStr(str1) === sortStr(str2);
}

1-7. 중복 문자 제거

function removeDuplicateCharacters(str) {
  return Array.from(new Set(str)).join('');
}

2. 배열 (Array)

2-1. 배열 중복 제거

function removeDuplicates(arr) {
  return [...new Set(arr)];
}

2-2. 배열 정렬

const arr = [5, 3, 8, 1, 4];
arr.sort((a, b) => a - b);

2-3. 배열의 합계 및 최댓값

const numbers = [3, 7, 2, 9, 4];
const sum = numbers.reduce((acc, num) => acc + num, 0);
const max = Math.max(...numbers);

2-4. 슬라이딩 윈도우 (고정된 크기의 부분합)

function slidingWindowSum(arr, windowSize) {
  const result = [];
  for (let i = 0; i <= arr.length - windowSize; i++) {
    let windowSum = 0;
    for (let j = 0; j < windowSize; j++) {
      windowSum += arr[i + j];
    }
    result.push(windowSum);
  }
  return result;
}

2-5. 이중 반복문 예제

function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      console.log(`Pair: (${arr[i]}, ${arr[j]})`);
    }
  }
}

3. 수학 (Math)

3-1. 약수 구하기

function getDivisors(n) {
  const divisors = [];
  for (let i = 1; i <= n; i++) {
    if (n % i === 0) {
      divisors.push(i); // i가 나누어 떨어지면 약수
    }
  }
  return divisors;
}

3-2. 소수 판별

function isPrime(n) {
  if (n < 2) return false;
  for (let i = 2; i < n; i++) {  
    if (n % i === 0) return false;
  }
  return true;
}

3.3 최소공배수, 최대공약수

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

function solution(a, b) {
  let minNum = Math.min(a, b)
  let maxNum = Math.max(a, b)
  let gcdValue = 1

  // 최대공약수 찾기 (완전탐색)
  for (let i = 1; i <= minNum; i++) {
    if (a % i === 0 && b % i === 0) {
      gcdValue = i
    }
  }

  // 최소공배수 찾기 (배수 탐색)
  let lcmValue = maxNum
  while (lcmValue % a !== 0 || lcmValue % b !== 0) {
    lcmValue++
  }

  return [gcdValue, lcmValue]
}

4. 해시 / 맵 (Hash / Map)

4-1. 빈도 수 세기

function frequencyCounter(arr) {
  const freq = {};
  for (let item of arr) {
    freq[item] = (freq[item] || 0) + 1;
  }
  return freq;
}

4-2. 첫 번째 고유 값 찾기

function firstUnique(arr) {
  const freq = frequencyCounter(arr);
  for (let item of arr) {
    if (freq[item] === 1) return item;
  }
  return null;
}

5. 투포인터 (Two-Pointer)

고정된 길이의 연속 부분 배열 중 합이 가장 큰 값을 반환하는 함수입니다.
슬라이딩 윈도우 기법을 효율적으로 활용해 시간 복잡도는 **O(n)**입니다.

연속 7일간의 최고 주가 합계를 구할 때
웹사이트 방문자 수에서 연속 n일중 가장 방문자가 많았던 구간을 구할 때 사용 되는 로직입니다.

5-1. 구간 합

function maxSubarraySum(arr, windowSize) {
  let maxSum = 0;
  let windowSum = 0;
  for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];
    if (i >= windowSize - 1) {
      maxSum = Math.max(maxSum, windowSum);
      windowSum -= arr[i - windowSize + 1];
    }
  }
  return maxSum;
}

6. 정렬 (Sorting)

6-1. 기준별 정렬

students.sort((a, b) => b.score - a.score);

6-2. 퀵 정렬

function quickSort(arr) {
  if (arr.length <= 1) return arr; // base case
  
  const pivot = arr[0];
  const left = arr.slice(1).filter(v => v < pivot);
  const right = arr.slice(1).filter(v => v >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

// 예시
console.log(quickSort([5, 3, 8, 4, 2])); // [2, 3, 4, 5, 8]

6-3. 병합 정렬

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let l = 0, r = 0;

  while (l < left.length && r < right.length) {
    if (left[l] < right[r]) result.push(left[l++]);
    else result.push(right[r++]);
  }

  // 남은 값 합치기
  return result.concat(left.slice(l)).concat(right.slice(r));
}

// 예시
console.log(mergeSort([7, 2, 6, 3, 9])); // [2, 3, 6, 7, 9]

6.4 숫자 정렬 (Basic Sort)

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

6.5 K번째 수

function getNthNumber(array, commands) {
  return commands.map(([i, j, k]) => {
    return array.slice(i - 1, j).sort((a, b) => a - b)[k - 1];
  });
}

파라미터 설명

• array: 기준이 되는 숫자 배열입니다. (예: [1, 5, 2, 6, 3, 7, 4])
• commands: 3개의 정수 [i, j, k]를 요소로 갖는 명령어 배열입니다.
  • i ~ j 구간의 숫자를 자르고,
  • 정렬한 후,
  • k번째 값을 구합니다 (1-based index).

로직 설명

각 명령 [i, j, k]에 대해 아래 과정을 반복합니다:

1. array.slice(i - 1, j)

   • i-1부터 j까지의 부분 배열을 복사합니다.
   • JavaScript의 slice는 start는 포함, end는 미포함이므로 j는 그대로 사용.

2. .sort((a, b) => a - b)

   • 해당 부분 배열을 오름차순 정렬합니다.

3. [k - 1]

   • 정렬된 배열의 k번째 요소를 가져옵니다 (0-based index이므로 -1 필요).

예제

const array = [1, 5, 2, 6, 3, 7, 4];
const commands = [
  [2, 5, 3],  // [5,2,6,3] -> [2,3,5,6] -> 3번째: 5
  [4, 4, 1],  // [6] -> [6] -> 1번째: 6
  [1, 7, 3],  // [1,5,2,6,3,7,4] -> [1,2,3,4,5,6,7] -> 3번째: 3
];

getNthNumber(array, commands); // 결과: [5, 6, 3]

최종 요약

• getNthNumber는 각 명령에 따라 배열의 특정 구간을 잘라 정렬하고 k번째 값을 추출하는 함수입니다.
• **시간 복잡도는 정렬 O(n log n)**이므로, commands의 수와 각 구간의 크기에 따라 성능 영향을 받을 수 있습니다.

6.6 가장 큰 수 만들기

값의 배열 numbers 를 입력받아 가장 크게 조합될 수 있는 정수 문자열을 만듭니다.

function makeLargestNumber(numbers) {
  const sorted = numbers.map(String).sort((a, b) => (b + a) - (a + b));
  return sorted.join('').replace(/^0+/, '0');
}

사용 방법

makeLargestNumber([3, 30, 34, 5, 9]);
// 결과: "9534330"

함수 구조 설명

1. numbers.map(String)

• numbers 배열의 값을 문자열로 변환
• 이유: 문자열 결합과 비교를 하기 위해

2. .sort((a, b) => (b + a) - (a + b))

• 작업: 두 문자열 a, b를 결합해 (b+a)가 (a+b)보다 크면 b를 앞에 오게 된다.
• 예:
  • a = '3', b = '30'
  • a + b = '330', b + a = '303'
  • '330' > '303' 가 되면 3이 앞에 오게 합니다.

3. sorted.join('')

• 정렬된 문자열 배열을 하나로 열결

4. .replace(/^0+/, '0')

• 최종 결과가 '0000' 같은 경우, 값을 '0'로 컨테츠 표현
• /^0+/ : 첫 번째에서 모든 0 처리
• '0' : 각장 0 하나로 바꾸기

6.7 학생들을 특정 조건에 따라 정렬

const students = [
  { name: "Junkyu", kor: 50, eng: 60, math: 100 },
  { name: "Sangkeun", kor: 80, eng: 60, math: 50 },
];

students.sort((a, b) => {
  if (a.kor !== b.kor) return b.kor - a.kor;
  if (a.eng !== b.eng) return a.eng - b.eng;
  if (a.math !== b.math) return b.math - a.math;
  return a.name.localeCompare(b.name);
});

정렬 기준 설명

1. 국어 점수 내림차순 (높은 점수 우선)

   if (a.kor !== b.kor) return b.kor - a.kor;
   

   • b.kor - a.kor이므로 국어 점수가 높은 학생이 앞에 오게 됩니다.

2. 영어 점수 오름차순 (낮은 점수 우선)

   if (a.eng !== b.eng) return a.eng - b.eng;
   

   • a.eng - b.eng이므로 영어 점수가 낮은 학생이 앞에 옵니다.

3. 수학 점수 내림차순 (높은 점수 우선)

   if (a.math !== b.math) return b.math - a.math;
   

   • 수학 점수는 높은 점수가 우선입니다.

4. 이름 알파벳순 (사전 순 정렬)

   return a.name.localeCompare(b.name);
   

   • 모든 점수가 같을 경우 이름을 기준으로 오름차순 정렬합니다.

정렬 결과 예시

[
  { name: "Sangkeun", kor: 80, eng: 60, math: 50 },
  { name: "Junkyu", kor: 50, eng: 60, math: 100 },
]

• Sangkeun은 국어 점수가 더 높기 때문에 먼저 나옵니다.

실무 활용 예

이런 정렬 방식은 다음과 같은 상황에서 유용합니다:

• 학생 성적 순위 산정
• 우선순위가 여러 개인 데이터 정렬 (ex. 상품 정렬, 이력서 평가 등

6.8 ATM 문제(=시간 누적 최소화 문제)

ATM 앞에 N명의 사람들이 줄을 서 있으며, 각 사람이 돈을 인출하는 데 걸리는 시간이 배열 times에 주어집니다.

각 사람은 앞사람이 인출을 끝나야 자신의 인출을 시작할 수 있으므로, 줄을 서는 순서에 따라 전체 기다리는 시간의 합이 달라질 수 있습니다

목표는 사람들이 줄을 서는 순서를 잘 정해서 기다리는 시간의 총합을 최소로 만드는 것입니다.

구현 코드

const times = [3, 1, 4, 3, 2];
times.sort((a, b) => a - b); // 오름차순 정렬

let sum = 0;
let acc = 0;
for (let t of times) {
  acc += t; // 지금까지의 대기 시간 누적
  sum += acc; // 전체 대기 시간에 누적 추가
}

console.log(sum); // 출력: 32

정렬 후 상태

times = [1, 2, 3, 3, 4];

각 단계에서 계산:

따라서 최소 대기 시간의 총합은 32입니다.

요약

• 전략: 인출 시간이 짧은 사람부터 먼저 줄을 서게 한다 → 오름차순 정렬
• 로직: 누적합을 구하면서 전체 대기 시간의 총합을 계산
• 시간복잡도:
  • 정렬: O(N log N)
  • 누적합 계산: O(N)

실무 활용 포인트 이 알고리즘은 대기열 최소화, 처리 순서 최적화, 리소스 스케줄링 같은 분야에 유용하게 쓰입니다. 예를 들어:

• 병원 접수 순서 최적화
• CPU 작업 스케줄링 (Shortest Job First)
• 고객센터 상담 순서 최적화 등

6.9 두 수의 합

문제 설명

"배열에서 두 수를 골라 더했을 때 특정 값 x가 되는 경우가 있으면 true를 반환하라. 없다면 false를 반환하라."

예시:

hasPair([1, 4, 2, 7, 5], 9); // true (2 + 7)
hasPair([1, 2, 3, 4], 8); // false

function hasPair(arr, target) {
  arr.sort((a, b) => a - b); // 1. 배열을 오름차순으로 정렬
  let left = 0, right = arr.length - 1; // 2. 투 포인터 초기화

  while (left < right) {
    const sum = arr[left] + arr[right]; // 3. 현재 두 수의 합
    if (sum === target) return true;         // 4. 목표값과 같으면 true 반환
    if (sum < target) left++;                // 5. 합이 작으면 왼쪽 포인터 증가
    else right--;                       // 6. 합이 크면 오른쪽 포인터 감소
  }
  return false;                         // 7. 끝까지 없으면 false 반환
}

시간 복잡도

• 정렬: O(n log n)
• 투 포인터 순회: O(n)
• 총 시간 복잡도: O(n log n)

실무 사용 예시

1. 결제 검증

• 장바구니 금액 중 특정 조합이 할인 조건을 충족하는지 체크할 때

2. 금융 시스템

• 사용자 이체 내역 중 두 개의 금액이 특정 합이 되는 사기 거래 패턴이 있는지 검출할 때

3. 추천 시스템

• 예산에 맞는 상품 두 개를 추천할 수 있는 조합이 있는지 확인할 때

4. 알고리즘 문제풀이

• 인터뷰나 코딩 테스트에서 자주 나오는 고전 문제로, 사고력과 알고리즘 최적화 능력을 테스트

추가 팁

• HashSet을 활용한 O(n) 방법도 있음 (정렬 없이):

function hasPairHash(arr, target) {
  const set = new Set();
  for (let num of arr) {
    if (set.has(target - num)) return true;
    set.add(num);
  }
  return false;
}

• 시간 복잡도: O(n) / 공간 복잡도: O(n)

7. 탐색 (Searching)

7.1 이진 탐색 (Binary Search)

function binarySearch(arr, target) {
  let left = 0;
  let 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;
}

7.2 BFS - 미로 탐색

function bfsMaze(maze, start) {
  const queue = [start];
  const visited = Array.from({ length: maze.length }, () => Array(maze[0].length).fill(false));
  const directions = [
    [1, 0], [-1, 0], [0, 1], [0, -1]
  ];
  visited[start[0]][start[1]] = true;

  while (queue.length > 0) {
    const [x, y] = queue.shift();
    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;
      if (
        nx >= 0 && ny >= 0 &&
        nx < maze.length && ny < maze[0].length &&
        maze[nx][ny] === 1 &&
        !visited[nx][ny]
      ) {
        queue.push([nx, ny]);
        visited[nx][ny] = true;
      }
    }
  }
  return visited;
}

7.3 DFS - 단지번호 붙이기

function dfsMap(grid) {
  const visited = Array.from({ length: grid.length }, () => Array(grid[0].length).fill(false));
  const dx = [0, 0, 1, -1];
  const dy = [1, -1, 0, 0];
  let count = 0;

  function dfs(x, y) {
    visited[x][y] = true;
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (
        nx >= 0 && ny >= 0 &&
        nx < grid.length && ny < grid[0].length &&
        grid[nx][ny] === 1 &&
        !visited[nx][ny]
      ) {
        dfs(nx, ny);
      }
    }
  }

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === 1 && !visited[i][j]) {
        dfs(i, j);
        count++;
      }
    }
  }
  return count;
}

7.4 백트래킹 - N과 M

1부터 n까지의 숫자 중에서 중복 없이 m개를 선택하는 모든 순열을 구하는 백트래킹 알고리즘입니다.

function backtracking(n, m) {
  const result = [];
  const temp = [];

  function dfs(depth) {
    if (depth === m) {
      result.push([...temp]);
      return;
    }
    for (let i = 1; i <= n; i++) {
      if (!temp.includes(i)) {
        temp.push(i);
        dfs(depth + 1);
        temp.pop();
      }
    }
  }

  dfs(0);
  return result;
}

7.5 매개변수 이진 탐색

이진 탐색 (parametric search) 을 이용해서 예산 배정 문제를 해결하는 방식이에요. 쉽게 말하면, 총 예산 total을 넘지 않으면서 가능한 최대 상한액 mid를 찾는 문제입니다.

function parametricSearch(budgets, total) {
  let left = 0;
  let right = Math.max(...budgets);
  let result = 0;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const sum = budgets.reduce((acc, cur) => acc + Math.min(cur, mid), 0);

    if (sum <= total) {
      result = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
}

8. 스택 / 큐 (Stack / Queue)

8-1. 괄호 검사

function isValidParentheses(s) {
  const stack = [];
  const map = { ')': '(', '}': '{', ']': '[' };
  for(let char of s) {
    if (['(', '{', '['].includes(char)) {
      stack.push(char);
    } else if (map[char]) {
      if (stack.pop() !== map[char]) return false;
    }
  }
  return stack.length === 0;
}

8-2. 문자열 뒤집기

function reverseString(str) {
  const stack = [];
  for(let char of str) {
    stack.push(char);
  }
  let reversed = "";
  while(stack.length) {
    reversed += stack.pop();
  }
  return reversed;
}

8.3 프린터 문제

특정 우선순위에 따라 출력 순서 결정

function solution(priorities, location) {
  const queue = priorities.map((priority, index) => ({ priority, index }));
  let count = 0;

  while (queue.length) {
    const current = queue.shift();
    if (queue.some(item => item.priority > current.priority)) {
      queue.push(current);
    } else {
      count++;
      if (current.index === location) return count;
    }
  }
}

8.4 요세푸스 문제

순서대로 제거하다가 마지막 남는 사람 찾기

function josephus(n, k) {
  const queue = Array.from({ length: n }, (_, i) => i + 1);
  const result = [];

  while (queue.length) {
    for (let i = 0; i < k - 1; i++) {
      queue.push(queue.shift());
    }
    result.push(queue.shift());
  }
  return result;
}

8.5

const str = "hello";
const queue = str.split(""); // ['h', 'e', 'l', 'l', 'o']

while (queue.length) {
  console.log(queue.shift()); // h e l l o
}

9. 재귀 / DFS, BFS

9-1. 팩토리얼

function factorial(n) {
  if(n <= 1) return 1;
  return n * factorial(n - 1);
}

9-2. 하노이 탑

function hanoi(n, source, target, auxiliary) {
  if(n === 1) {
    console.log(`Move disk 1 from ${source} to ${target}`);
    return;
  }
  hanoi(n - 1, source, auxiliary, target);
  console.log(`Move disk ${n} from ${source} to ${target}`);
  hanoi(n - 1, auxiliary, target, source);
}

9-3. DFS & BFS

const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
};

function dfs(node, visited = new Set()) {
  if(visited.has(node)) return;
  console.log(node);
  visited.add(node);
  for(let neighbor of graph[node]) {
    dfs(neighbor, visited);
  }
}

function bfs(start) {
  const visited = new Set();
  const queue = [start];
  while(queue.length) {
    const node = queue.shift();
    if(!visited.has(node)) {
      console.log(node);
      visited.add(node);
      queue.push(...graph[node]);
    }
  }
}

9-4. DFS - 섬의 개수 (2D 배열 탐색)

function numIslands(grid) {
  const row = grid.length;
  const col = grid[0].length;
  
  const dfs = (x, y) => {
    if (x < 0 || y < 0 || x >= row || y >= col || grid[x][y] === '0') return;
    grid[x][y] = '0';
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
  };

  let count = 0;
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (grid[i][j] === '1') {
        dfs(i, j);
        count++;
      }
    }
  }
  return count;
}

const map = [
  ['1', '1', '0', '0'],
  ['1', '0', '0', '1'],
  ['0', '0', '1', '1']
];
console.log(numIslands(map)); // 3

9-5. BFS - 미로 최단 경로

function shortestPath(maze) {
  const n = maze.length;
  const m = maze[0].length;
  const visited = Array.from({ length: n }, () => Array(m).fill(0));
  const queue = [[0, 0]];
  visited[0][0] = 1;

  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];

  while (queue.length) {
    const [x, y] = queue.shift();
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (nx >= 0 && ny >= 0 && nx < n && ny < m && maze[nx][ny] === 1 && visited[nx][ny] === 0) {
        visited[nx][ny] = visited[x][y] + 1;
        queue.push([nx, ny]);
      }
    }
  }
  return visited[n - 1][m - 1];
}

const maze = [
  [1, 0, 1, 1],
  [1, 1, 0, 1],
  [0, 1, 1, 1]
];
console.log(shortestPath(maze)); // 7

10. 동적 계획법 (DP)

10-1. 피보나치 (메모이제이션)

function fibonacci(n, memo = {}) {
  if(n in memo) return memo[n];
  if(n <= 1) return n;
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

10-2. 누적합 배열 반환 -> 구간 합 계산 할 때 유용

function prefixSum(arr) {
  const result = [0];
  for(let i = 0; i < arr.length; i++){
    result.push(result[i] + arr[i]);
  }
  return result;
}

10-3. 동전 교환 문제

function coinChange(coins, amount) {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for(let coin of coins) {
    for(let i = coin; i <= amount; i++){
      dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

11. 간단한 클래스 구현

11-1. Stack

class Stack {
  constructor() {
    this.items = [];
  }
  
  push(item) {
    this.items.push(item);
  }
  
  pop() {
    if(this.isEmpty()) return null;
    return this.items.pop();
  }
  
  isEmpty() {
    return this.items.length === 0;
  }
  
  peek() {
    return this.items[this.items.length - 1];
  }
}

11-2. Queue

class Queue {
  constructor() {
    this.items = [];
  }
  
  enqueue(item) {
    this.items.push(item);
  }
  
  dequeue() {
    if(this.isEmpty()) return null;
    return this.items.shift();
  }
  
  isEmpty() {
    return this.items.length === 0;
  }
  
  front() {
    return this.items[0];
  }
}

11-3. LinkedList

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }
  
  append(value) {
    const newNode = new ListNode(value);
    if(!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while(current.next) {
      current = current.next;
    }
    current.next = newNode;
  }
  
  display() {
    let current = this.head;
    const values = [];
    while(current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(" -> "));
  }
}

• 1.1 약수의 합

• 정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

function sumOfDivisor(n) {
  return Array(n)
    .fill()
    .map((_i, i) => i + 1)
    .filter((i) => n % i === 0)
    .reduce((sum, num) => sum + num, 0)
}

• 약수가 현업에서 사용되는 사례

약수는 단순한 수학 개념 같지만, 실제 프로그래밍/개발/현업 문제 해결에서도 다양하게 사용됩니다. 특히 자료구조, 알고리즘, 보안, 성능 최적화 등 여러 분야에서 유용하게 활용됩니다.

• 1.2 자릿수의 합

• 자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요. 예를들어 N = 123이면 1 + 2 + 3 = 6을 return 하면 됩니다.

풀이

function sumOfDigit(n) {
  return n
    .toString()
    .split('')
    .reduce((acc, curr) => acc + parseInt(curr), 0)
}

• 1.3 x만큼 간격이 있는 n개의 숫자

• 함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해야 합니다. 다음 제한 조건을 보고, 조건을 만족하는 함수, solution을 완성해주세요.

function solution(x, n) {
  return Array(n)
    .fill(x)
    .map((v, i) => (i + 1) * v)
}

• 1.4 자연수 뒤집어 배열로 만들기

-자연수 n을 뒤집어 각 자리 숫자를 원소로 가지는 배열 형태로 리턴해주세요. 예를들어 n이 12345이면 [5,4,3,2,1]을 리턴합니다.

function getReverseArray(n) {
  return n
    .toString()
    .split('')
    .reverse()
    .map((item) => Number(item))
}

• 1.5 두 정수 사이의 합

-두 정수 a, b가 주어졌을 때 a와 b 사이에 속한 모든 정수의 합을 리턴하는 함수, solution을 완성하세요. 예를 들어 a = 3, b = 5인 경우, 3 + 4 + 5 = 12이므로 12를 리턴합니다.

function solution(a, b) {
  let min = Math.min(a, b)
  let max = Math.max(a, b)
  //등차수열 공식
  return ((max - min + 1) * (min + max)) / 2
}

• 1.6 정수 내림차순 배치

• 함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를들어 n이 118372면 873211을 리턴하면 됩니다.

function changeDescInt(n) {
  return parseInt(
    n
      .toString()
      .split('')
      .sort((a, b) => b - a)
      .join(''),
    10,
  )
}

• 1.7 정수 제곱근 판별

• 임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다. n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요.

function solution(n) {
  let x = Math.sqrt(n)
  return Number.isInteger(x) ? (x + 1) ** 2 : -1
}

• 1.8 음양 더하기

• 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 return 하도록 solution 함수를 완성해주세요.

function solution(absolutes, signs) {
  return absolutes.reduce((sum, num, i) => sum + (signs[i] ? num : -num), 0)
}

• 1.9 나누 떨어지는 숫자 배열

• array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요. divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요.

function solution(array, divisor) {
  // divisor로 나누어 떨어지는 값만 필터링
  let result = array.filter((num) => num % divisor === 0).sort((a, b) => a - b)

  // 결과가 비어 있다면 [-1] 반환
  return result.length ? result : [-1]
}

• 1.10 김서방 찾기

• String형 배열 seoul의 element중 "Kim"의 위치 x를 찾아, "김서방은 x에 있다"는 String을 반환하는 함수, solution을 완성하세요. seoul에 "Kim"은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니다.

function solution(seoul) {
  // "Kim"의 위치 찾기
  let index = seoul.indexOf('Kim')

  // 결과 문자열 반환
  return `김서방은 ${index}에 있다`
}

• 1.11 콜라즈 추측

• 1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다. 1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.

2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다. 예를 들어, 주어진 수가 6이라면 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야 하는지 반환하는 함수, solution을 완성해 주세요. 단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환해 주세요.

function solution(num) {
  let count = 0

  while (num !== 1) {
    if (count >= 500) return -1

    num = num % 2 === 0 ? num / 2 : num * 3 + 1
    count++
  }

  return count
}
33

• 1.12 없는 숫자 더하기

0부터 9까지의 숫자 중 일부가 들어있는 정수 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요.

function solution(numbers) {
  const totalSum = 45 // 0부터 9까지의 합 (0+1+2+3+4+5+6+7+8+9)
  const numbersSum = numbers.reduce((sum, num) => sum + num, 0)

  return totalSum - numbersSum
}

• 1.13 제일 작은 수 제거하기

• 정수를 저장한 배열, arr 에서 가장 작은 수를 제거한 배열을 리턴하는 함수, solution을 완성해주세요. 단, 리턴하려는 배열이 빈 배열인 경우엔 배열에 -1을 채워 리턴하세요. 예를들어 arr이 [4,3,2,1]인 경우는 [4,3,2]를 리턴 하고, [10]면 [-1]을 리턴 합니다.

function solution(arr) {
  if (arr.length === 1) return [-1]

  const min = Math.min(...arr)
  return arr.filter((num) => num !== min)
}

• 1.14 핸드폰 번호 가리기

• 프로그래머스 모바일은 개인정보 보호를 위해 고지서를 보낼 때 고객들의 전화번호의 일부를 가립니다. 전화번호가 문자열 phone_number로 주어졌을 때, 전화번호의 뒷 4자리를 제외한 나머지 숫자를 전부 *으로 가린 문자열을 리턴하는 함수, solution을 완성해주세요.

function solution(phone_number) {
  const arrLength = phone_number.length
  return '*'.repeat(arrLength - 4) + phone_number.slice(-4)
}

• 1.15 내적

• 길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요.

function solution(a: number[], b: number[]): number {
    return a.reduce((sum, value, index) => sum + value * b[index], 0);
}

• 1.16 수박수박수?

• 길이가 n이고, "수박수박수박수...."와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 예를들어 n이 4이면 "수박수박"을 리턴하고 3이라면 "수박수"를 리턴하면 됩니다.

function solution(n: number): string {
    return "수박".repeat(Math.ceil(n / 2)).slice(0, n);
}

• 1.17 약수의 개수와 덧셈

• 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

function countDivisors(n) {
  let count = 0
  for (let i = 1; i <= n; i++) {
    if (n % i === 0) count++
  }
  return count
}

function solution(left, right) {
  let sum = 0
  for (let i = left; i <= right; i++) {
    if (countDivisors(i) % 2 === 0) {
      sum += i
    } else {
      sum -= i
    }
  }
  return sum
}

//countDivisors(n) 함수로 약수의 개수를 세고, 짝수면 더하고 홀수면 뺀다.
//O(n^2)의 복잡도로 비효율적일 수 있음.