윤깡패 블로그

이진 탐색(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번에서 찾은 노드부터 탐색을 다시 수행하고 탐색할 때 각 노드의 거리를 배열에 저..

정렬(Sort) 알고리즘 데이터를 정해진 기준에 따라 순서대로 나열해 의미 있는 구조로 재설정하는 것 버블(Bubble) 정렬 알고리즘 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 특징 시간 복잡도 : O(n²) + 간단하게 구현할 수 있다. - 다른 정렬 알고리즘보다 속도가 느린 편이다. 과정 비교 연산이 필요한 루프 범위를 설정한다. 인접한 데이터 값을 비교한다. swap 조건에 부합하면 swap 연산을 수행한다. 루프 범위가 끝날 때까지 2~3번을 반복한다. 정렬된 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다. 비교 대상이 없을 때까지 1~5번을 반복한다. * 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데..

투 포인터 알고리즘 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. 투 포인터 알고리즘을 활용하여 2개의 그룹을 병합하는 과정 - 시간 복잡도 : O(N + M) (N, M : 정렬된 배열 A와 B의 데이터 개수) 정렬된 배열 A와 B를 입력받는다. 배열 A에서 처리되지 않은 원소 중 가장 작은 원소를 data 1 index가 가리키도록 한다. 배열 B에서 처리되지 않은 원소 중 가장 작은 원소를 data 2 index가 가리키도록 한다. A[data 1 index]와 B[data 2 index] 중에서 더 작은 원소를 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다. 배열 A와 B에서 더 이상 처리할 원소가 없을 때까지 2~4번의 과정을 반복한다. * , 을 참고하였습니다.

문제 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 가능한 한 큰 수들끼리 묶어야 결괏값이 커진다. 음수끼리 곱하면 양수로 변한다. 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘 + 구현하기 쉽다. + 시간 복잡도가 우수하다. - 항상 최적의 해를 보장하지 못한다. 그리디 알고리즘 soobin0821.tistory.com 코..