코딩 테스트에선 항상 문제가 되는 것이 엣지 케이스입니다. 보통 엣지 케이스는 생각하기 힘들거나 상식적이지 않은 입력으로 들어오는 경우가 많습니다. 시간복잡도 계산을 끝내고 그 안에 풀 수 있도록 로직을 작성했다면 그 다음으로 엣지 케이스에 대한 대비를 해야합니다. 엣지 케이스는 보통 다음과 같은 케이스가 많습니다. 입력 값의 크기가 굉장히 작은 케이스 (대부분의 입력 값이 최대값 언저리인 경우) 입력 값의 크기가 굉장히 큰 케이스 (대부분의 입력 값이 최소값 언저리인 경우) 입력 값의 범위가 넒은 케이스 (A는 최소값이고 B가 최대값인 경우) 음수 입력이 허용된 경우 음수만 입력받는 케이스 리스트를 입력 받을 때 값이 없거나 하나만 있는 케이스 또한 입력 값이 아니더라도 상황에 따른 엣지 케이스도 있습..

문제를 읽기전에 무조건 입출력 제한을 보자! 문제를 자세히 읽기전에 입출력 제한을 보는것이 중요합니다. 특히 입력 제한을 보면 어떤 시간복잡도 내에 풀어야 하는지 알 수 있습니다. 예를 들어 입력이 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)으로 끝내야하는 ..

동적계획법 ▶ 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식 ▶ 그리디나 백트래킹처럼 특정 알고리즘이 아닌 문제 해결 방식을 의미한다. ▶ Dynamic Programming(DP)이라고도 부른다. ▶ 동적 계획법이 어렵게 느껴지는 원인 중 하나 ▶ Dynamic하지 않고 Programming과도 관련이 없다 ▶ 메모리를 많이 사용하는 대신 빠른 성능을 자랑한다. ▶ 두 가지 방법론이 있다. ▶ 메모이제이션 ▶ 타뷸레이션 메모이제이션 ▶ 하양식 접근법 ▶ 동적 계획법에서 작은 문제들의 결과는 항상 같다. ▶ 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 메모이제이션이다. 타뷸레이션 ▶ 상향식 접근법 ▶ 필요한 값들을 미리 계산해두는 것 ▶ 메모이제이션은 필요할 때 계산한다면(La..

백트래킹이란? ▶ 모든 경우의 수를 탐색하는 알고리즘 ▶ DFS나 BFS를 이용할 수 있다. ▶ 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기(Pruning)라고 한다. ▶ 자바스크립트는 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다. ▶코딩 테스트에선 이를 고려하여 재귀로 작성해도 풀 수 있도록 문제를 제출하는 경우도 있다. ▶ 탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다. BFS, DFS 모든 경우의 수를 찾을 때도 사용한다. 백트래킹의 핵심은 가지치기 가지치기를 얼마나 잘하느냐가 효율성을 결정한다. 어떻게 작성할 것인가 ▶ 우선 모든 경우의 수를 찾을 수 있도록 코딩 ▶ 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고..

그리디 매 선택에서 지금 이 순간 가장 최적의 답을 선택하는 알고리즘 최적해를 보장해주지 않는다. 그리디 알고리즘의 특징 ▶ 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다 ▶ 크루스칼, 다익스트라 알고리즘 등에 사용된다. ▶ 직관적인 문제 풀이에 적합하다. 동전 반환 문제 큰 단위인 지폐, 동전 순으로 거스름돈을 만들면 된다. 가장 쉽고 직관적인 그리디 문제

너비 우선 탐색 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘 BFS의 특징 ▶ Queue를 이용하여 구현할 수 있다. ▶ 시작 지점에서 가까운 정점부터 탐색한다. ▶ V가 정점의 수, E가 간선의 수일때 BFS의 시간복잡도는 0(V+E)다. 깊이 우선 탐색 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘 DFS의 특징 ▶ Stack을 이용하여 구현할 수있다. ▶ 시작 정점에서 깊은 것 부터 찾는다. ▶ V가 정점의 수, E가 간선의 수일 때 BFS의 시간 복잡도는 0(V+E)다.