알고리즘
-
백준 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
-
백준 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. 알고리즘키워드 - 정수론, 구현, 수학 * 접근..
-
백준 1065번: 한수정수론(Number theory) 2018. 7. 3. 09:57
https://www.acmicpc.net/problem/1065 1. 문제어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 2. 알고리즘키워드 - 수학, 구현 문제를 접근 하기 위해서는 먼저 등차 수열이 무엇인지를 이해 해야 한다. 수학에서, 등차수열(等差數列, 문화어: 같은차수렬, 영어: arithmetic sequence)은 연속하는 두 항의 차이가 모두 일정한 수열을 뜻한다. 예를 들어 1, 3, 5, 7, 9, ...은 등차수열이다. 이때 두 항의 차이는 이 수열의 모든 연속하는 두 항들에 대해서 공통..
-
백준 1003번: 피보나치 함수피보나치(Fibonacci) 2018. 7. 3. 09:53
https://www.acmicpc.net/problem/1003 1. 문제다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. 1234567891011int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}Colored by Color Scriptercs fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibonacci(1) (두 번째 호출..
-
백준 13241번: 최소공배수정수론(Number theory) 2018. 7. 3. 09:49
https://www.acmicpc.net/problem/13241 1. 문제두 수의 최소 공배수를 찾는 문제 2. 알고리즘키워드 - 유클리드 호제법, GCD 3. 코드 123456789101112131415161718192021#include #include #include #include #include // greater 사용 위해 필요 #include #include #include using namespace std;long long int gcd(long long int a,long long int b) { return (a % b == 0 ? b : gcd(b,a%b));}int main() { long long int a, b; cin >> a >> b; long long int sol =..
-
백준 2606번: 바이러스깊이우선탐색(DFS) 2018. 7. 1. 20:46
https://www.acmicpc.net/problem/2606 1. 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 2. 알고리즘 키워드 - DFS, BFS 참고 - 다음엔 BFS 로 풀어 봐야겠다. 3. 코드 #inc..
-
백준 2573번: 빙산깊이우선탐색(DFS) 2018. 7. 1. 20:06
https://www.acmicpc.net/problem/2573 DFS 응용 문제 탐색 되는 영역이 2 개가 되는 횟수를 출력 키워드 - DFS 참고 - 일년이 지나면 주변 경계값에 0 이 있는 개수 만큼 줄어 든다. DFS 코드 작성한 거보다 next 코드 작성 한게 더 힘들 었다. Source #include #include #include #include #include #include #include #include #include #include #include #include #include // vs 에서는 안필요 한대 BOJ 에서 필요함 using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define CENDL "\n" #..