HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
💌
JJong’s Archive/
🤖
코딩테스트/
🗒️
코테 Tip
🗒️

코테 Tip

 
문제 유형 파악하기
https://school.programmers.co.kr/app/courses/19008/curriculum/lessons/235384

문제를 읽기전에 무조건 입출력 제한을 보자!

문제를 자세히 읽기전에 입출력 제한을 보는것이 중요합니다. 특히 입력 제한을 보면 어떤 시간복잡도 내에 풀어야 하는지 알 수 있습니다.
예를 들어 입력이 100 이하인 경우 높은 확률로 완전 탐색 문제입니다. 시간복잡도 O(n^3) 까지도 감당이 가능하기 때문에 플로이드 워셜과 같이 시간복잡도가 높은 알고리즘도 사용이 가능합니다. 보통 다음과 같이 판단하시면 됩니다.
  • 입력이 100 이하인 경우
    • 완전 탐색
    • 백트래킹
  • 입력이 10,000 이하인 경우
    • 최대 O(n^2) 이내로 끝내야하는 문제
    • 문제에 따라 O(n^2 log n)까지는 허용
    • n*n 2차원 리스트를 모두 순회해야하는 문제가 많음
  • 입력이 1,000,000 이하인 경우
    • 최대 O(n log n)으로 끝내야하는 문제
    • 힙, 우선순위 큐
    • 정렬
    • 동적 계획법
    • 위상 정렬
    • 다익스트라 알고리즘
  • 입력이 100,000,000 이하인 경우
    • 최대 O(n)으로 끝내야하는 문제
    • 동적 계획법
    • 그리디
  • 그 이상인 경우
    • 최대 O(log n)으로 끝내야하는 문제가 많음
    • 거의 안나오는 문제 유형
    • 이진탐색

문제 유형

100%는 아니지만 높은 확률이라고 봐주시면 좋습니다. :)
코딩 테스트에서 많이 나오는 유형을 추렸습니다.

입력값이 작은 문제

위에서 적었듯 높은 확률로 완전 탐색 혹은 백트래킹 문제입니다.
구현력이 중요한 문제로 출제될 가능성이 높습니다.

지도가 주어지고 채워진 영역을 찾아야하는 경우

