SW

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..

0. 제목 백준 14501 퇴사 BOJ 14501 퇴사 C++ 14501 퇴사 1. 문제 https://www.acmicpc.net/problem/14501 2. 풀이 dp방식을 사용하였으며 dp배열의 원소값을 0으로 모두 초기화 하고 시작하였다. 만약 일을 진행하는데 주어진 날보다 초과되면 dp[i+1] 값을 해주면 된다. 초기에 0으로 초기화해주었기 때문에 N이 초과되어도 0으로 갱신이 가능하다. 주어진 날 내에 끝낼 수 있다면 dp[i] = max(dp[i+T[i]] + P[i], dp[i+1]); 을 수행해준다. 위 점화식을 풀어 설명해보면 dp[i+T[i]]+P[i] 는 i번째 상담을 수행하면 T[i]일간 상담을 못하고 P[i]의 금액을 얻을 수 있고, dp[i+1]은 i번째 상담을 수행하지 않..

0. 제목 백준 2309 일곱 난쟁이 BOJ 2309 일곱 난쟁이 C++ 2309 일곱 난쟁이 1. 문제 https://www.acmicpc.net/problem/2309 2. 풀이 9명의 난쟁이중 2명을 제외한 나머지의 합을 모두 구한 후 100과 비교해본다. 2명을 제외한 나머지를 vector에 넣고 오름차순 정렬 후 출력한다. 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 34 35 36 37 #include #include #include using namespace std; int main(int argc, const char * argv[]) { int A[10]; in..

0. 제목 백준 1931 회의실배정 BOJ 1931 회의실배정 C++ 1931 회의실배정 1. 문제 https://www.acmicpc.net/problem/1931 2. 풀이 최대 회의수를 구해야하기 때문에 시작시간을 기준으로 잡으면 안되고 종료시간을 기준으로 잡아야 한다. 시작시간을 기준으로 잡아버리면 (1, 10)이 있다고 할 때 (3, 5), (6, 8)이 들어갈 수 없기 때문에 최대수를 구할 수 없다. 따라서 종료시간으로 오름차순 정렬을 한 후, 만약 종료시간이 같다면 시작시간 기준으로 오름차순 정렬을 해준다. 현재 종료시간보다 나중에 있는 시작시간이 있다면 회의수인 cnt를 1증가시키고 현재 종료시간을 나중에 있는 종료시간으로 갱신해준다. 반복문의 모든 loop를 끝낸 이후의 cnt가 최대 회..

0. 제목 백준 1783 병든 나이트 BOJ 1783 병든 나이트 C++ 1783 병든 나이트 1. 문제 https://www.acmicpc.net/problem/1783 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 #include using namespace std; int main(int argc, const char * argv[]) { int N, M; int result = 1; cin >> N >> M; if(N == 1) result = 1; else if(N == 2){ result = min(4, (M+1)/2); }else if(N >= 3){ i..

0. 제목 백준 2178 미로 탐색 BOJ 2178 미로 탐색 C++ 2178 미로 탐색 1. 문제 https://www.acmicpc.net/problem/2178 2. 풀이 최단거리 구하는 문제로 BFS를 사용하였다. make_pair를 사용하여 좌표쌍을 큐에 push하였다. BFS특성상 한단계씩 뻗어 나가기때문에 최단거리를 구하는데 적합하다. 큐에는 탐색할 좌표들을 담아놓는다. 큐에 있는 좌표가 더이상 주변의 탐색을 모두 끝낸 좌표일때 pop을 해준다. dist배열의 값이 0이면 아직 방문하지 않은 것이고 1 이상이면 방문을 했다는 것이고 1이상의 숫자는 dist[i][j] 에 오기까지 거친 블록의 수이다. 주의할 점으로는 입력을 받을때 연속해서 받기때문에 scanf("%1d", &arr[i][j]..