개인사

리뷰 2048(Easy)의 어려운 버전, 재귀의 깊이가 기존 5에서 10으로 늘어났다. [G1] 백준 12100번 2048 (Easy) C++ 백트래킹, 구현, 시뮬레이션, 브루트포스 알고리즘리뷰 2048게임을 구현하는 문제, 시뮬레이션만 잘 작성하면 쉽게 풀 수 있으나 문제를 잘 읽어보아야 할듯 하다.https://www.acmicpc.net/problem/12100 문제 풀이전역 변수n : 맵의 행, 열을 저장할 변수anszzzz955.tistory.com 가지치기를 최소 두개를 추가해 줘야 시간 초과를 막을 수 있는 문제인 듯https://www.acmicpc.net/problem/12094 전역 변수n, ans : 맵의 행과 열의 길이를 저장할 정수형 변수 n, 최대값을 저장할 변수 ansmap ..

리뷰 2048게임을 구현하는 문제, 시뮬레이션만 잘 작성하면 쉽게 풀 수 있으나 문제를 잘 읽어보아야 할듯 하다.https://www.acmicpc.net/problem/12100 문제 풀이전역 변수n : 맵의 행, 열을 저장할 변수ans : 최대값을 저장하기 위한 변수map : 맵 정보를 입력받을 2차원 정수형 벡터 n값을 입력 받고 map을 n * n크기로 초기화 해준 뒤 맵의 정보을 입력 받아준다.dfs를 통해 상하좌우로 미는 작업을 완전 탐색으로 구현해 준다, 매개변수는 시도한 횟수 level과 맵을 참조한다.기저 조건으로 level이 5에 도달하면 5번 작업을 한 상태이므로 맵을 체크하여 최대 값을 갱신해 준다.4방향으로 탐색을 하며 상하좌우로 맵을 미는 작업을 한 후에 재귀를 실행해 준다.이때..

리뷰 문제를 제대로 읽지 않아 대각선까지 일치해야 하는줄 알았다.처음엔 해쉬 + Find를 통해 풀어야 하나 고민했는데 깊게 생각하지 않고 열, 행, 그룹으로 방문처리 하며 재귀를 사용하면 된다. 너무 어렵게 생각하지 말자https://www.acmicpc.net/problem/2239 문제 풀이전역 변수lst : 맵 정보를 나타낼 정수형 2차 배열cnt : 맵에 남아있는 0의 개수를 체크할 변수flag : 스도쿠 퍼즐이 완성되었는지 체크할 변수cols : 현재 행 기준 모든 열의 방문처리를 체크할 정수형 2차 배열rows : 현재 열 기준 모든 행의 방문처리를 체크할 정수형 2차 배열groups : 3*3 크기의 그룹 내의 방문처리를 체크할 정수형 3차 배열 9 * 9 크기의 for문을 개행해 준다 처..

리뷰 시작 문자열이 특정 조건을 가진 문자열을 더해 도착 문자열로 변할 수 있는지 여부를 체크하는 문제https://www.acmicpc.net/problem/12919 문제 풀이문자열 a와 b를 입력 받고, b의 크기에서 a크기를 뺀 값을 limit으로 저장한다. 이는 백트래킹의 기저조건이 될 값이다.변수 flag를 0으로 초기화 하고 함수 bt에 매개변수 0을 전달하여 백트래킹을 시작한다. 이때 0은 재귀 단계를 나타낸다.백트래킹의 기저조건은 flag가 1일때와 level이 limit에 도달했을 때다, 이는 둘의 문자열의 길이가 동일할때를 의미한다.문자열 a에서 b로 가는 재귀 말고, 문자열 b에서 a로 가는 재귀를 실행해 줄 것이다.만약 문자열 b의 앞이 B라면 문자열을 뒤집은 후 맨 뒤의 B를 삭..

리뷰 벽을 정확히 3개를 세워 학생들이 선생님의 눈을 피할 수 있게 하는 완전 탐색 문제https://www.acmicpc.net/problem/18428 문제 풀이전역 변수로 맵의 변의 크기 n, 정답 여부체크용 ans, 맵 lst, 방문 여부 v, 방향배열, 선생님 정보 T를 설정해 준다.input 함수를 통해 n값과 맵의 정보를 받는다, 이때 T가 입력된 경우 구조체 Pos타입 벡터 T에 추가해 준다.dfs 함수를 통해 완전 탐색을 돌려준다. 매개변수 level은 벽 설치 개수, row는 탐색을 재개할 행 정보다.벽의 개수가 3개가 되면 기저조건에 해당된다, bfs를 통해 시뮬레이션을 돌려준다.선생님을 순회하며 4방향으로 감시를 시작한다, 범위를 벗어나거나 벽을 만나기 전까지 해당 방향을 쭉 탐색한..