높은 확률로 BFS, DFS 문제입니다. FloodFill과 같이 정직한 방식으로 나오거나 전염병 문제나 치즈 문제(https://www.acmicpc.net/problem/2636)처럼 살짝 변형되서 나오는 경우가 있습니다.

그래프 그림이 있는 경우

이 경우 높은 확률로 세 가지 유형 중 하나입니다.
  • 최단 거리 찾기
  • 최소 신장 트리
  • 위상 정렬
      • 문제에서 "가장 빠른 길", "최단 거리"와 비슷한 키워드가 나온다면 당연히 최단 거리 찾기 유형이고 "X 비용 내로 갈 수 있는 길을 찾아라"와 같은 키워드가 나와도 최단 거리 찾기 유형입니다. 다익스트라, BFS, DFS 등이 사용될 수 있습니다.
최소 신장 트리 문제는 보통 "가장 저렴한 방법으로 모든 경로 연결해라" 등의 키워드로 출제됩니다. 경로가 아니라 통신망, 전송 시간, 회로, 배관 등 다양한 용어로 나올 수는 있지만 핵심은 모든 경로를 "가장 싸게 연결해라"입니다. 그래프는 양방향일수도 단방향일수도 있습니다. 크루스칼, 프림 알고리즘을 사용할 수 있습니다.
위상 정렬은 순서를 정해야할 때 사용됩니다. 보통 "순서", "차례" 등의 키워드가 나오면 위상 정렬 문제입니다.

X라는 조건을 만족하는 가장 최대/최소값을 찾아라

이 경우 높은 확률로 결정 문제입니다. 파라메트릭 서치를 이용해서 풀 수 있습니다.

실시간으로 정렬이 이루어져야 하는 경우

높은 확률로 우선순위 큐 혹은 힙을 사용하는 문제입니다.

DP 문제

보통 완전 탐색처럼 시간이 오래걸리면 안되는데 특별한 알고리즘을 사용하는 문제가 아닐거 같을 때는 높은 확률로 DP 문제입니다. 다른 문제처럼 "딱봐도 이거네!" 하는 특징이 없어서 보통 문제를 보고 바로 유형을 판단하기 힘든 경우 DP처럼 풀 수 있는지 생각해봐야 합니다. 종이를 꺼내고 다음과 같은 방식으로 해보셔도 괜찮을 것 같습니다.
  1. 문제를 따라 먼저 초기값을 적는다.
  1. 초기값을 포함해 모든 상태값을 적는다.
  1. 현재상태를 통해 다음 값을 구할 수 있는지 판단한다.
  1. 혹은 이전 상태들을 통해 현재 값을 구할 수 있는지 판단한다.
      2. 이런식으로 여러 번 해보고 식을 만들 수 있다면 100% DP 문제입니다.

문자열이 주어지는 경우

구현력 문제인 경우가 많습니다. 문자열을 자르거나, 붙이거나 탐색하는 문제가 대부분입니다. 문자열을 탐색하는 알고리즘이 필요한 경우 KMP 알고리즘을 사용할 수 있지만 보통 파이썬과 같은 스크립트 언어에선 문자열 탐색이 빌트인으로 존재하기 때문에 구현에만 집중하면 됩니다.

현재 상황에서 가장 최적인 선택을 해야하는 경우

문제에서 항상 최적의 선택을 해야하는 경우 혹은 "가장 많은 선택을 할 수 있는", "가장 작은/큰" 등의 키워드가 들어가면 그리디 문제일 가능성이 높습니다. 위에서 잠깐 말했던 최소 신장 트리도 그리디의 일종입니다.
 
엣지 케이스 찾기
코딩 테스트에선 항상 문제가 되는 것이 엣지 케이스입니다.
보통 엣지 케이스는 생각하기 힘들거나 상식적이지 않은 입력으로 들어오는 경우가 많습니다. 시간복잡도 계산을 끝내고 그 안에 풀 수 있도록 로직을 작성했다면 그 다음으로 엣지 케이스에 대한 대비를 해야합니다.
엣지 케이스는 보통 다음과 같은 케이스가 많습니다.
  1. 입력 값의 크기가 굉장히 작은 케이스 (대부분의 입력 값이 최대값 언저리인 경우)
  1. 입력 값의 크기가 굉장히 큰 케이스 (대부분의 입력 값이 최소값 언저리인 경우)
  1. 입력 값의 범위가 넒은 케이스 (A는 최소값이고 B가 최대값인 경우)
  1. 음수 입력이 허용된 경우 음수만 입력받는 케이스
  1. 리스트를 입력 받을 때 값이 없거나 하나만 있는 케이스
또한 입력 값이 아니더라도 상황에 따른 엣지 케이스도 있습니다.
  1. 그래프에서 사이클(cycle)이 발생하는 경우
  1. 길찾기 문제에서 지그재그로 움직일 경우
  1. 부동소수점 오차
엣지 케이스는 문제마다 무궁무진합니다. 위 사례가 아닌 유형도 문제에 따라 발생할 수 있습니다. 그렇기 때문에 항상 문제 풀이하면서 엣지 케이스를 염두해둡시다. :)
 
자바스크립트의 9가지 코드 트릭

1. 구조 분해 할당을 이용한 변수 swap

ES6의 구조 분해 할당 문법을 사용하여 두 변수를 swap 할 수 있습니다.
let a = 5, b = 10;
[a, b] = [b, a];
console.log(a, b); // 10 5

2. 배열 생성으로 루프 제거하기

보통 단순히 범위 루프를 돌고 싶다면 다음과 같이 코드를 작성합니다.
let sum = 0;
for (let i = 5; i < 10; i += 1) {
    sum += i;
}
만약 범위 루프를 함수형 프로그래밍 방식으로 사용하고 싶다면 배열을 생성해서 사용할 수 있습니다.
const sum = Array
    .from(new Array(5), (_, k) => k + 5)
    .reduce((acc, cur) => acc + cur, 0);

