본문 바로가기

백준28

[Back Tracking] 백준 15650번 - N과 M (2) 재귀함수를 통해 경우의 수를 찾아가는 방법은 N과 M(1) 블로그 포스팅을 참고! #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' int M, N, min_num, cnt1, cnt2; char input; bool choosed[10]; int answer[10]; void loop(int stage) { if (stage == M + 1) { for (int i = 1; i M; for (int i = 0; i < 8; i++) { choosed[i] = false; } loop(1); } 2021. 1. 23.
[Back Tracking] 백준 15649번 - N과 M(1) N과 M모두 8이하의 수이기 때문에 최대 8중 for문으로 돌아간다. 8^8 Brute Force로 풀 수 있는 문제이다 가변하는 여러 겹의 for를 어떻게 만들것인가? -> 재귀함수 사용한다 choose[] = 이미 선택된 것을 나타내는 배열 answer[] = 답을 순서대로 출력하기 위해서 저장해 놓는 배열 만약 세개를 다 선택했다면 loop를 나간다 나갈때, 답을 출력한다. loop를 나가고 나서 다시 2단계로 돌아올 때 끝난 과정의 3단계에서 choose된 것을 false로 바꾸어 준다 추후 다른 2단계에서 선택된 경우에서 써야 한다 (같은 단계에서는 어차피 for문이 다음으로 넘어가기 때문에 상관 없다) #include #include #inclu.. 2021. 1. 22.
[Brute Force] 백준 1018번 - 체스판 다시 칠하기 시간 제한 : 2초 시간 제한이 2초 라는 것은 1초에 1억 (10^8)번 계산하는 것의 두배 이므로 2*10^8 이다 하나씩 완전 탐색을 한다고 가정했을 때 (M-8)*(N-8)*8*8 번 걸린다. M Black CASE 2) 왼쪽 상단이 White일 때 (가로index + 세로 index) 가 홀수인 경우 => Black (가로index + 세로 index) 가 짝수인 경우 => White vector로 이차원 배열 만들기 vector arr; vectorarr(M, vector(N,'N')); // 이차원 벡터 'N'으로 초기화 //이차원 벡터 탐색 방법 for(int i=0; i> N; min_num = 64; vector arr(M, vector(N, 'N')); for (int i = 0; i.. 2021. 1. 22.
[Greedy] 백준 1080번 - 행렬 그리디.. 어렵고 어렵다 난 일단 문제 읽고 뭔 소리지 싶었다.. 문제부터 막혔다 일단 3 X 3 연산에 대해 생각해보았다 총 (M-3) X (N-3)의 연산이 이루어진다는 것인데...! 매번 연산 하나 할때 마다 행렬 B와 비교해서 최소를 찾는다? 문제점. 어디부분을 연산부터 해야 최소 횟수를 찾을 수 있는것인가 순서대로 하면 최소값 못찾을 거 같고 심지어 B 행렬로 만들어 낼 수 있음에도 못 만들 가능성도 있다 그렇다면???? A 와 B가 다른 부분만 inverse 연산 해주면 된다! 그럼 다른 A와 B가 다른 부분을 표시하는 임시 행렬 tmp를 만들어준다 그럼 이제 tmp 행렬에서 1인 부분만 파악을 해서 그 부분을 기준 삼아 3x3 연산을 실행해 주면 된다 CASE 0 ) 행렬이 같은 경우 사전에.. 2021. 1. 12.

티스토리툴바