리뷰 문제 풀이전역변수로 테케의 수 tc와 지렁이의 수 n, 이동과 대기한 수를 나타낼 Move, Stay 정답 변수 ans를 설정한다.init 함수를 통해 ans를 최대한 큰 값, Move와 Stay를 0으로 초기화 해준다.input 함수를 통해 n값과 n개의 지렁이의 좌표를 Pos 구조체를 활용하여 pos배열에 저장해 준다.dfs 함수를 통해 각 지렁이가 짝을 지었을때의 좌표 벡터값을 구해줄 것이다.매개변수로는 지렁이 인덱스를 나타낼 level과 x좌표의 값 sumX, y좌표의 값 sumY를 전달해 준다.Move와 Stay가 각각 n / 2보다 작을 경우 Move와 Stay를 각각 증가시켜주고 재귀를 진행하면 된다.재귀를 전달할땐 level인덱스의 x, y좌표를 sumX, sumY에 더해주고 leve..

리뷰 모든 CCTV가 바라볼 수 있는 모든 방향을 체크하고 사각지대가 제일 적은 케이스를 찾는 문제https://www.acmicpc.net/problem/15683 문제 풀이전역 변수로는 맵, 방향 배열과 행의 개수 n, 열의 개수 m, cctv의 개수 k, 정답을 출력할 ans를 설정했다.n과 m값을 받아오고 n * m의 맵을 받아온다. 이때 현재 들어온 값이 1이상 이라면 별도의 처리가 필요하다.입력값이 6인 경우 벽이므로 continue, 1 ~ 5 사이라면 CCTV이므로 cctv 배열에 추가해 준 뒤 k의 개수를 증가시킨다.이때 각 CCTV의 시야는 모두 다르므로 구조체 CCTV의 look에 각각의 시야각을 추가해 준다.CCTV들의 방향을 저장할 빈 벡터 dirs를 초기화 하고 level 0부터..

리뷰 어렵다고 생각이 들진 않았는데 생각보다 엣지케이스가 많아서 오답이 많이 노출되었다... 후https://www.acmicpc.net/problem/17142 문제 풀이n과 m을 입력 받고 맵 정보를 초기화 한다. 만약 맵에 2가 존재한다면 Pos구조체 타입의 virus 벡터에 추가해 준다.입력을 다 받고 나서 length 변수에 virus의 크기를 저장해 주고 dfs를 실행해 준다.dfs를 통해 virus의 크기만큼의 반복을 돌며 중복이 없고 순서가 있는 탐색을 진행해 준다.기저조건은 level이 m이 도달했을 때이다, path 변수에 저장된 인덱스를 갖고 bfs를 실행해 준다.방문 배열부터 초기화 해준다, 이때 벽의 경우에는 미리 0으로 초기화 해주고 나머지는 -1로 초기화 해준다.path에 저장..

리뷰 완전 탐색을 통해 배열을 돌리는 경우의 수를 모두 실행하고 최적값을 찾는 문제회전을 하는 횟수인 k의 범위가 6으로 작아서 완전 탐색을 돌려도 시간이 크게 많이 걸리지는 않았다. https://www.acmicpc.net/problem/17406 문제 풀이input 함수를 통해 n, m, k값을 입력 받고 2차 배열 정보를 받아준다.k번에 걸쳐 회전을 할 좌표를 받고, 회전할 범위를 받은 뒤 구조체 배열 pos에 전달해 준다.좌표 인덱스를 받을 빈 벡터 path를 초기화 해주고, dfs 함수의 매개변수로 0과 path를 전달해 준다.dfs 함수를 통해 k! 개의 경우의 수를 구해준다. 매번 방문 처리 후 path에 회전할 순서를 저장해 주면 된다.재귀가 k번째에 달했을때 simul 함수에 path와..

리뷰 백트래킹 + 구현 + 시뮬레이션 문제, 시간 분배를 잘 해줘야 한다.https://www.acmicpc.net/problem/17281 문제 풀이이닝의 수 n값을 받아오고 2차 정수 배열 inning에 i번째 이닝에 j번 타자가 치는 정보를 받아온다.빈 벡터 temp를 초기화 하고 dfs를 통해 완전 탐색을 돌려준다.dfs의 매개변수로는 현재 타자의 수 level과 타자의 번호를 저장한 벡터 turn을 받아준다.level이 9 즉, 9명의 타자가 모두 모아졌을때가 기저조건이 되며 simul함수를 호출하고 리턴한다.level이 3 즉, 4번 타자의 정보를 받아올때는 0번 인덱스 (1번타자)를 추가해 주고 리턴한다.1 ~ 8인덱스 즉, 2 ~ 9번 타자가 level번째 타자가 되는 모든 경우를 탐색하며..