알고리즘 문제풀이/백준
-
[백준/BOJ] 14225번 부분수열의 합 (C++)알고리즘 문제풀이/백준 2021. 1. 5. 23:58
www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 1182번 문제에서 조금 심화된 브루트 포스(완전 탐색) 문제입니다. DFS를 이용해 만들어 낼 수 있는 부분수열의 합을 모두 구하고 이를 배열에 체크합니다. 모든 탐색이 끝난 후, 체크 배열에서 false인 첫 인덱스를 출력하고 종료합니다. 이때, 배열 범위안에 false인 인덱스가 없다면, 가장 큰 인덱스에서 +1을 한 값을 출력하면 됩니다..
-
-
[백준/BOJ] 2003번 수 들의 합 2 (C++)알고리즘 문제풀이/백준 2021. 1. 4. 13:10
www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투 포인터를 이용해 해결할 수 있는 문제입니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n, m, answer = 0; cin >> n >> m; vector v(n); for(int i = 0; i < n; i++) { ..
-
[백준/BOJ] 1644번 소수의 연속합알고리즘 문제풀이/백준 2021. 1. 4. 13:04
www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 수학 + 투 포인터 문제였습니다. 새롭게 알게된 점 연속된 값들을 이용하여 풀어나가는 문제에서 한 배열에 포인터 변수 2개를 두어 탐색하는 투 포인트 알고리즘을 쓸 수 있다. 이때 투 포인트 알고리즘의 시간복잡도는 O(N)이다. 에라토스네스의 체 알고리즘을 이용하여 소수를 모두 구해 prime 벡터에 값을 넣어 준 후, prime 벡터에 head와 tail 2개의 포인터 변수를 둬서 투 포인터 탐색을 통해 n을 만들 수 있는 경우를 모두 구하면 됩니다. #include #include using namespace std; void..
-
[백준/BOJ] 1932번 정수 삼각형 (C++)알고리즘 문제풀이/백준 2021. 1. 1. 16:06
www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net DFS + DP 유형의 문제입니다. 입력값을 2차원 배열에 넣어주고, DFS를 통해 (0, 0) 에서 시작하여 n-1번째 행의 모든 열을 방문합니다. 리프 노드에서 다시 루트 노드로 올라가면서, 누적 최대값을 갱신하게 됩니다. #include #include using namespace std; int n; int map[501][501]; int dp[501][501]; int DFS(int x, int y) { if(dp[x][y] != -1) return dp[x][y]; //..
-
[백준/BOJ] 1003번 피보나치 함수 (C++)알고리즘 문제풀이/백준 2021. 1. 1. 15:53
www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net DP 유형의 문제입니다. Top-Down 방식을 이용해서 피보나치 함수를 구현한 후, 피보나치 함수의 값, 0이 나오는 갯수, 1이 나오는 갯수 이 세가지의 규칙을 찾아내면 되는 문제였습니다. 이 세가지의 규칙은 다음과 같습니다. 피보나치 함수 0이 나오는 갯수 1이 나오는 갯수 0 1 0 1 0 1 2 1 1 3 1 2 4 3 4 n의 값이 2이상일 때 부터 0이 나오는 갯수는 F(n - 1), 1이 나오는 갯수는 F(n) 과 같다는 것을 확인할 수 있습니다. #include #include using n..
-
[백준/BOJ] 17298번 오큰수 (C++)알고리즘 문제풀이/백준 2020. 12. 31. 14:43
www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 스택 유형의 문제 프로그래머스의 주식가격과 비슷한 문제였습니다. 인덱스 번호를 스택에 넣어주면서 스택의 top을 인덱스로하는 벡터의 값과 현재 인덱스의 벡터의 값을 비교하여 오큰수를 찾아내는 것이 포인트입니다. 비교가 끝난 후, 스택에 남아있는 인덱스 번호는 만족하는 오큰수를 가지지 않으므로 따로 -1을 대입하면 됩니다. #include #include #include using namespace std; int main(v..
-
[백준/BOJ] 1167번 트리의 지름 (C++)알고리즘 문제풀이/백준 2020. 12. 30. 15:53
www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 트리 유형의 문제 (다시 풀기) 트리에서의 지름이란 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다고 합니다. 지름을 구하는 유명한 공식(?)이 있다는 것을 처음으로 알게 되었는 데, 트리에서 지름을 구하는 방법은 다음과 같습니다. 1. 트리에서 임의의 정점 v1을 잡는다. 2. 정점 v1에서 가장 먼 정점 v2를 찾는다. 3. 정점 v2에서 가장 먼 정점 v3를 찾는..