알고리즘/백준

문제https://www.acmicpc.net/problem/7562풀이너비 우선 탐색 간단한 BFS 문제로 기존 문제와 다른 점은 목적지에 도착할 때까지 걸린 count가 필요하다. bool 배열로 해당 칸의 방문 여부를 판별하는 것보다 int 배열로 해당 칸에 도착할 때까지 걸린 count를 기록한다. 방문 여부는 해당 칸의 count가 0인지를 확인하면 된다. 코드#include #include #include #include using namespace std;int T;int I;// visited 배열이 아닌 int로 count와 방문 여부를 동시 관리int moveCount[300][300];int moveX[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };int moveY[..

문제https://www.acmicpc.net/problem/9020풀이수학, 에라토스테네스의 채, 소수 판정 소수 판정에는 에라토스테네스의 채를 사용하여, 알고리즘 시작 전에 10000까지 소수를 판정해 둔다. 두 소수의 차이가 가장 적은 것을 출력해야 하므로, 시작 값(start)을 n / 2로 설정하여, 중앙에 가장 가깝도록 한다. start를 1씩 감소 시키면서, n - start가 소수라면 해당 값이 차이가 가장 적은 소수이므로 이를 출력하고 알고리즘을 중지한다. 처음에는 두 포인터로 문제를 해결하였지만, 위의 방법이 더 효율적이였다. 코드방법 1#include #include using namespace std;const int MAX = 4'000'001;bool prime[MAX];// 에..

문제https://www.acmicpc.net/problem/1065풀이수학, 브루트포스 알고리즘 입력되는 수는 1000 이하의 수이다. 100 미만의 수는 모두 한수를 이루기 때문에, 100 미만의 수가 들어온다면 N을 출력한다.0 ~ 9까지의 수는 그 자체로 등차수열이다.10 ~ 99까지의 수는 수열을 이루는 수가 2개이기 때문에 등차수열이다.100 이상의 수가 들어온다면 100부터 N까지 아래의 검사를 실시하여, 통과된 개수를 출력한다.현재 수의 각 자리수를 구한다. 연속된 자리수 사이의 차이가 일치한다면 한수이다. 코드#include using namespace std;int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.t..

문제https://www.acmicpc.net/problem/2512풀이이분 탐색 간단한 이분 탐색 문제. 상한액을 이분 탐색으로 찾으면 된다.start를 1, end를 예산요청액 중 최댓값으로 설정한다.mid를 (start + end) / 2로 설정한다.mid를 상한액으로 설정했을 때의 현재 합계를 구한다.mid보다 작은 예산 요청액은 그대로 sum에 더한다.mid보다 큰 예산 요청액은 mid만큼을 sum에 더한다.sum과 M을 비교하여 start와 end 값을 조정한다. start가 end를 넘을 때까지 진행한다.코드#include #include #include #include #include #include #include #include #include #include #include #incl..

문제 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 풀이 백트래킹, 브루트포스 알고리즘 연산자의 수는 N - 1로 어떤 연산에서 사용되지 않는 연산자를 생각할 필요가 없고, 전체 연산자를 어떤 순서로 사용할지 정하면 된다. 재귀 함수에서 현재까지 연산한 값(current)과 사용할 피연산자(operands[depth + 1]와 각 연산자의 남아 있는 수를 인자로 받는다. current와 피연산자를 남아 있는 연산으로 계산하고, 사용한 연산자를 1 줄여..

문제 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 구현, 시뮬레이션 vector(sharks)에 상어를 입력받는다. 보드 배열(board)의 각 칸에는 현재 위치한 상어의 index가 입력된다. 상어가 위치해 있지 않은 경우 -1이 기본값으로 설정된다. 다음 보드(next_board)의 상태를 나타내는 배열을 만든다. 마찬가지로 기본값은 -1로 설정된다. 다음의 작업이 C번 실행된다. 낚시왕이 위치한 열에 있는 상어 중에서 행이 0과 가장 가까운 상어를 잡는다. 남아 있는 상어의 위..

문제 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 구현, 시뮬레이션 풀이 1 현재 칸에서 왼쪽에 위치한 블록들 중 최고 높이와 오른쪽에 위치한 블록들 중 최고 높이를 구한다. 현재 칸에서는 최고 높이들 중에서 작은 값과 현재 높이의 차만큼의 물이 찬다. 풀이 2 한 행에서 물이 차는 칸을 계산한다. 현재 행에서 블록과 블록으로 막히는 칸들은 물이 차는 칸이다. 행에서 0번 열부터 시작하여 W - 1번 열까지 탐색한다. 처음 블록이 등장했다면 flag를 true로 설정한다. flag가 ..

문제 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 풀이 구현, 시뮬레이션 성별에 따라서 스위치를 바꾸는 방법이 다르다. 남자의 경우 입력되는 숫자의 배수에 해당하는 스위치를 바꾼다. // num의 배수에 해당하는 스위치는 상태를 바꾼다. for (int i = num; i > N; for (int i = 1; i > button[i]; } int K; cin >> K; while (K--) { int gender, num; cin >> gender >> num; if (gender == 1) { //..

문제 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 구현, 시뮬레이션 각 칸을 하나의 구조체로 만들었다. 구조체에는 영양분과 나무를 가지는 vector로 구성된다. 처음에는 sort 작업을 없애기 위해, 우선순위 큐로 만들었지만 오히려 시간초과가 발생하였다. struct space { int nutrient = 5; vector trees; }; 계절 별로 함수로 만들어서 해결한다. 봄, 여름에는 (i, j)위치의 칸의 나무를 오름차순으로 정렬하고, 성장 가능한 나무는 따로 vector에..

문제 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이 구현, 시뮬레이션, 너비 우선 탐색 판의 가장자리 부터 bfs를 실시하여 치즈가 있는 칸을 0으로 설정하여 치즈가 모두 녹을 때까지 진행하면 된다. 칸의 가장자리는 에는 치즈가 놓여있지 않기 때문에, (0, 0)에서 bfs를 시작해도 무방하다. 루프를 돌면서 만나는 치즈를 바로 0으로 만들면 해당 칸이 현재 루프에 영향을 미치므로 다음 루프에서의 판을 나타내는 next_board배열을 만들어서 next_board에 해당 칸을 0으로 설정한다. // 다음 칸이 ..