4일차 강의요약 (13강)

13강 (시뮬레이션)

1. 상하좌우는 dy[4], dx[4]를 적극사용
2. 매번 반복문을 돌면서 시작위치를 탐색하기보다는
vector<pair<int, int>> pos에 미리 시작위치를 입력받을 때 저장해두는 것이좋다
3. bfs에서와 마찬가지로 특정 index를 활용하여 bool visited 배열의 사용 없이
방문여부를 체크할 수 있다.
4. 이전 값을 저장해둠으로써 false로 되돌리는 효과를 얻을 수 있다.

 

각 CCTV의 방향을 정해야함 >> 16가지의 가능성 (백트래킹)

변수들이 가질 수 있는 값이 여러개이고 모든 조합을 확인하고 싶은 상황에서

변수들끼리는 서로 독립적일 때 백트래킹대신 진법 이용하면 더 쉬움

 

가능한 종류가 4개 → 4진법사용 000~333 각각의 자리를 방향 3개에 대응시킴

39는 4진법으로 213 → 방향 (2,1,3) 이를 통해 모든 조합을 다 확인해볼 수 있음

cctv가 k개 있다고 할 때 tmp는 0부터 4^k-1까지 돌아야 함

4^k -1 계산 → 1<<(2*cctv.size())

 

- 2차원 배열을 회전시킬 때 헷갈릴 경우 직접 종이에 좌표를 써두고 돌려보면 직관적이다.

(수에서 규칙을 찾는다고 생각)

- utility 헤더안에 있는 swap 함수 활용 가능

- index와 관련해서 처리할때 매번 n개를 검사하기보다는 삽입할위치를 저장하는 변수를 하나 추가하여 (idx)

O(n)으로 관리함과 동시에 bool visited 배열의 기능도 대체할 수 있다.

- 일반 스티커와 같은 배열을 회전시키는 방법외에도 "게임판 자체"를 회전시켜서 회전의 효과를 줄 수 있다.

- 순열, 조합문제와 같은경우 next_permutation을 이용해 백트래킹을 사용하지 않고 간결하게 처리할 수 있다.

- 가지치기 유의하기 (조합)