알고리즘 문제풀이/백준
-
[백준/BOJ] 16198번 에너지 모으기 (C++)알고리즘 문제풀이/백준 2021. 2. 4. 21:53
www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n, sum = 0; vector v(11, 0); cin >> n; for(int i = 0; i > v[i]; } while(v.size() > 2) { int maxx..
-
[백준/BOJ] 2748번 피보나치 수 2 (C++)알고리즘 문제풀이/백준 2021. 2. 3. 16:27
www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net dp 유형의 문제입니다. dp를 이용해서 피보나치 수를 구현하면 쉽게 풀 수 있는 문제인데, 이때 n의 최대값이 90이므로 int 범위가 벗어나므로, long long 타입을 사용하는 것을 주의합니다. #include #include using namespace std; typedef long long ll; ll dp[91]; ll F(int n) { if(dp[n] != ..
-
[백준/BOJ] 16197번 두 동전 (C++)알고리즘 문제풀이/백준 2021. 2. 3. 16:08
www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 13460번과 비슷한 BFS 유형의 문제입니다. 두 동전이 동시에 움직이는 것을 처리해주기 위해서, visit배열을 4차원 배열을 두어 각 동전의 움직임을 기록합니다. 그리고 큐에도 두 동전의 좌표와 버튼을 누른 수를 넣으며 BFS 탐색을 해주기 위해서 구조체를 선언하였습니다. 그 다음 문제풀이를 위한 순서는 다음과 같습니다. 1. 위, 오른쪽, 아래, 왼쪽 방향마다 동전이 하나만 떨어지는 경우 체크 2. 동..
-
[백준/BOJ] 15658번 연산자 끼워넣기 (2) (C++)알고리즘 문제풀이/백준 2021. 2. 1. 16:46
www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net 14888번과 동일한 문제인데, 연산자의 개수가 n-1개가 아닌 최대 4n개까지 입력받을 수 있는 것이 달랐습니다. 처음에 next_permutation을 이용하여 접근했는데, 시간복잡도가 44C11 * 11 이라 시간초과가 발생하였습니다. 그래서 14888번의 동일한 풀이에 연산을 할 때 마다 연산자를 기록할 수 있게 벡터를 하나 생성하여 해결했습니다. #includ..
-
[백준/BOJ] 17140번 이차원 배열과 연산 (C++)알고리즘 문제풀이/백준 2021. 1. 30. 22:39
www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 어려운 구현 문제였습니다. (다시 풀기) 1. 현재 행에서 각 열의 숫자가 나오는 빈도 수를 구합니다. (cnt 배열 이용) 2. cnt 배열의 값이 0 이상인 경우, 숫자와 그 빈도 수를 저장합니다. (pair형 2차원 벡터 v 이용) 3. 초기 입력 배열 A를 0으로 초기화하고, v 벡터를 빈도 수, 크기 순으로 오름차순 정렬합니다. (이를 쉽게 하기 위해서 v에 값을 넣을 때 빈도 수를 fir..
-
[백준/BOJ] 17144번 미세먼지 안녕! (C++)알고리즘 문제풀이/백준 2021. 1. 28. 00:57
www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 삼성 역량 테스트 기출 문제 : 시뮬레이션(구현) (다시 풀기) 먼지의 확산을 구현하고, 공기청정기의 작동을 구현하면 되는 문제입니다. 이때 주의해야 할 점은 먼지의 확산을 구현하는 과정에서, 2차원 배열이 하나만 존재하면 올바른 확산을 구현할 수 없기 때문에 두 개의 배열이 필요합니다. 공기청정기의 작동은 다음과 같은 접근으로 구현했습니다. 위 공기청정기, 아래 공기청정기를 기준으로 가까운쪽에서 시작하여, ..
-
[백준/BOJ] 16235번 나무 재테크 (C++)알고리즘 문제풀이/백준 2021. 1. 26. 17:37
www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 삼성 역량 테스트 기출 문제 : 시뮬레이션(구현) (다시 풀기) 입력 조건 N : map의 가로, 세로 크기 M : 구매하여 심은 나무의 수 K : 지난 시간 x, y : 나무의 위치, z : 나무의 나이 제한 사항 1 ≤ N ≤ 10 1 ≤ M ≤ N2 1 ≤ K ≤ 1,000 1 ≤ A[r][c] ≤ 100 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10 입력으로 주어지는 나무의 위치는 모두 ..
-
[백준/BOJ] 16234번 인구 이동 (C++)알고리즘 문제풀이/백준 2021. 1. 25. 21:44
www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 삼성 역량 테스트 기출 문제 : BFS + 시뮬레이션(구현) (다시 풀기) 문제의 포인트는 BFS 탐색시에 방문하는 좌표를 저장할 큐를 하나 더 선언하는 것입니다. 그래서 BFS를 탐색과 좌표 저장을 동시에 진행하면서, 좌표를 저장한 큐를 하나씩 꺼내어 이에 평균을 넣어주면 쉽게 해결할 수 있습니다. #include #include #include #include using namespace st..