본문 바로가기

알고리즘74

[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] 백준 19639번 - 배틀로얄 일단 정답률이 27%라서 쫄았다 오늘 하루는 이거겠구나 하는 생각으로 시작한다 i번째 줄의 수 Vi가 음수라면, i번째 행동에 −Vi번째 적을 죽인다. i번째 줄의 수 Vi가 양수라면, i번째 행동에 Vi번째 아이템을 먹는다. 준석 제외 플레이어 수 = X 체력 회복 아이템 수 = Y 준석의 처음 및 최대 체력 = M (짝수) 준석이의 체력 잃는 양 그렇게 먹으나 1/2 초과 될때까지 포션들 집어 먹는 것이나 똑같지 않나? -> 그래서 예제에서는 크기 상관없이 1번째(3) 죽이고 2번째(5)죽이고 그랬구나? => 1/2 초과될 때까지 포션 먹는 것으로! 3. 그렇다면 포션 총 회복량 + M 사실상 적들을 치는 순서가 .. 2021. 1. 18.

티스토리툴바