devlog

출처 : https://www.acmicpc.net/problem/18234 풀이 방법pi는 wi보다 항상 크다.라는 조건에 의해 그리디로 풀이할 수 있음을 파악했다.pi는 당근을 뽑지 않으면 계속해서 누적되다가 해당 당근을 뽑게 된다면 누적된 pi와 wi만큼 맛을 얻을 수 있다.이를 통해 T일 전까지 가장 큰 pi를 계속 누적을 하다 마지막에 뽑는 것이 가장 많은 맛을 얻을 수 있다는 것을 알 수 있다. 또한 pi는 wi보다 항상 크다라는 조건에 의해, 만약 T가 6이고 당근이 3종류라면 6, 5, 4일 차에만 당근을 뽑아 먹고, 1, 2, 3일 차에는 당근을 안 뽑아 먹는 것이 더 크다는 조건을 알 수 있다. (만약 뽑게 된다면, wi가 중간에 포함되어야 하기 때문에 안 뽑고 Pi만큼 얻는게 더 좋다..

출처 : https://www.acmicpc.net/problem/17398 풀이 방법풀이의 방법만 안다면 구현은 간단한 문제였다. 간선을 하나씩 끊어 가면서 이때 나누어진 두 집합의 노드의 수를 계산하는 문제이다.만약 간선을 끊을 때마다, 끊어진 두 노드에서 bfs 또는 dfs를 수행해서 각 집합의 노드의 수를 계산하게 된다면 시간 복잡도가 초과된다.그렇게 때문에 nlogn 이하의 시간 복잡도를 가지는 알고리즘을 생각해 내야 했다. 지금 까지 공부하며 시간 복잡도를 줄였던 방법에 대해 생각해 보았다. 1. 노드기준이 아닌 엣지 기준으로 생각해 보기2. 방향 간선에선 간선의 방향을 바꾸어 보기3. 순서를 역으로 생각해 보기 등등 생각이 났지만, 이 문제에 적용할 수 있는 방법은 역으로 생각하기였다. 1...

출처 : https://www.acmicpc.net/problem/7812 풀이 방법처음엔 문제의 케이스가 여러 번 주어진다는 것을 보지 못하고 O(n^2)으로 풀이할 수 있어서 풀이했지만, 케이스가 여러 개 주어지므로 시간 초과가 발생한다. 즉 O(n)만에 풀이를 해야한다. 항상 트리 문제를 풀이할 땐, 문제가 풀리지 않는다면 노드를 기준이 아닌 엣지를 기준으로 생각해 보아야 한다.A가 중앙일 때와 B가 중앙일 때를 비교해 보면 A와 B를 연결하는 엣지의 더해지는 횟수만 변경되고 나머지 엣지는 유지된다.이 점에 초점을 맞추어서 고민을 해보았다. 정답은 서브트리와 관련이 있었다.A에서 B로 이동할 때 A-B엣지가 더해지는 수는 (B 쪽 엣지를 끊고 난 후 A의 자식 수) - (A쪽 엣지를 끊고 난 후 B..

출처 : https://www.acmicpc.net/problem/12865 풀이 방법,이번 문제는 0-1 배낭 문제(0-1 Knapsack Problem)로, 1차원 DP를 활용하여 최적의 해결법을 찾는다.DP 배열을 사용하여 주어진 무게 제한 내에서 최대 가치를 찾는 방식으로 풀이하였다. 1. DP 배열 정의• dp[j] → 무게 j일 때 배낭에 담을 수 있는 최대 가치를 저장• 초기값은 0으로 설정2. 각 물건을 순회하며 DP 테이블 갱신• 현재 물건을 넣을 수 있는 최대 무게부터 역순으로 탐색 (이전 값이 유지되도록)• 현재 가방을 선택하는 경우 vs. 선택하지 않는 경우를 비교하여 dp 갱신 dp[j] = max(dp[j], dp[j - weight] + value) import java.io...

출처 : https://www.acmicpc.net/problem/2138 풀이 방법이 문제는 전구를 켜는 순서가 중요하지 않으며, 또한, 전구를 여러 번 켜고 끄더라도 같은 상태로 반복하므로, 각 전구는 0번 또는 1번만 변경하면 된다는 점을 파악하는 것이 중요하다. (2번 스위치 하는 것은 0번 스위치 하는 것과 동일) 문제 해결을 위해 첫 번째 전구부터 시작하여 전구를 바꾸는 경우와 그대로 두는 경우를 고려하며 탐색한다. 이 과정에서 현재 인덱스 이전의 전구가 원하는 정답 상태와 다르다면, 반드시 현재 전구를 바꿔야 한다는 규칙을 도출할 수 있다. 이러한 방식으로 인덱스를 늘려가며 조건을 적용해 나가면 최소 횟수로 전구를 원하는 상태로 만들 수 있다. #include #include #include..