3. 배열 내 같은 요소 제거하기

Set을 이용할 수 있습니다.
const names = ['Lee', 'Kim', 'Park', 'Lee', 'Kim'];
const uniqueNamesWithArrayFrom = Array.from(new Set(names));
const uniqueNamesWithSpread = [...new Set(names)];

4. Spread 연산자를 이용한 객체 병합

두 객체를 별도 변수에 합쳐줄 수 있습니다.
const person = {
	name: 'Lee Sun-Hyoup',
	familyName: 'Lee',
	givenName: 'Sun-Hyoup'
};

const company = {
	name: 'Cobalt. Inc.',
	address: 'Seoul'
};

const leeSunHyoup = { ...person, ...company };
console.log(leeSunHyoup);
// {
//   address: “Seoul”
//	   familyName: “Lee”
//   givenName: “Sun-Hyoup”
//   name: "Cobalt. Inc." // 같은 키는 우선 순위에 따라 정해진다.
// }

5. &&와 || 활용

&&와 ||는 조건문 외에서도 활용될 수 있습니다.
/// ||
// 기본값을 넣어주고 싶을 때 사용할 수 있습니다.
// participantName이 0, undefined, 빈 문자열, null일 경우 'Guest'로 할당됩니다.
const name = participantName || 'Guest';

/// &&
// flag가 true일 경우에만 실행됩니다.
flag && func();

// 객체 병합에도 이용할 수 있습니다.
const makeCompany = (showAddress) => {
  return {
    name: 'Cobalt. Inc.',
    ...showAddress && { address: 'Seoul' }
  }
};
console.log(makeCompany(false));
// { name: 'Cobalt. Inc.' }
console.log(makeCompany(true));
// { name: 'Cobalt. Inc.', address: 'Seoul' }

6. 구조 분해 할당 사용하기

객체에서 필요한 것만 꺼내 쓰는 것이 좋습니다.
const person = {
	name: 'Lee Sun-Hyoup',
	familyName: 'Lee',
	givenName: 'Sun-Hyoup'
	company: 'Cobalt. Inc.',
	address: 'Seoul',
}

const { familyName, givenName } = person;

객체 생성시 키 생략하기

객체를 생성할 때 프로퍼티 키를 변수 이름으로 생략할 수 있습니다.
const name = 'Lee Sun-Hyoup';
const company = 'Cobalt';
const person = {
  name,
  company
}
console.log(person);
// {
//   name: 'Lee Sun-Hyoup'
//   company: 'Cobalt',
// }

7. 비구조화 할당 사용하기

함수에 객체를 넘길 경우 필요한 것만 꺼내 쓸 수 있습니다.
const makeCompany = ({ name, address, serviceName }) => {
  return {
    name,
    address,
    serviceName
  }
};
const cobalt = makeCompany({ name: 'Cobalt. Inc.', address: 'Seoul', serviceName: 'Present' });

8. 동적 속성 이름

ES6에 추가된 기능으로 객체의 키를 동적으로 생성 할 수 있습니다.
const nameKey = 'name';
const emailKey = 'email';
const person = {
  [nameKey]: 'Lee Sun-Hyoup',
  [emailKey]: 'kciter@naver.com'
};
console.log(person);
// {
//   name: 'Lee Sun-Hyoup',
//   email: 'kciter@naver.com'
// }

9. !! 연산자를 사용하여 Boolean 값으로 바꾸기

!! 연산자를 이용하여 0, null, 빈 문자열, undefined, NaN을 false로 그 외에는 true로 변경할 수 있습니다.
function check(variable) {
  if (!!variable) {
    console.log(variable);
  } else {
    console.log('잘못된 값');
  }
}
check(null); // 잘못된 값
check(3.14); // 3.14
check(undefined); // 잘못된 값
check(0); // 잘못된 값
check('Good'); // Good
check(''); // 잘못된 값
check(NaN); // 잘못된 값
check(5); // 5