cpp(14)
-
[백준] 숨바꼭질 | 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 -
[백준] 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 -
[백준] 2583 | 영역 구하기 | C++
풀이 전에, 선을 기준으로 한 좌표체계를 공간으로 바꾸는 방법은 의외로 간단하다. 오른쪽 위 꼭지점 좌표를 end포인터처럼 생각하면 된다. (소스코드의 input함수 참고) 그러면 아래 그림의 좌표체계를 선이 아닌, 공간처럼 인식할 수 있다. 1. DFS 풀이 DFS 풀이의 핵심은 이렇다. int 영역넓이(전역변수); 풀이함수(solution)에서 좌표마다 반복: 만약 빈 좌표라면: DFS를 돌린다(빈 좌표갯수 count, 인접한 빈 좌표들을 채운다); 반환값1(영역갯수)++; 영역넓이를 반환값2에 저장한다; 영역넓이를 0으로 초기화한다; void DFS(좌표): 현재 좌표를 채운다; 영역넓이++; 4방향반복: 만약 togo좌표가 비어있다면: DFS(togo좌표) 재귀진입; 각 영역마다의 넓이를 전역변수..
2022.07.15