반응형 브루트포스25 백준 15684번 사다리 조작 - C++ 풀이 1. i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면 i와 (i+1)의 위치가 바뀐다. 2. 백트래킹으로 최대 3개의 가로선을 놓는 경우를 모두 시도해본다. 1. i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면 i와 (i+1)의 위치가 바뀐다. i번 세로줄과 (i+1)번 세로줄 사이에 가로줄을 놓으면, 원래 결과 (i, i+1)에서 (i+1, i)로 결과가 바뀐다. 두 세로줄의 위치를 스왑한 것과 같은 효과를 얻게 된다. 이 사실을 이용하여 그어진 가로줄의 목록을 가지고 사다리 게임의 결과를 계산할 수 있다. (아래 코드에서 check() 함수 구현을 참고) 2. 백트래킹으로 최대 3개의 가로선을 놓는 경우를 모두 시도해본다. 백트래킹을 이용하여 최대 3개의 가로선을 긋는 경우를 모두 .. 2022. 6. 24. 백준 1058번 친구 - C++ 풀이 1. 어떤 사람 p의 2-친구수는 p가 아닌 나머지 모든 사람에 대해 2-친구 여부를 판별해서 구할 수 있다. 2. 모든 사람의 2-친구수를 각각 구한 뒤 그 중 최대값을 찾는다. 1. 어떤 사람 p의 2-친구수는 p가 아닌 나머지 모든 사람에 대해 2-친구 여부를 판별해서 구할 수 있다. 어떤 사람 p의 2-친구수는 k(k != p)인 모든 사람에 대해 친구 여부를 판별해서 구할 수 있다. 두 사람 A, B가 2-친구 사이인지 구하려면 두 사람 모두와 친구인 사람 C가 있는지 찾아야 하므로 O(N)의 시간복잡도가 든다. 따라서 어떤 사람 p의 2-친구수를 구하는데는 O(N^2)의 시간복잡도가 들게 된다. 2. 모든 사람의 2-친구수를 각각 구한 뒤 그 중 최대값을 찾는다. 모든 사람에 대해 2-친구수를.. 2022. 6. 1. 백준 25174번 힘겨운 쿠기의 식당 개업기 - C++(cpp) 풀이 1. 좌표압축으로 x, y값 범위를 N이하로 줄인 뒤, 각 좌표에 고양이들의 Z값을 기록한 2차원 배열을 board를 만든다. 2. board의 누적합을 기록한 2차원 배열 psum을 만든다. 3. psum을 활용하여 4분면으로 나누는 모든 경우에 대해 E값을 구한 뒤 최솟값을 찾는다. 1. 좌표압축으로 x, y값 범위를 N이하로 줄인 뒤, 각 좌표에 고양이들의 Z값을 기록한 2차원 배열을 board를 만든다. 좌표평면에서 유의미한 포인트들은 고양이가 위치하는 포인트들이다. 유의미한 두 좌표값 사이의 무의미한 좌표값들은 모두 같은 결과를 만들어낸다. 좌표압축으로 x, y값의 범위를 줄여주자. 2. board의 누적합을 기록한 2차원 배열 psum을 만든다. i 사분면에 있는 Z값 합을 구하기 위해 누적합.. 2022. 5. 17. 백준 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. 백준 5175번 문제없는 문제 - C++(cpp) 풀이 1. N개 문제 중에 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다. 2. 모든 경우를 크기 순, 사전 순으로 탐색하면서 M개의 알고리즘을 모두 커버 가능한지 탐색한다. 1. N개 문제 중에 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다. N개 문제 중에서 세트에 포함시킬 문제만 고르는 경우의 수는 2^N가지이다. N=20이므로 총 2^20가지의 경우가 있고 이는 시간 내에 모두 탐색할 수 있다. 2. 모든 경우를 크기 순, 사전 순으로 탐색하면서 M개의 알고리즘을 모두 커버 가능한지 탐색한다. 이제 모든 경우를 크기 순, 사전 순으로 탐색하면서 최초로 M개의 알고리즘을 모두 커버하는 경우를 찾아내면 된다. 크기 순, 사전 순으로 정렬하기 위해 각 경우를 비트마스크로 나타내고 1의 .. 2022. 4. 11. 이전 1 2 3 4 5 다음 반응형
