알고리즘 문제풀이
-
[백준/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..
-
[프로그래머스/Level 2] 예상 대진표 (C++)알고리즘 문제풀이/프로그래머스 2021. 1. 3. 20:50
programmers.co.kr/learn/courses/30/lessons/12985 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr #include using namespace std; int solution(int n, int a, int b) { int answer = 0; while(1) { if(a == b) return answer; a = (a + 1) / 2; b = (b + 1) / 2; answer++; } }
-
[백준/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..