알고리즘 문제풀이
-
[백준/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..
-
[프로그래머스/Level 3] 풍선 터트리기 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 4. 17:48
programmers.co.kr/learn/courses/30/lessons/68646 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 예전에 문제를 해결하지 못해서 다른 풀이를 참고하여 글을 정리했는데, 다시 풀어보니 기존 방식이 이해가 안가서 해당 블로그를 참조하여 새롭게 풀이를 정리합니다. 각 자리 풍선이 최후까지 남아있는지 확인 하기 위해서 현재 위치가 i라고 했을 때, (0 ~ i - 1)의 최소값과 (i + 1 ~ 끝)의 최소값을 비교합니다. 현재 위치의 풍선보다 왼쪽과 오른쪽의 풍선이 둘다 작으면 해당 풍선은 최후까지 남아있을 수 없습니다. (인접한 풍선 중 번호가 더 작은 걸 최대 1번만 터트릴 수 있..
-
[백준/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. 동..
-
[프로그래머스/Level 3] 2 x n 타일링 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 3. 12:56
programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 백준의 11726번과 동일한 문제입니다. #include using namespace std; int dp[60001]; int solution(int n) { dp[1] = 1; dp[2] = 2; for(int i = 3; i
-
[프로그래머스/Level 2] 피보나치 수 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 1. 16:52
programmers.co.kr/learn/courses/30/lessons/12945 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.co.kr #include #include #include using namespace std; int dp[100001]; int F(int n) { if(dp[n] != -1) return dp[n]; if(n..
-
[백준/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..