전체 글
-
백준 2902번: KMP는 왜 KMP일까?문자열(String) 2018. 7. 3. 10:22
https://www.acmicpc.net/problem/2902 1. 문제대문자 출력 하는 문제 2. 알고리즘키워드 - 구현, 문자열O(n) 3. 코드 12345678910111213141516171819202122#include #include // min#include #include #include using namespace std; int main() { string word; cin >> word; const int size = word.size(); for (int i = 0; i = 'A' && ch
-
백준 2675번: 문자열 반복문자열(String) 2018. 7. 3. 10:19
https://www.acmicpc.net/problem/2675 1. 문제문자열의 길이 만큼 하나의 단어를 출력 하는 문제. 2. 알고리즘키워드 - 구현 처음 알고리즘을 시작 할때는 부르트포스 문제로 생각 했는데 지금 와서 보니 단순 구현 문제다. 3. 코드 12345678910111213141516171819202122232425262728#include #include // min#include #include #include using namespace std; int main() { int n; cin >> n; for (int i = 0; i > cand >> word; int size = word.size(); for (int j = 0; j
-
백준 1546번: 평균구현(Implementation) 2018. 7. 3. 10:17
https://www.acmicpc.net/problem/1546 1. 문제입력 받은 수에서 평균을 구하는 문제 2. 알고리즘키워드 - 구현, 수학 3. 코드 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #include // greater 사용 위해 필요 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); // scanf 안쓸 경우 쓰세요. Cin 사용시 int N; cin >> N; vector arr(N); int maxValue = 0; for (int i=0; i> ..
-
백준 2748번: 피보나치 수2피보나치(Fibonacci) 2018. 7. 3. 10:15
https://www.acmicpc.net/problem/2748 메모리 제약 사항이 128 MB 임으로 메모제이션이나 다이나믹프로그래밍으로 접근 해야 한다. 키워드 - 정수론, 피보나치, 다이나믹 프로그래밍 1 2 3 5 8 13 21 이전 요소의 값을 계속 더해 준다 Source #include #include #include #include #include // greater 사용 위해 필요 #include using namespace std; // 자료형 범위 명심 long long dp[91] = {0, }; int main() { ios::sync_with_stdio(false); cin.tie(0); // scanf 안쓸 경우 쓰세요. Cin 사용시 dp[1] = 1; dp[2] = 1; f..
-
백준 2839번: 설탕 배탈구현(Implementation) 2018. 7. 3. 10:11
https://www.acmicpc.net/problem/2839 1. 문제상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 2. 알고리즘키워드 - 정수론, 구현, 수학 * 접근..
-
백준 4344번: 평균은 넘겠지구현(Implementation) 2018. 7. 3. 10:09
https://www.acmicpc.net/problem/4344 1. 문제대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. 2. 알고리즘키워드 - 구현참고 - 자리수 출력에 유의 할 것 3. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include // greater 사용 위해 필요 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); // scanf 안쓸 경우 쓰세요. Cin 사용시 in..
-
백준 1912번: 연속합다이나믹프로그래밍(DP) 2018. 7. 3. 10:07
https://www.acmicpc.net/problem/1912 1. 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 2. 알고리즘키워드 - 다이나믹프로그래밍, 브루트 포스 * 접근초기 문제를 풀때 부르트포스로 해결 했었는데. 7달 뒤 보니 채점 기준이 달라져서 시간 초과 되었다. 입력 받는 수열 에서이전 값과의 합이 더크 다면 현재 dp 에 dp[i - 1] + dp[i] 저장 이전 값과의 합이 작다면 현..
-
백준 1850번: 최대공약수정수론(Number theory) 2018. 7. 3. 10:03
https://www.acmicpc.net/problem/1850 1. 문제모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이 때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. 2. 알고리즘키워드 - 정수론, 유클리드 호제법문제 이해를 잘 해야 한다. 공약수만큼 1을 출력 하는 문제다. 3. 코드 1234567891011121314151617181920212223#include #include // min#include #include #include using namespace std; typedef unsigned lon..