패스트캠퍼스 챌린지 31일차

[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.

 

2월 23일 오늘의 강의

백준 1904번 문제

 

 

문제 해석

1. 시간 제한은 0.75초로  Python3로 약 1,500만번 연산 가능함을 알 수 있다.

2. 입력 데이터는 N = 1,000,000로, O(N)으로 문제를 풀어야한다.

3. N의 가짓수에는 N-1의 가짓수가 포함되어 있으므로 DP를 통해 상향식으로 접근한다.

4. 그렇지 않으면 모든 연산을 다 해야하기 때문에 시간 초과가 발생한다.

 

문제 풀이

1. 동적 프로그램 문제를 풀기 위해서는 점화식을 세워야한다.

2. D[i] = 수열의 길이가 i일 때 경우의수라면 D[3] = 3, D[4] = 5이다.

3. 따라서, 점화식은 D[n]은 D[n-1] + D[n-2]이고 이를 DP로 구현한다.

 

 

 

중간에 실수한게 있었는데 삽입할 때 15746으로 나누지 않고 그대로 삽입해서 메모리 초과가 되었다. 앞으로 이런 문제가 있을 경우에는 사전에 나눈 값을 기준으로 리스트에 삽입 시켜줘야겠다.

 

백준 12865번 문제

 

 

문제 해석

1. 시간 제한은 2초로 Python3로 4,000만번 이내에 연산할 수 있다. 

2. 데이터의 크기는 N = 100, K = 100,000이다. 시간 복잡도 O(NK)로 문제를 해결할 수 있다.

3. 배낭에 넣을 수 있는 물건들의 가치 합을 최댓값으로 출력한다.

 

문제 풀이

1. 배낭 문제(Knapsack Problem)로 알려져있는 전형적인 동적 프로그래밍 문제이다.

2. 2차원 배열리스트를 적용해서 최댓값을 갱신한다.

 

 

 

이번 문제는 강의를 참고해서 풀었다. 아직은 익숙하지 않은 문제 유형이라 여러번 풀어보면서 감을 잡는게 중요할 것 같다.

 

백준 11053번 문제

 

 

문제 해석

1. 시간 제한은 1초이며 Python3 기준 약 2,000만번 연산이 가능하다.

2. 데이터의 크기는 N = 1,000, A = 1,000이다.

3. 최장 증가 수열 LIS(Longest Increasing Subsequence) 알고리즘 관련 문제이다.

 

문제 풀이

1. LIS 알고리즘 문제는 전형적인 동적 프로그래밍 문제이다.

2. 수열의 크기가 N개라면, 동적 프로그래밍 알고리즘으로 O(N^2)에 풀 수 있다.

 

 

 

이번 문제도 강의를 참고해서 풀었다. 가장 긴 부분 수열의 길이라고해서 문제 자체를 이해하지 못했는데 막상 문제를 풀어보니까 어느정도 이해가 된 것 같다. 이 부분도 계속 반복적으로 풀어봐야겠다.

 

 

https://bit.ly/37BpXiC

 

패스트캠퍼스 [직장인 실무교육]

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.