Concept 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. 아래와 같은 수열이 있을 때 오름차순으로 정렬된 부분 수열은 1,3,5 1,3,4 3,5 1,2,4 등과 같이 존재하며, 해당 수열에서 최장 증가 부분 수열은 3 Feature 이러한 LIS의 길이를 구하는 방법 중 단순한 접근법은 Brute-Force방법으로 수열의 총 길이가 K라고 가정할 때 1개 이상의 원소를 가지는 모든 부분수열의 경우의 수는 2^K개로 모든 부분 수열의 오름차순 정렬을 확인하는 것은 시간이 매우 오래 걸린다. LIS의 길이를 구하는 최적 방법에는 2가지가 있다. 다이나믹 프로그..

Concept 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 Feature 배낭 문제에는 두 가지 유형이 존재 Fractional Knapsack : 물건을 쪼갤 수 있음. 무게나 가치가 소수점 단위로 나뉠 수 있는 문제. 0-1 Knapsack : 물건을 쪼갤 수 없음. 무게나 가치가 무조건 정수타입을 가지는 문제. Implement Brute-Force 가장 기본적인 풀이방법으로써 N개의 물건에 대해 가능할 수 있는 모든 조합을 만들어 보는 접근법. 시간복잡도는 O(2^N)으로 많이 느리다고 볼 수 있다. Dynamic Programming DP의 핵심은 메모이제이..

이분 그래프 조건 : 두 개의 색으로만 구분, 인접한 정점이 같은 색을 가지면 안됨. Concept 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 위 사진과 같이 두 개의 그룹으로 나누어지며, 같은 그룹의 정점은 인접하지 않음. 간선(E)이 아예 없고, 정점(V)만 있는 경우도 이분 그래프에 속함. Feature 주어진 그래프가 이분 그래프인지 확인하기 위해서는 BFS, DFS 탐색을 활용. 완전탐색의 일종으로 모든 정점을 방문하여 검사하기 때문에 O(V+E)의 시간복잡도를 가짐 인접 정점 간의 싸이클(Cycle)이 발생할 경우 홀수 싸이클의 경우 이분 그래프를 절대 만족 못함. Implement 너비 우선 탐색(BFS)를 활용한 탐색 1. 인접리스트를 활..

1. 재귀 호출과 메모이제이션 문제 제시 : 토끼 수 구하기 문제의 내용만 달라졌을 뿐 사실 상 피보나치 f(n) = f(n-2) + f(n-1)이 성립 피보나치 수열 Fi : 피보나치 i번째 항을 구하는 함수 Fi : Fi-2 + Fi-1 → 재귀로 구현 fibo(n) IF n=2 AND memo[n] = 0 //0은 메모가 안된 상태를 의미 memo[n]