알고리즘
-
[BOJ] 9019 :: DSLR알고리즘/BOJ(C++) 2018. 7. 2. 22:58
https://www.acmicpc.net/problem/9019 얘도 BFS문제입니다! 앞으로 한동안은 미뤄놨던? 어려운 BFS문제들을 다 풀어서 끝내려고합니당... 이번주 scpc 2차라서 좀 다양한 못접해본 문제들 풀어야 하긴 하는데 ㅠ 몬가 이제와서 새로운 개념 공부해서 풀기 좀 늦은것 같기도하고... 암튼 잡소리 치우고 이문제도 너무 전형적인 bfs문제인데 여기서는 이제 다른 bfs문제랑 다른게 현재 탐색중인 지점이 어디서왔는지를 나타내는것(from배열 이용) 뿐만 아니라 그 지점으로 올때 사용된 방법(how)도 기록을 해주어야 한다는 점 입니다! L과 R구하는데 실수만 안하면 하핳...금방 풀수있는 문제입니다123456789101112131415161718192021222324252627282..
-
[BOJ] 1377 :: 버블 소트알고리즘/BOJ(C++) 2018. 7. 1. 15:49
https://www.acmicpc.net/problem/1377 백준 풀고 점점 풀이올리기가 귀찮아지는데...풀이올리면 나도 한번 다시 푸는 방법 복습하는 거니까 다시 열심히 올리려고한다! 우선 이 문제는 우리가 아는 평번한? 버블 소트 문제인데, 전체 크기인 N의 크기가 너무 커서 실제 버블 소트를 돌리면 TL이 뜬다. 그래서! 우리는 처음 들어왔을 때 수의 위치와 정렬 후 수의 위치를 비교해 가장 앞으로 많이 옮겨간 수가 몇칸 옮겨갔는지를 찾아주면 되는 문제이다!이때 정렬할때 algorith 헤더파일에 들어있는 sort함수를 쓰면 nlogn에 정렬이 가능하다. vector pair로 입력을 받아 first에는 수의 값 second에는 위치를 입력받으면 된다.후에 first를 기준으로 sort하고 s..
-
[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..