알고리즘/BOJ(C++)
-
[BOJ] 4963 :: 섬의 개수알고리즘/BOJ(C++) 2018. 6. 20. 12:26
https://www.acmicpc.net/problem/4963 0은 바다 1은 섬일때 총 섬의 개수를 구하는 문제입니다. 1로 연결된 모든 지점을 구해 그것을 한개의 섬으로 간주하고 총 섬의 개수를 구하면 됩니다. 대각선도 연결된 것으로 간주합니다. 즉 한 지점에 대해 자기자신을 주위로 8개 모두 탐색을 해야하는 것 입니다. 1인 지점이 존재하면 그 지점부터 탐색을 시작하고, 섬의 개수를 증가시켜줍니다.자신 주위의 8개를 모두 탐색하며 1이 있다면 연결된 섬이라는 의미 이므로 0으로 변경시켜주고, 그와 연결된 섬도 탐색하기 위해 queue에 넣어 그 지점도 후에 다시 탐색될 수 있도록 합니다. bfs방식을 이용해서 풀이 했습니다.#include #include using namespace std;in..
-
[BOJ] 1676 :: 팩토리얼 0의 개수알고리즘/BOJ(C++) 2018. 6. 19. 23:30
https://www.acmicpc.net/problem/1676 n!이 몇개의 0으로 이루어져있는지를 구하는 문제입니다. 10은 2와 5의 곱으로 이루어지는데 상식적으로..? 2의 개수보다 5의 개수가 훨씬 많으므로 소인수 분해 한 결과 5가 몇개인지 탐색해주면 됩니다. 5의 배수의 개수 + 25의 배수의 개수 + 125의 배수의 개수 ...이렇게 해서 총 몇개의 5로 이루어져 있는지 구하면 그 결과가 정답입니다. #include using namespace std;int main(){int n;cin >> n;int cnt = 0;for (int i = 5; i
-
[BOJ] 11653 :: 소인수분해알고리즘/BOJ(C++) 2018. 6. 19. 23:21
https://www.acmicpc.net/problem/11653 정수 n을 입력받아 그 소인수를 모두 구해 출력해주는 문제 입니다. n의루트값 전까지 나눌 수 있는 한 모두 나눠서 출력해 주면 됩니다!n이 소수인 경우 나눌 수 있는 값이 없으므로 예외처리 해서 출력해 줍니다! #include using namespace std;int main(){int n;cin >> n;for (int i = 2; i*i 1)printf("%d\n", n);}
-
[BOJ] 6588 :: 골드바흐의 추측알고리즘/BOJ(C++) 2018. 6. 19. 23:16
https://www.acmicpc.net/problem/6588 아아아ㅓ이ㅓㅏㅣㄹ아ㅣ 진짜 왜 자꾸 시간초과 뜨나했더니 푸는 방법은 다 맞았었는데 endl이 아니라 '\n'을 썼어야 했다...여러분 잊지 마세요ㅠ 소수 저장 방법을 vector에서 int형 배열로 바꾸고 탐색 방법도 바꾸고 별의 별 짓을 다했는데..허무하군 푸는 방법은1. 바로 전 글에서 썼던 에라토스테네스이 체를 이용해 max값인 10000000 까지 모든 소수를 구해 int형 배열에 저장해 줍니다.22. 찾은 소수의 개수 까지 탐색하며 만약 n - 소수 또한 소수라면 두 소수의 합으로 표현할 수 있는 경우이므로 그 때 출력을 해주고 탈출3. 만약 (그럴일이 없지만) 두 소수의 합으로 출력할 수 없다면 flag 변수로 확인해서 gold..
-
[BOJ] 1929 :: 소수 구하기 (에라토스테네스의 체 구현)알고리즘/BOJ(C++) 2018. 6. 19. 22:59
https://www.acmicpc.net/problem/1929 a와 b사이의 모든 소수를 구해서 출력하는 문제입니다.너무 뻘짓을 많이 해서 이것때매 정답률 엄청 낮아짐 ㅠㅠ속상하다 소수를 구하는데 우리가 일반적으로 생각하는 그 평범한 포문을 쓰면 시간초과가 납니다(1부터 자기 자신 전까지의 수로 나눠지는지 아닌지 판단하는 과정) 가장 효율적인 소수를 구하는 방법인 '에라토스테네스의 체'를 사용해야 합니다. 이 방법은 큰 배열을 잡아놓고 2부터 n까지 자신의 배수를 지워나가는 방법입니다. 이미 지워진 부분이라면 검사할 필요가 없고 지워지지 않았다면 자기 자신의 배수를 지워주면 됩니다. 주의해야 할 점1. i*i가 n보다 작을 때 까지만 확인해야 합니다. 소수의 특성상 구하고자 하는 수의 루트값보다 작은..
-
[BOJ] 11576 :: Base Conversion알고리즘/BOJ(C++) 2018. 6. 19. 22:32
https://www.acmicpc.net/problem/11576 a진수의 수와 b진수의 수가 입력이 들어오면 a진수의 수를 b진수의 수로 바꾸어서 출력해주는 문제입니다. 항상 진법변환문제가 그렇듯, 0인경우만 처리를 잘 해주면 됩니다. 다른 마땅한 방법이 생각나지 않아서 a진수를 decimal값으로 변환한 후 다시 그 값을 b진수로 변환해 주었습니다. 좀..어렵게 푼것같기도 하네요 #include #include #include using namespace std;int main(){int a, b;cin >> a >> b;int len;cin >> len;int decimal = 0;bool start = true;for (int i = len - 1; i >= 0; i--){int temp;cin..
-
[BOJ] 1373 :: 2진수 8진수알고리즘/BOJ(C++) 2018. 6. 19. 21:42
https://www.acmicpc.net/problem/1373 2진수를 8진수로 바꾸는 간단한 문제입니다.2진수를 3개씩 끊어서 10진수로 바꿔서 출력해주면 됩니다. 앞의 3개만 예외처리 해서 총 길이가 3의배수가 아닐경우 처리해주면 됩니다. #include #include #include #include using namespace std;int main(){string initial;cin >> initial;int decimal = 0;int len = initial.length();int left = len % 3;if (left == 1){cout
-
[BOJ] 2225 :: 합분해알고리즘/BOJ(C++) 2018. 6. 16. 21:09
https://www.acmicpc.net/problem/2225 다이나믹 프로그래밍으로 해결했습니다. 아무리 생각해도 1차원 dp로는 해결되지 않는데 아직 2차원 dp에 약한지 점화식 세우는데 꽤 애를 먹었네요 ㅠ 우선 dp[202][202]정도 잡아줍니다이 때 dp[k][n]의 정의는 k번 더해서 n을 만들 수 있는 경우의 수 입니다. dp[i][n] 은 dp[i-1]행에서 0부터 n까지 값을 더해서 만들 수 있습니다.i-1번 더해서 만들 수 있는 경우의 수에 0부터 n까지 어떤 수던 한개 더하면 n을 만들 수 있으니까요! 5 by 5의 예를 들어 보겠습니다. 0 1 2 3 4 51 1 1 1 1 1 12 1 2 3 4 5 63 1 3 6 10 15 214 1 4 10 20 35 565 1 5 15 ..