1. 본캠프 시작
- 본캠프 OT
- Chapter 1 Blueprint 세션 및 과제
- 개인 공부
2. 본캠프 OT
- 간단한 부트캠프 소개와 튜터님들 소개
- 앞으로의 커리큘럼
- 기타 필수 공지 안내
3. 개인공부
- C++ 코딩테스트 완전정복 강의 (1-2, 1-3)
- 비주얼 스튜디오 환경 C++17버전으로 셋팅 (이전까지는 C++14였음 어쩐지 알고리즘 문제풀랑 다르더라...)
- 효율적인 공부법 : 단순 문제풀이X 지금까지 푼 문제 통계를 보고 취약한 유형의 문제에 집중 (하기싫어서 미루던 BFS, DFS, 그래프 문제들...)
- 효율적인 풀이 : 문제요약(3문장요약: 요구 성능, 예외사항, 키워드) → 입출력 분석(예시 입력 작성) → 전략 설계(예시 입력 작성) → 구현(전체 과정의 30%)
- 실버3 9461번 파도반 수열 (다이나믹 프로그래밍)
- 첫 시도에 방법은 맞았으나 N == 100일때 출력이 -가 나옴 N == 100부터 거슬러올라가다 정상적인 출력에서 10억이 넘어가는 것을 발견 == 오버플로우
- int로 받던 것들을 long long으로 수정하여 해결
// 실버3 9461번 파도반 수열(다이나믹 프로그래밍)
#include <iostream>
#include <vector>
using namespace std;
vector<long> P(101, 0);
long long DP(int N)
{
P[0] = 0;
P[1] = 1;
P[2] = 1;
P[3] = 1;
P[4] = 2;
for (int i = 5; i <= N; i++)
{
P[i] = P[i - 1] + P[i - 5];
}
return P[N];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
for (int i = 0; i < T; i++)
{
int N;
long long result;
cin >> N;
result = DP(N);
cout << result << '\n';
}
return 0;
}
// 실버3 9461번 파도반 수열(다이나믹 프로그래밍) 개선
#include <iostream>
#include <vector>
using namespace std;
vector<long long> P(101, 0);
void DP()
{
P[0] = 0;
P[1] = 1;
P[2] = 1;
P[3] = 1;
P[4] = 2;
for (int i = 5; i <= 100; i++)
{
//P[i] = P[i - 2] + P[i - 3]도 같은 결과 대신 P[1] = P[2] = P[3] = 1; 로 좀더 깔끔하게 초기 입력가능 i = 4 부터
P[i] = P[i - 1] + P[i - 5];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//for 문안에서 매번 호출하는 것 보다 한번만 호출 해준다음 For문에서는 N만 입력해서 해결
DP();
int T;
cin >> T;
for (int i = 0; i < T; i++)
{
int N;
cin >> N;
// 위에서 DP()를 호출해서 이미 저장되어있는 P배열 중에 P[N]를 출력
cout << P[N] << '\n';
}
return 0;
}
- 실버3 1172번 타일링2 (다이나믹 프로그래밍)
- 비슷한 다이나믹 프로그래밍은 이전에도 풀어봤으나 이번에는 2 x 2 블록이 추가된 형태 이전의 규칙과는 달라 점화식을 다시 찾아야했음
- 지금까지의 경험으로는 처음부터 점화식의 규칙을 찾기보다는 일단 손계산을 하며 점화식을 고려하는 것이 좋았음 이에 바로 계산부터 시작해 패턴을 찾음 (그림판에 무작정 그리는 것도 방법)
- (DP[i - 1] * 2)에서 짝수일경우 + 1 홀수일경우 -1로 계산되는 것을 확인 바로 적용하고 % 10007 로 오버플로우 방지 정답 확인 후 찾아보니 DP[i] = (DP[i - 1] + 2 * DP[i - 2]) % 10007 로 푸는 방법도 있었음
// 실버3 11727번 타일링2(다이나믹 프로그래밍)
#include <iostream>
#include <vector>
using namespace std;
// 어차피 10007로 나눈 나머지를 저장해 갈건데 굳이 long long을 안써도 됐을것 같음
vector<long long> DP(1001, 0);
void P()
{
DP[1] = 1;
DP[2] = 3;
DP[3] = 5;
// 아래 for문 DP는 배열을 0부터 1000까지 1001개 할당했는데 DP[1001]에 접근해서 문제가 생김 1000까지로 조정해서 해결함
for (int i = 4; i <= 1000; i++)
{
if (i % 2 == 0)
{
DP[i] = ((DP[i - 1] * 2) + 1) % 10007;
}
else
{
DP[i] = ((DP[i - 1] * 2) - 1) % 10007;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
P();
int N;
cin >> N;
cout << DP[N] << '\n';
return 0;
}
4. 내일 일정
- 라이브 세션 참가 및 개인 공부
til, 내일배움캠프, 사전캠프, 알고리즘, 언리얼, 해시 맵
