차근차근

0. 제목 백준 1697 숨바꼭질 BOJ 1697 숨바꼭질 C++ 1697 숨바꼭질 1. 문제 https://www.acmicpc.net/problem/1697 2. 풀이 완전탐색을 푸는데에 5가지 방법이 있다. brute force(N중 for문) 순열 BFS(최소를 구하는 문제) 비트마스크 백트래킹 이 문제는 BFS를 사용하여 푼다. 현재위치와 현재까지 걸린 시간을 큐에 넣고 조건을 확인해가며 push, pop을 반복한다. 그렇게 반복문을 돌다가 현재위치가 동생이 있는 위치와 같아지게 되면 bfs함수는 현재까지 걸린시간을 반환한다. 3. 코드 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 32 33..

0. 제목 백준 10819 차이를 최대로 BOJ 10819 차이를 최대로 C++ 10819 차이를 최대로 1. 문제 https://www.acmicpc.net/problem/10819 2. 풀이 next_permutation 이라는 STL 함수를 사용하면 된다. next_permutation은 순열의 순서를 바꿔주고 순열이 최종적으로 끝나면(완전하게 역순이 되면) 다시 원래 순서대로 바꾼 뒤 false를 반환해준다. 예를 들어, 1 2 3 4 -> 1 2 4 3 -> 1 3 2 4 -> 1 3 4 2 -> ... -> 4 3 2 1 -> (false반환)1 2 3 4 그리고 처음에 무조건 실행을 하는 do~while문을 사용하였다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

0. 제목 백준 6378 디지털 루트 BOJ 6378 디지털 루트 C++ 6378 디지털 루트 1. 문제 https://www.acmicpc.net/problem/6378 2. 풀이 이 문제의 핵심은 수가 최대 1000자리라는 것이다. int 는 불가능하고 long long 마저도 불가능하다. 따라서 문자열로 입력받는다. 그 후 한자리수가 될 때까지 반복적으로 조건에 따라 계산을 한다. 3. 코드 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 #include #include using namespace std; int main(int argc, const char * argv[]) { string s; int s..

0. 제목 백준 2225 합분해 BOJ 2225 합분해 C++ 2225 합분해 1. 문제 https://www.acmicpc.net/problem/2225 2. 풀이 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다. dp를 이용하였고 dp[K][N]의 의미는 K개의 수로 N을 만드는 경우의 수이다. 예를 들어, dp[3][30]을 구한다고 해보자. 3개로 30을 만들어야 하는 경우이고, 마지막에 더하는 수가 0이라면 2개로 30을 만드는 경우가 나올테고, 마지막에 더하는 수가 1이라면 2개로 29를 만드는 경우가 나올테고, 마지막에 더하는 수가 2라면 2개로 28을 만드는 경우가 나올테다. 위와 같이 쭉 나열해보면 다음과 같은 점화식이 나온다. dp[i][j] = dp..

0. 제목 백준 9461 파도반 수열 BOJ 9461 파도반 수열 C++ 9461 파도반 수열 1. 문제 https://www.acmicpc.net/problem/9461 2. 풀이 점화식을 찾으면 쉽게 풀리는 문제이다. 두가지 점화식으로 풀리는데 다음과 같다. dp[i] = dp[i-2] + dp[i-3] dp[i] = dp[i-1] + dp[i-5] 두가지 중 하나로 코드를 짜면 정답이다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; int main(int argc, const char * argv[]) { int T, N; long int dp[101] = {0}; cin >> ..

0. 제목 백준 1167 트리의 지름 BOJ 1167 트리의 지름 C++ 1167 트리의 지름 1. 문제 https://www.acmicpc.net/problem/1167 2. 풀이 두점 사리의 거리 중 가장 먼 것을 찾아야 하므로 한점을 잡고 그 점으로부터 가장 먼 점을 먼저 찾는다. 찾은 가장 먼 점을 기준으로 잡고 또 다시 그곳으로부터 가장 먼 점을 찾는다. 위와 같은 아이디어를 가지고 시작해보겠다. vector 원소의 자료형으로 pair로 설정하였는데, first에는 연결된 정점, second에는 거리를 저장하였다. 가장 먼 점을 구해야 하기 때문에 bfs를 사용하였다. 기준점으로부터의 거리를 저장하는 dist배열을 만든 후 bfs로 한단계를 거칠때마다 그 거리를 더해준 후 저장한다. 첫번째 bf..

0. 제목 백준 11725 트리의 부모 찾기 BOJ 11725 트리의 부모 찾기 C++ 11725 트리의 부모 찾기 1. 문제 https://www.acmicpc.net/problem/11725 2. 풀이 DFS를 이용하였다. 먼저, vector를 이용해 양방향으로 모두 연결시켜주었다. DFS를 하면서 나아가려는 방향의 노드가 아직 방문하지 않은 상태라면 그 노드를 탐색하게 되고 그와 동시에 방금 있었던 노드를 새로 간 노드의 부모로 설정해주었다. 루트가 1이므로 1부터 DFS를 실시하고 2번 노드의 부모부터 차례로 출력해주면 된다. 3. 코드 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 32 33 ..

0. 제목 백준 2869 달팽이는 올라가고 싶다 BOJ 2869 달팽이는 올라가고 싶다 C++ 2869 달팽이는 올라가고 싶다 1. 문제 https://www.acmicpc.net/problem/2869 2. 풀이 제한시간이 짧기 때문에 for문으로 풀면 시간초과가 나온다. 다른 방식 풀이는 다음과 같다. 하루에 A-B 만큼 올라갈 수 있다. 도달하는 날에는 미끄러질 필요가 없는 것을 고려하여 식을 세운다. V-A 만큼 가면 도착이다. 따라서 V-A까지 A-B 씩 가는 것이다. V-A가 A-B로 나누어 떨어지지 않으면 높이에서 하루 가는 거리를 나눈 값에서 하루를 더해주고 나누어 떨어지면 그대로 높이에서 하루 가는 거리를 나눈 값을 출력해준다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 ..

0. 제목 백준 11651 좌표 정렬하기 2 BOJ 11651 좌표 정렬하기 2 C++ 11651 좌표 정렬하기 2 1. 문제 https://www.acmicpc.net/problem/11651 2. 풀이 vector의 sort기준인 comp함수식만 잘 세우면 되는 문제이다. 좌표쌍을 vector에 넣어줘야 하므로 make_pair를 사용하였다. 3. 코드 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 32 33 #include #include #include using namespace std; typedef pair P; int N; vector v; bool comp(P a, P b){ if(a...

0. 제목 백준 1003 피보나치 함수 BOJ 1003 피보나치 함수 C++ 1003 피보나치 함수 1. 문제 https://www.acmicpc.net/problem/1003 2. 풀이 dp방식을 사용하였다. dp[i][0]은 i 번째 수 계산 시 나오는 0의 개수이고 dp[i][1]은 1의 개수이다. i가 0, 1일때 초기값을 지정해주고 dp[i][k] = dp[i-1][k] + dp[i-2][k] 를 수행해주면 0과 1의 개수를 구할 수 있다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int main(int argc, const char * argv[]) { int..