Algorithm/문제풀이(29)
-
[백준] 숨바꼭질 | 1697 | C++
풀이의 핵심은 BFS이다. 필자는 배열 안에 걸린시간을 저장하는 방식으로 풀었다. 정답 소스코드 #include using namespace std; int n, k; int arr[100004]; queue Q; void BFS() { while(!Q.empty()) { int x=Q.front(); Q.pop(); if(x==k) return; if(x-1>=0 && x-1=0 && x+1=0 && x*2>n>>k; arr[n]=1; Q.push(n); BFS(); cout
2022.08.20 -
[백준] 12865 | 평범한 배낭 | C++
풀이의 출처: https://chanhuiseok.github.io/posts/improve-6/ 이 문제는 냅색 알고리즘(knapsack algorithm)이 무엇인지 알 수 있게 해주는 문제이다. 풀이의 핵심은 2가지로 나눠서 볼 수 있다. 1. 이차원 다이나믹 테이블 풀이 준비물이 있다. i번째 물건의 무게를 저장하는 배열 W, i번째 물건의 가치를 저장하는 배열 V, i번째 물건까지 고려할 때 j용량까지 담을수 있는 최대가치값 dp[][] dp[i][j]의 의미는 i번째 물건까지 고려할 때, j용량에 담을 수 있는 가치값의 최대합이다. 따라서 다음과 같이 2중 for문을 작성하려 한다. 1번째 물건부터 n번째 물건까지 i반복: 1용량부터 k용량까지 j반복: j번째 용량에 i물건 투입가능: dp[i..
2022.08.17 -
[백준] 14501 | 퇴사 | C++
재귀와 동적계획법으로 풀 수 있다. 1. 재귀(브루트포스) 재귀함수의 변수로는 날짜(인덱스) - int L, 누적상담료 - int psum 으로 설정하였다. 현재 날짜를 L이라고 하자. 날짜 L에 상담을 할 것인지 하지 않을 것인지 선택을 해야 한다. 1. 날짜 L에 상담하기로 선택했다면, 다음에 선택할 수 있는 날짜는 언제인가? 바로 날짜 L+T[L]부터 상담이 가능할 수 있지 않은가? 그리고 여태껏 누적되어온 상담료 psum에 오늘 선택한 상담료 P[L]을 더한다. void f(int L, int psum) { ... f(L+T[L], psum+P[L]); } 다만 조건이 있다. 상담을 진행하는 도중에 휴가날을 맞이할 수는 없는 노릇이다. 그래서 상담할지 선택하기 전에, 다음 상담이 가능한 날짜(L+..
2022.07.21 -
[백준] 17478 | 재귀함수가 뭔가요? | C++
풀이의 핵심은 이렇다. 정답 소스코드 #include using namespace std; int n; void f(int L) { for(int i=0; i
2022.07.20 -
[백준] 1717 | 집합의 표현 | C++
풀이의 핵심은 Union & Find 알고리즘이다. 위 그림을 보면, 노드 1, 2, 3이 한 집합, 노드 4, 5가 한 집합으로 엮여있음을 직관적으로 알 수 있다. (추후, 작성하겠습니다.) 정답 소스코드 #include using namespace std; int n, m; int unf[1000004]; int Find(int v) { if(unf[v]==v) return v; return unf[v]=Find(unf[v]); } void Union(int a, int b) { a=Find(a); b=Find(b); if(a!=b) unf[a]=b; } int main() { ios_base::sync_with_stdio(0); for(int i=1; i>n>>m; int a, b, c; while..
2022.07.19 -
[백준] 4948 | 베르트랑 공준 | C++
풀이의 핵심은 이렇다. i는 2부터 123456*2일 때까지 반복: j는 2부터 i*j값이 123456*2일 때까지 반복: i*j의 값은 소수가 아님을 배열에 저장한다; (n이 입력으로 주어진다.) i는 n+1부터 2*n까지 반복: 저장한 배열의 값으로 소수인지 아닌지 판별한다: 소수라면 count; count한 소수의 갯수 출력(이후 다시 n을 입력으로 받고 반복실행); 소수가 아닌 수를 생각해보자면, 어떤 수의 2배, 3배, 4배, ..., n배는 모두 소수가 아니다. 따라서 어떤 수를 i로 생각하고, 2부터 반복으로 곱해나가서 그 값은 소수가 아니라고 저장하는 것이다. (이 방식은 매우 자주 사용되므로 외우는 편이 낫다.) 정답 소스코드 #include using namespace std; int ..
2022.07.19