Algorithm115 [백준][C++] 13397번: 구간 나누기 2 <178> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 맨 처음 든 생각은 구간을 어떻게 나누지? 였다. 또한 brute force 계열의 문제라고 생각했다. 하나하나 구간을 나눠서 찾아야 한다 생각했다. 하지만 N이 5천이나 되기 때문에 시간안에 불가능할것 같았다. 최대 5천명을, 3구간으로만 나누라.. Algorithm/백준 2022. 1. 25. [알고리즘] 비트마스크 조합, 부분수열 예전부터 비트마스크 활용하는거 정리 한번 해야지... 해야지 하다 안해서... 이번에 정리해본다. 먼저 부분수열부터 문제를 통하여 알아봅시다. 1. 비트마스크를 활용하여 부분 수열 구하기 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 위 백준 문제를 통하여 설명해보겠습니다. 문제의 예시처럼 5개의 원소가 있다고 해봅시다. -7 -3 -2 5 8 각 원소 하나마다 (포함 or 미포함) 둘중 하나.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] next_permutation : 다음 순열 next_permutation (다음 순열 구하기) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 ▶ 우선 순열의 특징을 먼저 살펴봅시다! A라는 집합의 원소가 [1, 2, 3, 4] 라고 해보자. A의 순열은 다음과 같다. 1 2 3 4 (오름차순) : 첫 순열 1 2 4 3 1 3 2 4 1 3 4 2 ... 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 ... 4 3 2 1 (내림차순) :마지막 순열 오름차순으로 시작했던 순열이, 최종적으로 내림차순으로 배열되어 끝나게 된다. 총 N! 개의 서로 다른 순열이 있다. 1 2 로 시작하는 순열인 1 2 ? ? 의 마지막 순열의(내림차순) 다음 순열을 어떻게 구할까? 1 2 ? ? 의 마지막 순열은 1 2 4 .. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] Two Pointers Algorithm : 투포인터 알고리즘 Two Pointers Algorithm " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 투 포인터 알고리즘은 기본적으로 1차원 배열상에서 배열을 가리키는 포인터 2개를 이용하는 방법 입니다! (포인터 라고 해서 C의 그 포인터를 사용한다는 것 이 아닌, 배열의 어느 한칸을 가리키는 용도로 사용하는 것을 의미합니다) 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 대표적인 문제로 백준의 2003번이 있습니다. 이 설명을 보기전 문제를 먼.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] Sweeping Algorithm : 라인 스위핑 알고리즘 Sweeping Algorithm " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 라인 스위핑 알고리즘은 무엇일까? 사실 개념 자체는 매우 단순하다. 공간이나 직선 상에서 한쪽 시작점을 기준으로 반대편 종료지점 까지 scan하면서 지나가는데, 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단기준이 되는 기준 을 적용해 주면 정답이 구해지는 형태입니다. 이처럼 알고리즘의 구조 자체는 간단합니다. 즉, 스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 해야한다. 대표적인 문제로 백준의 선 긋기 문제가 있습니다. 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] Counting inversions Counting inversions " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 예를들어 배열A에 1, 2, 3, ... n 의 수가 무작위 순서로 들어있다고 해보자. 이 수들에서 2개의 무작위 수를 생각했을 때, 그 순서 대비 크기가 역전되어 있는 두 수의 쌍이 몇개가 되는지를 구해보자. 예를 들어 A {2, 3, 6, 4, 1, 7}이 있을때, 크기가 역전된 쌍은 (2, 1), (3, 1), (6, 4), (6, 1), (4, 1) 이 있다. 따라서 Inversion 된 쌍의 수는 5개 이다. 이런 Inversion된 쌍의 수를 어떻게 구해야 할까? 직관적으로 떠오르는 직접다 for문 돌면서 확인하는 방식은 O(n^2)이 걸릴것이 눈에 훤하다... 이럴때 Merge.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [백준][C++] 14852번: 타일 채우기 3 <177> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 맨 처음 생각했던 방식은 DP[N]을 만들기 위해 끝부분에 2*1 채우는 방식과, 2*2 즉, 다음 그림과 같은 방식이 끝이라고 생각했다. 따라서 점화식이 DP[N] = DP[N-1]*2 + DP[N-2]*3 이라 생각했다. 하지만 예외가 있었다. 길이가 3, 4, 5 ... 등 다음과 같은 추가적인 case가 존재했다. 각각 길이가 3, 4인 case 이다. 즉 DP[N] = DP[N-1]*.. Algorithm/백준 2022. 1. 21. [알고리즘] lower_bound, upper_bound : C++ ⭐ 조건 : 탐색을 진행할 array, vector는 오름차순으로 정렬되어 있어야 한다. lower_bound " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 lower_bound(3)을 진행하고 싶다. 배열 arr의 첫 시작지점 부터 탐색하면서 처음으로 3이 나오는 배열의 위치(Iterator)를 반환한다. 즉, 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위한 용도이다. 위치를 반환한다고 한 이유는 lower_bound의 반환형은 Iterator 이기 때문이다. 실제로 몇 번째 인덱스인지 알고 싶다면, 아래 코드와 같이 lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 된다. #include #incl.. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] 에라토스테네스의 체 : 소수 판별법 에라토스테네스의 체 (Sieve of Eratosthenes) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이 방식은 지정됨 범위네에서 대량의 소수를 한번에 구할때 유용하다. 예를 들어 121 이하의 소수를 모두 구해야 한다고 해보자. 어떻게 해결해야 할까? 결론부터 말하면 121의 제곱근, 즉 11 이하의 소수 n에 대하여 n의 배수들은 전부 제외시키면 된다. n의 배수라는 말 자체가 소수가 아니다. 아직 이해가 잘 안갈 수 있다. 다시 설명해 보자. 121의 제곱근인 11이하의 수 들을 생각해보자. 일단 2는 소수니 제거하지 않는다. 2를 제외한 모든 2의 배수 4, 6, 8, 10, ..., 120 에 해당되는 수들은 전부 제거하면 된다. 이들은 소수가 아니다. .. Algorithm/PS 알고리즘 정리 2022. 1. 21. [알고리즘] 트리의 지름 : Diameter of Tree 트리의 지름 이란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 트리의 지름은 두개의 말단노드간의 최장거리를 의미한다. 각각의 정점을 u, v 라고 한다면 이들간의 거리는 d(u, v) 라고 함수로 나타낼 수 있으며, 최장거리(지름)는 이러한 d(u, v) 값들중 최대인 Max d(u, v)라고 할 수 있다. 트리의 지름을 찾는 알고리즘 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 BFS(node) 를 통하여 node로 부터 가장 멀리있는 node를 구한다고 해보자. 이 방식은 greedy 방식에 해당된다. 1. 임의의 시작 정점 s로부터 가장 멀리있는 정점인 u를 BFS(s)로 구한다. (DFS도 가능) 2. 이렇게.. Algorithm/PS 알고리즘 정리 2022. 1. 20. [알고리즘] Bipartite Graph : 이분 그래프 이분 그레프 (Bipartite Graph) 란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 학교에서 공부할때 필기한 내용을 먼저 보인후, 이를 내가 설명하여 보겠다. 이분 그레프란 정점의 집합을 2개의 독립적인 집합으로 나눌 수 있으며, 나눠진 집합에서는 서로다른 집합 사이에만 간선이 존재하는 그레프를 의미한다. 즉 같은 집합 내부의 정점간에는 간선이 있으면 안된다. 이를 그림으로 표현하면 다음과 같음 그레프를 의미한다. 집합이 오른쪽(V)과 왼쪽(U) 2개의 집합으로 나뉘어 졌다. 간선들의 양끝 정점(u와 v) 또한 서로다른 집합에 포함되어있다. 정점 u는 집합 U에, 정점 v는 집합 V에 포함되어야 하는 것! 추가적으로 그림에는 없지만, 한쪽 집합에 그냥 .. Algorithm/PS 알고리즘 정리 2022. 1. 20. [알고리즘] Knapsack Problem Knapsack 알고리즘 이란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 터질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 위와 같은 문제를 해결하는대 사용되는 알고리즘을 대표적으로 Knapsack 알고리즘 이라고 부른다. 이러한 Knapsack 문제는 동적프로그래밍(DP)의 대표적인 문제로, 대부분의 알고리즘 서적에서 확인해볼수 있는 대표 유형이라 할 수 있다. 알고리즘의 분석 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 어떤 문제를 DP로 풀기 .. Algorithm/PS 알고리즘 정리 2022. 1. 20. 이전 1 ··· 6 7 8 9 10 다음
