강의

https://youtu.be/jZwf4OPlhtk?si=bp2RTqhZAIHz_FVJ

설명

그냥 노가다 문제 브루트포스 알고리즘 같은 거 써야 하는 문제

문제

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x0D.md

15683

에휴.. 최적화 뭐 이런 거 생각할 필요 없고 그냥 브루트포스 문제임

얻어갈 것: 000 001 002 003 010 011 012 013... 머 이렇게 4P3을 구할 때 4진법으로 쉽게 경우의 수를 생각해줄 수 있음

10진법으로 생각해보면 0~9까지의 수로 순열 9P3을 구하면 000 ~ 009, 010 ~ 019, ... 990 ~ 999 이기 때문에
000부터 999까지 for문을 돌리고 %10을 해가며 자릿수 하나하나 떼어서 보면 됨.

이 문제의 경우 기준방향 4개로 cctv개수에 따라 순열을 구하면 되기 때문에 0~4^size - 1 까지 for문을 돌리고 %4를 해가며 자릿수를 떼어서 보면 됨.

for (int t = 0; t < (1 << (2 * size)); ++t) {
		// 4Pk == 4^k == 2^(2 * k) ==> 1 << (2 * k)
		...
		int tmp = t;
		for (int i = 0; i < size; ++i) {
			int dir = tmp % 4; // tmp를 4진법 수로 보고 있으니 %4를 해서 자릿수를 구해줌
			tmp /= 4; // 다음 자릿수를 구해주기 위해 /4
            ...
		}
		...
}

그리고 이 문제의 경우 최적화 안 했을 때 시간복잡도 구해보면

내 경우는 대충 (4 x 8 x 8) x 4^8
제한시간 1초일 때 연산량 1억 정도로 계산하면 된다고 함
백준의 경우 1초당 3~5억 https://syh39.github.io/algorithm/algorithm_2/

암튼 제일 러프하게 구해도 몇천만 정도밖에 안 되니까 최적화 고민할 필요 없이 케이스 잘 나눠서 풀어주면 됐던 문제~~

https://github.com/zhy2on/practice-algorithm/blob/main/BaaarkingDog/0xd/15683.cpp

18808

얻어갈 것: 2차원 배열 90도 회전

void rotate(){
  int tmp[12][12];
  
  for(int i = 0; i < r; i++)
    for(int j = 0; j < c; j++)
      tmp[i][j] = paper[i][j];
  
  for(int i = 0; i < c; i++)
    for(int j = 0; j < r; j++)
      paper[i][j] = tmp[r-1-j][i];

  swap(r, c);
}

12110

앞선 두 문제 합치면 됐던 문제
그래도 헤맸다...........
네 방향 swipe는 보드 자체를 rotate하면 한 방향으로 swipe하는 알고리즘만 만들어서 쓸 수 있음.

얻어갈 것: 블럭을 위치시킬 때 앞 칸으로 한 칸 한 칸 이동하면서 어디서 멈출지 결정하면 O(N^2).
대신 앞전에 위치시킨 인덱스를 저장해서 사용하면 O(N)으로 시간복잡도를 줄일 수 있음.

15686

얻어갈 것: 조합의 경우 최악의 경우가 nC(n/2)~~

그리고 첨에 selected도 벡터로 선언해놓고 selected[t] = chicken[i] 했는데 segfault! 왜냐면 selected가 empty인 상태에서 바로 []로 접근해 줘버렸기 때문에. 그냥 배열로 선언하는 게 나음

pair<int, int> selected[13];
vector<pair<int, int> > chicken, house;