출처 : https://www.acmicpc.net/problem/14466 풀이 방법먼저 문제를 이해하는 것이 중요하다.농장에서 다리가 없는 곳은 자유롭게 이동이 가능하지만, 다리가 연결된 곳은 다리를 건너야 이동이 가능하다.주어진 예시를 통해 이해해 보자위 이미지에서 체크가 소의 위치 사각형의 변에 동그라미가 다리의 위치이면, (3,3)의 위치로 이동하기 위해선 무조건 다리를 건너야 한다.하지만, (2, 2)와 (2, 3)은 다리를 이용하지 않고 돌아서 (2, 2), (1, 2), (1, 3), (2, 3)와 같이 다리를 이용하지 않고 이동이 가능하다. 이 문제를 쉽게 구현하기 위해, 다리를 저장하는 자료구조가 중요했다.다리라는 3차원 배열을 선언한 뒤 bridge [y][x][dir] 해당 배열을 ..

출처 : https://www.acmicpc.net/problem/23289 풀이 방법시뮬레이션 문제이므로 조건 정리를 꼼꼼하게 하고 풀이하면 된다. 해당 문제에서 가장 까다로운 부분은 벽을 처리하는 것이다.입력으로 주어지는 벽은 현재 칸에서 위 쪽에 있거나, 오른쪽에 있는데 이렇게 된다면 벽을 처리하기 위해 항상 해당 벽의 왼쪽 좌표나 아래쪽 좌표를 확인해야 한다는 불편함이 있다. 이를 해결하기 위해 입력을 받을 때 해당 벽의 양쪽 좌표에 벽을 표시해 주었다. 가령 a, b의 위쪽에 벽이 있다면, wall[a][b][2] = 1, wall [a-1][b][3] = 1로 y, x의 좌표에 dir (오른쪽, 왼쪽, 위쪽, 아래쪽)으로 설정해서 문제를 풀이하였다. 운풍기를 돌리기 위해 Fan 구조체를 정의하..

출처 : https://www.acmicpc.net/problem/20188 풀이 방법완전 탐색으로 노드를 기준으로 하면 시간 복잡도가 N^2 이므로 시간 초과된다.시간 복잡도를 줄이기 위해 DP를 사용할까 했지만, 노드를 기준으로 문제를 완벽하게 분리하는 것이 쉽지 않았다.이럴 때 필요한 것이 역발상 즉 간선을 기준으로 생각해 보면 정답을 구할 수 있다. 위 그림에서 5-6을 잇는 간선을 지나가는 경우는 5를 루트로 하는 서브트리의 노드 중 2개를 선택하거나, 5의 서브트리 노드 중 하나를 선택하고, 1, 4, 3중에 하나를 선택하는 경우라고 알 수 있다.그러므로, 각 노드를 루트로 가지는 서브트리에서 노드의 수를 계산해 주면 된다. 이는 dfs로 계산하고, 나온 값이 ret라고 하면, ret * (r..

출처 : https://www.acmicpc.net/problem/22954 풀이 방법처음에는 유니온 파인드 문제인 줄 알았지만 굳이 구현할 필요는 없었다.1. bfs 함수를 통해 트리를 만든다.-> 1번에서 만든 트리의 노드가 n개 라면 -> 문제의 조건에서 1개 이상이기만 하면 되므로 마지막에 방문한 노드만 분리하고 답을 도출한다.2. 만약 1번에서 구한 노드의 개수가 n보다 작으면 다음 방문을 안 한 노드를 기준으로 bfs를 진행한다.-> 2번에서 진행한 bfs를 통해 구한 노드의 수의 합과 1번에서 구한 노드의 수의 합 n이 아니라면 2개 이상으로 분할이 되므로 -1을 출력-> 만약 1, 2번에서 구한 노드의 수가 같으면 문제의 조건인 다른 개수의 노드를 가진 트리에 위반하므로 -1를 출력 주의 ..

출처 : https://www.acmicpc.net/problem/3687풀이 방법각 수를 만드는데 필요한 성냥개비의 수를 알아보자1 = 2개2 = 5개3 = 5개4 = 4개5 = 5개6 = 6개7 = 3개8 = 7개9 = 6개0 = 6개 가장 큰 수를 만드는 것은 가장 자릿수가 많아야 한다.가장 자리수가 많기 위해선 가장 작게 성냥개비를 사용할 수 있는 수를 최대한 많이 추가해야 하는데필요한 성냥의 수를 보면 너무 좋게 2개를 사용해서 1, 3개를 사용해서 7을 만들 수 있어 그리디 하게 풀방법을 생각해 낼 수 있었다.만약 주어진 성냥개비수가 홀수이면 맨 앞을 7로 나머지 뒤는 모두 1로, 반대로 짝수이면 모든 수를 1로 채워 넣으면 가장 큰 자릿수를 만들 수 있고 이것이 가장 큰 수가 된다. 가장 작..