본문 바로가기
반응형

전체 글282

백준 4963번 섬의 개수 - C++(cpp) 풀이 1. 땅인 칸을 정점으로 생각하고, 가로, 세로, 대각선으로 이어져있는 땅들을 간선으로 잇는다. 2. 하나의 섬은 그래프의 연결 요소 하나와 대응된다. 3. DFS/BFS를 사용해 그래프의 연결 요소 개수를 센다. 1. 땅인 칸을 정점으로 생각하고, 가로, 세로, 대각선으로 이어져있는 땅들을 간선으로 잇는다. 주어진 상황을 그래프로 바꾸어 생각할 수 있다. 땅인 칸을 정점으로, 이어져있는 땅들을 간선으로 이으면 그래프가 된다. 2. 하나의 섬은 그래프의 연결 요소 하나와 대응된다. 이제 섬은 그래프의 연결 요소와 같다는 것을 알 수 있다. 3. DFS/BFS를 사용해 그래프의 연결 요소 개수를 센다. 따라서 섬의 개수는 곧 그래프의 연결 요소 개수와 같다. 한 번의 DFS/BFS로 하나의 연결 요소에 속.. 2022. 5. 3.
백준 11055번 가장 큰 증가 부분 수열 - C++(cpp) 풀이 1. dp(idx): idx번째 수로 시작하는 합이 가장 큰 증가 부분 수열의 합 2. dp(idx) = max(arr[idx] + dp(next)) (단, idx < next이고 arr[idx] < arr[next]) 3. dp(i)의 최댓값이 합이 가장 큰 증가 부분 수열의 합이다. 1. dp(idx): idx번째 수로 시작하는 합이 가장 큰 증가 부분 수열의 합 dp(idx)를 idx번째 수로 시작하는, 합이 가장 큰 증가 부분 수열의 합이라고 하자. 2. dp(idx) = max(arr[idx] + dp(next)) (단, idx < next이고 arr[idx] < arr[next]) arr[idx] 뒤에는 arr[idx]보다 더 뒤에있으면서 큰 수만 올 수 있으므로 dp(idx) = idx < .. 2022. 5. 3.
백준 10819번 차이를 최대로 - C++(cpp) 풀이 1. N개의 정수의 순서를 정하는 경우의 수는 N! 2. N이 작으므로 모든 경우를 탐색하여 주어진 식이 최대가 되는 경우를 찾는다. 1. N개의 정수의 순서를 정하는 경우의 수는 N! 크기가 N인 배열에 들어있는 수들의 순서를 바꾸는 경우의 수는 N!이다. 2. N이 작으므로 모든 경우를 탐색하여 주어진 식이 최대가 되는 경우를 찾는다. N이 최대 8이므로 8! = 40,320가지밖에 되지 않는다. 따라서 시간 내에 모두 탐색하는 것이 가능하다. 재귀와 비트 마스크를 이용해서 모든 경우를 탐색하고 최대가 되는 경우를 찾으면 된다. #include #include #include using namespace std; int N; int arr[8], pick[8]; int brute_force(int i.. 2022. 5. 3.
백준 2644번 촌수계산 - C++(cpp) 풀이 1. 각 사람을 정점, 부모 자식 관계를 간선으로 연결하면 결과는 트리를 이룬다. 2. 촌수는 트리에서 두 정점 간의 거리와 같다. 3. DFS나 BFS로 두 정점간의 거리를 구한다. 1. 각 사람을 정점, 부모 자식 관계를 간선으로 연결하면 결과는 트리를 이룬다. 부모 자식 관계에서 사이클이 생성되는 것은 불가능하다. 따라서 결과는 항상 트리 구조이다. 2. 촌수는 트리에서 두 정점 간의 거리와 같다. 촌수는 트리에서 두 정점 사이의 간선의 개수, 즉 두 정점간의 거리를 뜻한다. 3. DFS나 BFS로 두 정점간의 거리를 구한다. DFS나 BFS로 두 정점 간의 거리를 구하면 된다. 이때 트리에서 두 정점이 연결되어있지 않으면 촌수를 계산할 수 없는 경우이다. #include #include using.. 2022. 5. 2.
백준 1475번 방 번호 - C++(cpp) 풀이 1. 9는 6이라고 생각하고, 0-8까지 숫자의 등장 횟수를 카운트한다. 2. N개의 숫자 i를 나타내기 위해서는 N개의 세트가 필요하다. 단 6의 경우 한 세트에 6이 두 개씩 들어있으므로(9=6으로 생각하면) ceil(N/2) 개의 세트가 필요하다. 3. 각 숫자를 나타내기 위해 필요한 세트 개수 중 최댓값이 필요한 세트 개수의 최솟값이다. 1. 9는 6이라고 생각하고, 0-8까지 숫자의 등장 횟수를 카운트한다. 6과 9는 뒤집어서 사용할 수 있으므로 같은 숫자로 취급해도 무방하다. 각 숫자의 등장 횟수를 카운트해주는데, 9는 6으로 취급해서 카운트해준다. 2. N개의 숫자 i를 나타내기 위해서는 N개의 세트가 필요하다. 단 6의 경우 한 세트에 6이 두 개씩 들어있으므로(9=6으로 생각하면) cei.. 2022. 4. 19.
반응형

티스토리툴바