알고리즘 풀이/백준(Boj)
-
백준(BOJ) 2193번 이친수알고리즘 풀이/백준(Boj) 2019. 7. 15. 01:28
문제 : https://www.acmicpc.net/problem/2193 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 나의풀이 : 동적계획법은 항상 완전탐색에서 시작하듯 이친수를 일단 직..
-
백준(BOJ) 1969번 DNA알고리즘 풀이/백준(Boj) 2019. 7. 15. 00:42
문제 : https://www.acmicpc.net/problem/1969 입력첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.출력첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다. 나의풀이 : 전체 문자들을 세로로 비교해가면서 가장 높은 숫자들을 선택해준후 벡터에 넣는다. 숫자는 골라졌지만 가장 높은 숫자는 아닌 혹은 사전순으로 우선 순위가 아래인 숫자들의 수를 subsum을 통해..
-
백준(BOJ) 1003번 피보나치 함수알고리즘 풀이/백준(Boj) 2019. 7. 11. 16:09
문제 : https://www.acmicpc.net/problem/1003 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다.각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.출력각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. 나의풀이: f(0)의 0과 1의 수 : 1 0f(1)의 0과 1의 수 : 0 1f(2)의 0과 1의 수 : 1 1f(3)의 0과 1의 수 : 1 2f(4)의 0과 1의 수 : 2 3f(5)의 0과 1의 수 : 3 5 f(n) 은 f(n-2) + f(n-1) 를 세로로 각각 더해주면 나온다는 것을 알 수 있다. 그림에 보듯 f(n)의 0의수는 f(n-1)의 1의 수와 똑같기에 f(n..
-
백준(BOJ) 1568번 새알고리즘 풀이/백준(Boj) 2019. 7. 10. 08:02
문제: https://www.acmicpc.net/problem/1568 입력첫째 줄에 새의 수 N이 주어진다. 이 값은 10^9보다 작거나 같다.출력첫째 줄에 정답을 출력한다. 코드 ( C++ ) #include using namespace std;int N; int main(){cin >> N;int sing = 1;int cnt = 0;while (N != 0) {if (N < sing) // 남아있는 수 보다 sing이 더 커지면 sing을 다시 1로 만든다.sing = 1;N -= sing;sing++;cnt++;}cout
-
백준(BOJ) 2579번 계단 오르기알고리즘 풀이/백준(Boj) 2019. 7. 10. 07:44
문제 : https://www.acmicpc.net/problem/2579 입력입력의 첫째 줄에 계단의 개수가 주어진다.둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.출력첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다. 코드 ( C ++ )#include #include using namespace std;int stairs[301];int cache[301];int N;void find(){cache[0] = 0;cache[1] = stairs[1];cache[2] = stairs[1] + stairs[2];for (int i ..
-
백준(BOJ) 9095번 1,2,3 더하기알고리즘 풀이/백준(Boj) 2019. 7. 9. 07:00
문제 : https://www.acmicpc.net/problem/9095 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 나의풀이 : n의 개수가 적기 때문에 완전탐색으로도 가능하나 동적 계획법 연습을 위해 동적계획법으로 풀어 보았다.4를 시작으로 -1 을 빼는 경우 -2를 빼는 경우 -3을 빼는 경우로 나뉘어서 재귀적 함수를 호출한다. 0이 만들어지면 경우의 수 1 반환, 0보다 작다면 0을 반환한다. 중복되어서 계산되는 경우는 메모이제이션을 통해 중복 방지한다. 코드 ( C ++ ) #include #include ..
-
백준(BOJ) 1463번 1로 만들기알고리즘 풀이/백준(Boj) 2019. 7. 8. 03:54
문제:https://www.acmicpc.net/problem/1463입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 나의풀이 : 동적 계획법을 통해 풀었다. 런타임 에러가 나온다면 MAX에 0이 5개나 7개는 아닌지 봐보자. 코드 ( C ++ ) #include #include #include #include using namespace std;const int MAX = 10000000;int cache[MAX + 1];const int INF = 987654321;int solve(int x){int& ret = cache[x];if (ret != -1)return ret;if (x == 1) return 0; //..
-
백준(BOJ) 1158번 조세푸스 문제알고리즘 풀이/백준(Boj) 2019. 7. 8. 02:47
문제: https://www.acmicpc.net/problem/1158 나의풀이 : 중간과정에서의 삽입과 삭제가 쉬운 연결리스트를 이용하였다. 복잡도는 O(N * K) 입력첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)출력예제와 같이 조세퍼스 순열을 출력한다. 코드 ( C ++ ) #include #include #include using namespace std;int N, K;int main(){cin >> N >> K;list people;vector result;for (int i = 1; i 0) {for (int i = 0; i < K - 1; ++i) { // 자기포함 K번만큼 돌면서 죽일 kill 포인터를 지정해준다.if (kill == ..