코딩테스트 준비 (32) 썸네일형 리스트형 [백준 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를 통해 카메라를 하나씩 방문하여 모든 .. [백준 17143][C++] 낚시왕 문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 과정 1. 상어를 저장하기 위한 방법 설정 상어 구조체를 작성 struct shark {int speed; int dir; int size} 상어의 좌표는 배열 형태로 저장한다. (한 칸에 하나의 상어만 존재하기 때문에) 2. 낚시로 상어를 잡는 함수 낚시가 성공했을 때 전역 변수 ans에 상어의 size를 더해주고 해당 칸의 상어를 제거한다. 3. 낚시가 끝난 후 .. [백준 13460][C++] 구슬 탈출 2 문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [참고 링크] 이 문제는 스스로 풀지 못하였고, 참고한 링크의 코드를 이해한 내용을 바탕으로 설명하였다. 풀이 과정 1. 문제 조건에 맞도록 기울여 이동하는 함수를 작성한다. 2. 4방향으로 각각 탐색을 진행하며, 이동을 통해 빨간 공이 구멍에 들어간 경우 현재까지 기울인 횟수를 출력하고 탐색을 종료한다. 이때 파란 공이 구멍에 들어간 경우는.. [백준 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 알고.. [백준 16235][C++] 나무 재테크 문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net [참고 질문] 풀이 과정 1. 각 계절별 문제 조건에 맞는 함수를 구현한다. 봄 : 나이가 어린 나무부터 양분 흡수를 진행하기 위해 sorting을 진행한다. 조건을 만족하지 못해 죽는 나무와 살아남은 나무 중 번식 가 능한 나무를 기록한다. 여름 : 봄에서 기록된 죽은 나무들을 양분으로 만들어준다. 가을 : 봄에서 기록된 번식 가능한 나무들을 번식을 진행한다. 범위를 벗어나.. [백준 16234][C++] 인구 이동 문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 과정 1. 연합의 개수는 2개 이상일 수 있다. 즉 각 연합별로 인구의 평균을 적용하기 위한 방법을 이용해야 한다. 2. 첫 칸을 너비 우선 탐색 방식 (BFS)으로 탐색하며 각 칸에서 진행할 수 있는 최대의 연합을 구성한다. 이때 방문되었던 칸은 visited 배열을 통해 기록한다. 방문되지 않았던 칸에서 다시 BFS를 진행한다. 3. 모든 칸에 대한 연합 정보를 구한다.. [백준 17779][C++] 개리맨더링2 문제 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 해당 문제의 정답률에 비해 각 영역을 나누는 과정이 조금 까다로웠다. 풀이 과정 1. 각 조건을 브루트포스하게 탐색할 때 꼭짓점이 범위를 벗어나는지 체크 2. 꼭짓점을 통해 각 선거구의 영역 나누기 3. 나눠진 영역별 인구 총합 구하기 4. 최대 인구와 최소 인구의 차이 구하기 5. 정답값 업데이트 세부 풀이 (1) 브루트포스(완전 탐색)의 조건에서 각 꼭짓점들이 index의 범위를 벗어나는지 체.. 이전 1 2 3 4 다음
