일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 잠실
- C++
- dfs
- dynamic programming
- 삼성 SDS 대학생 알고리즘 특강
- 해커랭크
- 동적 계획법
- 알고리즘
- koitp
- 백트래킹
- 스택
- DP
- hackerrank
- 완전탐색
- 다이나믹 프로그래밍
- Algorithm
- 그리디
- BFS
- 소수
- 브루트포스
- sw expert academy
- 에라토스테네스의 체
- BOJ
- 맛집
- SWEA
- PS
- 구현
- 백준
- 삼성 기출
- 시뮬레이션
- Today
- Total
펭로그
문제링크 : https://boj.kr/11052 123456789101112131415161718192021222324252627282930// BOJ 11052 붕어빵 판매하기#include using namespace std; int max(int a, int b) { return a > b ? a : b;} int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("../input.txt", "r", stdin); int num; cin >> num; vector price(num + 1); // 개당 가격 vector dp(num + 1); // 최대 값 저장 for (int i = 1; i >..
문제 링크 : https://boj.kr/2156 이 문제에서는 연속된 인접 포도주가 최대 2잔까지 허용된다.이 문제에서의 핵심은 포도주를 마시기 위해선 인접한 최대 2개의 노드를 비교했을때 마신 포도주의 위치가 2 이하여야 하는 것이다.포도주를 마신 위치를 1로 하고 안 마신 위치를 0으로 표현하였다. 현재 위치를 기준으로 그 이전 단계를 계산한다면 아래의 경우를 생각할 수 있다.1. 현재 포도주를 먹지 않았을 경우 - 그 앞에 어떤 경우가 와도 상관 없다. 마신경우, 최대 2개까지만 허용 (0+0, 1+0, 1+1+0)2. 현재 포도주를 먹었을 경우 - 바로 전 포도주를 먹지 않았을 수도 있다. (0+1) - 바로 전(-1) 포도주를 먹었다면 반드시 그 이전(-2) 포도주는 먹지 않았어야 한다. (0..
문제 링크 : https://boj.kr/1149 어떤 집을 R, G, B 중 하나로 색칠할 때 인접한 이웃 끼리는 서로 색이 겹치면 안된다. 한 집을 R로 선택하게 되면 그 다음에 올 수 있는 이웃의 값은 G, B 중에 하나만 올 수 있게 된다.그 중에 G를 선택했다면 그 다음 값은 R, B 중에 선택해야 한다.R, G, B의 3가지 값 중에서 하나를 선택하면 그 값을 제외한 2가지를 선택할 수 있다.2가지 선택값 중에서 하나를 선택하면 그 뒤에는 또 2가지를 선택할 수 있는 경우의 수가 주어진다.이 과정을 반복하면 3*2*2*2* .....가지의 경우의 수가 나오며 일반항으로 고쳐보면 3*2^(N-1)가지의 경우를 계산해야 함을 알 수 있다.이를 빅-오 표기법으로 바꿔보면 O(2^N)임을 알 수 있다..
문제 링크 : https://boj.kr/1932 입력이 위 그림과 같이 정삼각형 형태의 피라미드의 형태로 주어진다.이 형태를 어떻게 입력받아야 할까? 하고 고민을 해봤다.첫줄부터 인덱스를 메겨서12 34 5 67 8 9 1011 12 13 14 15이런 형태로 각 줄의 첫 인덱스들이 1, 2, 4, 7, 11 이런 식으로 늘어나는 계차수열 형태로 입력받아야 하는가? 하고 고민도 해봤다. 하지만 입력을 보니 그냥 이런 형태 그대로 입력 받아도 계산하는데는 문제 없겠구나 싶었다.따라서, N*N 형태의 일반 매트릭스 형태로 입력받고 모든 노드를 0으로 초기화 시킨 상태에서 계산하도록 하였다. 이 문제는 재귀로 풀게되면 엄청난 연산 횟수로 시간초과를 발생시킬 수 있는 문제이다.상위 단계에 있는 인접 노드의 값..
문제 링크 : https://boj.kr/1834 이 문제는 막상 해보니 어렵지 않았다.종이에 직접 써보면서 규칙을 찾으니 쉽게 점화식을 찾을 수 있었다. [N = 젯수 일 때, 피젯수(몫,나머지) 순서]N = 1 일 때, 존재하지 않음N = 2 일 때, 3(1,1)N = 3 일 때, 4(1,1) 8(2,2)N = 4 일 때, 5(1,1) 10(2,2) 15(3,3)N = 5 일 때, 6(1,1) 12(2,2) 18(3,3) 24(4,4) 벌써부터 규칙이 보인다.1. 몫과 나머지가 같은 수들은 N+1의 배수들2. 배수의 갯수는 N-1개점화식을 구해보면 (N + 1) * i 가 된다. 단, 이 문제는 입력 최대 값이 2,000,000이기 때문에 최대로 올 수 있는 값은 sigma(i=1~1,999,999)..