윤깡패 블로그

문제 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 풀이 1. 에라토스테네스의 체를 이용해 최대 범위에 해당하는 모든 소수를 구한다. 2. 주어진 소수들의 N제곱값이 입력된 A와 B 사이에 존재하는지 판별해 유효한 소수의 개수를 센다. 에라토스테네스의 체 알고리즘 에라토스테네스의 체 알고리즘 에라토스테네스의 체 알고리즘 소수를 구하는 대표적인 판별법 * 소수(Prime Number) : 1과 자기 자신 외에 약수가 존재하지 않는 수 ⇒ 1은 소수가 아니..

문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 동적 계획법(Dynamic Programming) 알고리즘 동적 계획법(Dynamic Programming) 알고리즘 동적 계획법(Dynamic Programming) 알고리즘 한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법 동적 계획법 알고리즘 핵심 이론 1. 큰 soobin0821.tistory.com 코..

문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 이진 탐색을 적용하면 데이터 정렬까지 고려하여 O(nlogn) 시간 복잡도로 해결할 수 있다. 이진 탐색(Binary Search) 알고리즘 이진 탐색(Binary Search) 알고리즘 이진 탐색(Binary Search) 알고리즘 탐색 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색하는 알고리즘 이진 탐색 핵심 이론 특징 - 배열 내부..

이진 탐색(Binary Search) 알고리즘 탐색 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색하는 알고리즘 이진 탐색 핵심 이론 특징 - 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. - 시간 복잡도 : O(logN) 과정 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 1. 현재 데이터셋의 중앙값을 선택한다. 2. 중앙값 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다. 4. 과정 1 ~ 3번을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다. 구현 int start = 0; int end = A.size() - 1; while(start ta..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 완전 탐색을 진행하며 몇 번째 깊이에서 원하는 값을 찾을 수 있는지를 구하는 것과 동일 ⇒ BFS를 사용해 최초로 도달했을 때 깊이를 출력 BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문에 DFS보다 BFS가 적합하다. DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘 탐색 알고리즘 주어진 데이터에서 자신이 원하..

문제 https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 풀이 일반적인 반복문으로 구하면 시간 초과가 발생하므로 에라토스테네스의 체 알고리즘 방식을 제곱수 판별 로직에 적용해 문제를 해결한다. min과 max 사이의 수들 안에서 1,000,000의 데이터만 확인한다. 에라토스테네스의 체 알고리즘 에라토스테네스의 체 알고리즘 에라토스테네스의 체 알고리즘 소수를 구하는 대표적인 판별법 * 소수(Prime Number) : 1과 자기 자..

문제 https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 풀이 투 포인터 알고리즘 투 포인터 알고리즘 투 포인터 알고리즘 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. 투 포인터 알고리즘을 활용하여 2개의 그룹을 병합하는 과정 - 시간 복잡도 : O(N + M) (N, M : 정렬된 배열 A와 B의 데이터 soobin0821.tistory.com 코드 #include #include using namespace std;..

문제 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 에라토스테네스의 체 알고리즘 에라토스테네스의 체 알고리즘 에라토스테네스의 체 알고리즘 소수를 구하는 대표적인 판별법 * 소수(Prime Number) : 1과 자기 자신 외에 약수가 존재하지 않는 수 ⇒ 1은 소수가 아니다. 시간 복잡도 : O(Nlog(logN)) + 매우 빠르게 동 soobin0821.tistory.com 코드 #include #include using namespace std; int main()..

에라토스테네스의 체 알고리즘 소수를 구하는 대표적인 판별법 * 소수(Prime Number) : 1과 자기 자신 외에 약수가 존재하지 않는 수 ⇒ 1은 소수가 아니다. 시간 복잡도 : O(Nlog(logN)) + 매우 빠르게 동작한다. - 메모리가 많이 필요하다. ⇒ 알고리즘을 수행할 때 N의 크기만큼 배열을 할당해야 하기 때문 에라토스테네스의 체 핵심 이론 1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다. [ 예시 ] 1부터 30까지의 모든 자연수를 나열한다. 2. 2부터 시작하고, 남은 수 중에서 지워진 상태가 아닌 가장 작은 수를 찾는다. 3. 남은 수 중에서 현재 선택된 숫자의 배수를 배열에서 끝까지 탐색하면서 제거한다. 이때 처음으로 선택된 숫자는 제거하지 않는다. [ 예시 ] 2를 ..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 가장 긴 경로 찾기 ⇒ 임의의 노드에서 가장 긴 경로로 연결된 노드는 트리의 지름에 해당하는 두 노드 중 하나다. 그래프를 인접 리스트로 저장한다. 임의의 노드에서 탐색을 수행하고 탐색할 때 각 노드의 거리를 배열에 저장한다. 2번에서 얻은 배열에서 임의의 노드와 가장 먼 노드를 찾는다. 3번에서 찾은 노드부터 탐색을 다시 수행하고 탐색할 때 각 노드의 거리를 배열에 저..