브루트포스 알고리즘 (5) 썸네일형 리스트형 [백준 17825][C++] 주사위 윷놀이 문제 https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 본 문제에 대한 풀이는 아래의 블로그를 참고하여 구현했다. 해당 문제를 각 경로를 나누어 풀어 어렵게 구현하다 실패한 뒤, 여러 풀이를 찾아보았다. 그중 가장 코드가 깔끔하고 이해하기 쉬웠고 하드코딩에 대한 나의 생각도 바꿔놓았다. [참고 링크 : 안산 학생의 찬란한 개발 블로그] 풀이 과정 1. 윷놀이 판의 이동 순서, 각 칸의 점수, 방향 전환 구간을 기록한다. (하드 코딩) 2. DFS를 통해 윷판의 말을 이동시키는 과정의 모든 경우를 탐색하며 최대 값을 구한 뒤, 출력한다. 세부 풀이 (1) 윷놀이 말의 진행 .. [백준 17142][C++] 연구소 3 문제 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 문제에서 주어진 제한 시간이 짧음에 주의하여 구현해야 한다. 풀이 과정 1. 주어진 입력에 주어진 바이러스의 위치 중 활성화할 바이러스를 선택할 수 있는 경우 탐색 알고리즘 구현(DFS, 조합 이용) 2. 선택된 바이러스의 위치에서 BFS를 통한 전이 함수 구현 3. 1에서 구현한 알고리즘을 통해 2를 반복하며 최소 전파시간 업데이트 4. 모든 탐색을 마친 후 최소 전파시간 출력 첫 제출에서 시간 초.. [백준 15683][C++] 감시 문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net [참고 링크 : 주성호 님의 글] 풀이 과정 1. 각 카메라의 타입별로 동작에 맞는 감시 함수가 필요하다. 이를 위해 한 방향을 감시하는 함수를 작성하여 타입에 맞게 적용한다. 각 카메라의 타입마다 가능한 경우의 수가 정해져 있다. (타입별 4, 2, 4, 4, 1 가지의 경우 가능) 2. 모든 경우를 탐색하기 위해 DFS를 이용했다. DFS를 통해 카메라를 하나씩 방문하여 모든 .. [백준 12100][C++] 2048(Easy) 문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net [참고 링크 1] [참고 링크 2 : 구데타마 님의 '꾸준함' 블로그] 풀이 과정 1. 문제의 조건에 맞도록 각 방향에 맞게 블록들을 이동하는 함수를 구현한다. 이때 '한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.'라는 조건에 주의해야 한다. 2. 1번에서 구현한 이동 함수를 5번 수행한 모든 경우를 탐색해야 한다. 3. DFS 알고.. [백준 17779][C++] 개리맨더링2 문제 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 해당 문제의 정답률에 비해 각 영역을 나누는 과정이 조금 까다로웠다. 풀이 과정 1. 각 조건을 브루트포스하게 탐색할 때 꼭짓점이 범위를 벗어나는지 체크 2. 꼭짓점을 통해 각 선거구의 영역 나누기 3. 나눠진 영역별 인구 총합 구하기 4. 최대 인구와 최소 인구의 차이 구하기 5. 정답값 업데이트 세부 풀이 (1) 브루트포스(완전 탐색)의 조건에서 각 꼭짓점들이 index의 범위를 벗어나는지 체.. 이전 1 다음
