일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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++
- sw expert academy
- DP
- BFS
- 구현
- hackerrank
- 동적 계획법
- 해커랭크
- Algorithm
- 소수
- 삼성 SDS 대학생 알고리즘 특강
- SWEA
- PS
- 그리디
- dfs
- 브루트포스
- 백트래킹
- BOJ
- 스택
- 완전탐색
- 잠실
- 삼성 기출
- dynamic programming
- 맛집
- 시뮬레이션
- 알고리즘
- koitp
- 백준
- 다이나믹 프로그래밍
- 에라토스테네스의 체
- Today
- Total
목록분류 전체보기 (108)
펭로그
틀림 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667// BOJ 2110 공유기 설치#include using namespace std; struct node { int from; int to; // 우선순위큐 comparator bool operator num >> ap; int input, s = 1000000000, e = 1; vector house(1000000001, false); while (num--) { cin >> input; house[input] = true; s = min(s, input); e = max(..
문제 링크 : https://boj.kr/2293 1234567891011121314151617181920212223242526272829303132// BOJ 2293 동전1#include using namespace std; int dp[10001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("../input.txt", "r", stdin); int num, result; cin >> num >> result; vector coin(num + 1); vector dp(result + 1, 0); for (int i = 1; i > coin[i]; dp[0] = 1; for (int cn :..
문제링크 : https://boj.kr/1463 DP를 사용하면 이전 단계의 계산 결과를 그대로 활용할 수 있는 문제이다.문제에서 힌트로 주어진 10을 연산하는 방법을 생각해보면10 -> 5 -> 4 -> 2 -> 110 -> 9 -> 3 -> 1이런 방법이 나올 수 있을 것이다.10이라는 숫자는 바로 2로 나눌 수 있는 숫자이지만 -1을 한 후에 연산하면 횟수가 더 적은 것을 확인할 수 있다.따라서, 어떤 숫자가 2나 3으로 나눌 수 있을 지라도 -1을 했을 때와 비교한 후 최소 횟수가 어느쪽인지를 취하면 문제를 풀 수 있게 된다. 1을 뺀 후에 연산하는 방법이 어떤 경우에도 허용이 되기 때문에 먼저 1을 빼서 연산한 횟수를 계산한다.현재 숫자에서 1을 뺀 연산은 이전 단계에서 이미 연산이 되었기 때문..
문제링크 : https://boj.kr/2193 이친수의 조건1. 0으로 시작하지 않는다.2. 1이 두번 연속으로 나오지 않는다. 이 조건을 만족하려면 반드시 2자리 이상의 이친수는 10으로 시작하게 된다.그리고 10의 뒷부분 역시 이친수의 조건을 만족해야 이친수가 될 수 있다. DP를 이용하면 간단하게 풀린다.5자리 이친수의 경우 아래와 같이 표현할 수 있다.10+3자리 이친수100+2자리 이친수1000+1자리 이친수10000+0자리 이친수(사실 존재하지 않음) 이를 DP 식으로 표현하면 다음과 같다. 이 식에 따라 아래와 같이 풀어주면 된다.여기서 주의할 점은 47번째 숫자의 값이 2,971,215,073이 되어 int 표현 범위를 초과하게 된다.반드시 long long 타입으로 선언해주어야 한다. ..
문제링크 : https://boj.kr/14501 12345678910111213141516171819202122232425262728293031// BOJ 14501 퇴사#include using namespace std; int max(int a, int b) { return a > b ? a : b;} int dp[17]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("../input.txt", "r", stdin); int num, day, pay; cin >> num; for (int i = 1; i > day >> pay; dp[i + 1] = max(dp[i], dp[i + 1]..
문제링크 : 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)..