개인사

리뷰 모든 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번째 타자가 되는 모든 경우를 탐색하며..

리뷰 10달에 걸친 복수가 완료되었다. 아무것도 모르는 코린이 시절 날 괴롭혔던 문제https://www.acmicpc.net/problem/17484 문제 풀이n과 m값을 받아오고 n * m크기의 맵을 초기화 해준다.열의 개수 * 방향 배열의 개수 m * 3 만큼 for문을 개행시켜 주고, dfs의 매개변수로 열 인덱스와 방향 인덱스를 전달해 준다.0, col 부터 탐색을 시작하여 이전과 같은 방향은 가지 못하도록 탐색을 시작해 준다.현재 행이 n - 1에 도달한 경우 cv값을 ans와 비교해 최소값을 갱신해 준다.모든 탐색이 종료된 후 ans에 저장된 값을 출력해 주면 된다. 참고 사항가지치기로 nv값이 이미 ans보다 크다면 큐에 추가해 줄 필요가 없다.  정답 코드#include#includeus..

리뷰 https://www.acmicpc.net/problem/17471예제가 다 맞길래 제출했는데 1%에서 틀리길래 당황했다. 하지만 질문게시판에 존재하는 몇가지 반례를 보고 문제점을 파악하였다. 문제 풀이n값을 받아주고 정답을 출력할 변수 ans를 10억으로 초기화 해준다.각 노드에 대해 투표권을  입력 받아주고, 인접 배열을 생성해 준다. 나는 노드를 0부터 시작했기 때문에 b에서 1을 빼줬다.벡터 a, b를 초기화 하고 dfs에 매개변수를 level = 0, 빈 벡터a, 빈 벡터b를 전달해 주고 실행하였다.dfs에서는 level이 벡터에 들어있는 노드의 개수이자, 노드 자체를 나타낸다.벡터 a에 level 노드를 넣어주고 재귀를 실행한다, 재귀를 빠져나오면 a에서 노드를 빼준다.벡터 b에 leve..

리뷰 처음엔 주어진 자릿수와 최대 교환 횟수가 적기에 완전 탐색으로 구현하려 했으나 최대 교환 횟수를 모두 소진해야 하기에 백트래킹 구현 시 시간 초과가 출력되었다.따라서 최적의 조건만 생각하는 그리디 알고리즘으로 접근하니 숩게 풀렸다.D3 난이도에서 너무 어렵게 생각했던 것 같다.   SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  문제 풀이각 테스트 케이스에서 숫자를 스트링 s로 받아오고, 최대 교환 횟수를 k로 받아온다.정답 출력용 변수 ans를 0으로 초기화 하고 문자열 s의 크기를 length에 초기화 해준다.탐색할 문자열의 인덱스 level = 0, 교환 횟수 cnt = 0으를 재귀 함수의 매개변수로 ..

리뷰 땅에서 어떠한 물로 이동한다고 생각하면 굉장히 어렵게 느껴지나, 물에서 땅으로 퍼지는 시간을 구하면 쉽게 생각할 수 있는 문제   SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 풀이init 함수를 통해 정답을 출력할 변수 ans를 0으로 초기화 하고, 방문 배열을 전부 -1로 초기화 해준다.input 함수를 통해 n과 m값을 받고 맵 정보를 받아온다, 이때 W의 좌표를 Pos 구조체 타입의 큐 q에 추가해 주고 해당 좌표의 방문 처리를 0으로 초기화 해준다.큐에 담긴 좌표를 통해 bfs 함수를 실행해 준다, 해당 좌표에서 퍼져나갈 수 있는 위치까지 쭉 퍼져나가면 된다.퍼져나가면서 방문 처리는 현재 좌표..

리뷰  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 전형적인 유니온 파인드 문제, 기본적인 코드만 구현하면 해결할 수 있는 문제이다. 문제 풀이테스트 케이스 마다 init 함수를 실행하여 ans를 0으로, 1 ~ n의 노드를 자기 자신을 value로 갖도록 nodes배열을 초기화 한다.query함수를 통해 m개의 간선을 입력 받고 두 노드를 Union 처리를 해준다.solution 함수를 통해 1 ~ n개의 노드 각각을 Find하여 부모를 최신화 하고 자기 자신을 value로 가진 노드를 발견했을 경우 ans를 증가 시켜준다.각 테스트 케이스 마다 ans 값을 출력해 주면 된다. 참고 사항Union 처리 후 자..

리뷰 아ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ 재귀 너무 싫다.https://www.acmicpc.net/problem/17136  문제 풀이input 함수를 통해 맵을 초기화 해주고 1의 총 개수를 변수 one에 저장해 준다. 색종이 5개도 각각 5개씩 저장해 준다.dfs함수를 시작한다 매개변수로는 행, 붙힌 색종이 개수, 남은 1의 개수를 전달해 준다.당연하게도 기저조건은 맵에 1이 존재하지 않는 경우이다, 정답 ans를 갱신하고 리턴해 준다.만약 현재 붙힌 색종이 개수가 ans보다 크거나 같고, 25개 이상을 붙였다면 더 이상 탐색할 필요가 없다.x행부터 탐색을 시작하여 1을 만날 경우 1~5번 인덱스의 색종이를 하나씩 대입해 본다.만약 i번째 색종이를 붙힐 수 있다면 색종이를 붙히고 해당 색종이의 개수를 한개 줄..