알고리즘/백준

문제 풀이 누적 합과 이분 탐색을 사용한다. 배열 A에서 얻을 수 있는 모든 부 배열의 합을 vector A에 저장한다. 배열 B에서 얻을 수 있는 모든 부 배열의 합을 vector B에 저장한다. 이분 탐색을 위해 vector B를 오름차순으로 정렬한다. upper_bound와 lower_bound로 (T - 현재 검사하는 vector A의 원소의 값)을 가지는 vector B의 원소의 수를 구한다. upper_bound는 현재 검사하는 벡터에서 N의 값을 초과하는 값의 첫 인덱스를 반환한다. lower_bound는 현재 검사하는 벡터에서 N의 값 이상의 값의 첫 인덱스를 반환한다. 코드 #include #include using namespace std; int A[1001]; vector sum_A..

문제 풀이 에라토스테네스의 체와 두 포인터 알고리즘을 사용한다. N까지 소수를 에라토스테네스의 체로 구한다. 가장 작은 소수인 2부터 두 포인터 알고리즘을 시작한다. (start, end = 2) start가 end 초과일 때까지 진행한다. start에서 end까지 소수의 합이 N이하라면 end를 다음 소수까지 증가시킨다. 초과라면 start를 다음 소수까지 증가시킨다. 코드 #include using namespace std; const int MAX = 4'000'001; bool prime[MAX]; // 에라토스테네스의 체 // N까지의 수 중 소수는 true로 표시 void eratosthenes(int N) { memset(prime, false, sizeof(prime)); for (int ..

문제 풀이 방향 비순환 그래프와 위상 정렬을 이용한다. indegree가 0인 노드부터 큐에 넣는다. 큐가 empty될 때까지 검사하며 하나씩 pop한다. 검사되는 노드인 current노드와 연결된 노드인 next의 indegree를 1감소 시킨다. next노드의 indegree가 0이 되었다면 큐에 넣는다. next노드까지 소모되는 시간은 (current노드 까지 소모 시간 + next노드의 build 시간)의 최대값이다. 코드 #include #include #include #include using namespace std; int N, K, W; int build_time[1001]; int indegree[1001]; vector outdegree[1001]; vector priority[100..

문제 풀이 분리 집합을 이용한다. 각 점이 하나의 노드이며, 입력이 간선이다. 간선을 들어오는 순서대로 사이클이 생기는 지 검사하면서 Union연산으로 노드를 잇는다. 코드 #include #include using namespace std; typedef struct { int x; int y; }edge; int parent[500'000]; int getParent(int n) { if (parent[n] == n) { return n; } return getParent(parent[n]); } bool cycle(int x, int y) { int p1 = getParent(x); int p2 = getParent(y); return p1 == p2; } void Union(int x, int y..

문제 풀이 다이나믹 프로그래밍을 사용한다. N번 집을 칠할 때, 1번 집의 색의 영향을 받는다. 1번 집을 R로 칠한 경우, G로 칠한 경우, B로 칠한 경우 세 가지를 모두 검사해야 한다. 1번 집을 칠한 색이외의 cache에는 충분히 큰 값을 두어 2번 집을 칠할 때 선택되지 않도록 해야한다. i번 집을 j색으로 칠했을 때의 최솟값은 i번 집을 j색으로 칠한 비용과 i - 1번 집을 j 이외의 색으로 칠한 비용의 합의 최솟값이다. N번 집은 1번 집을 칠했을 때의 색으론 칠할 수 없으니 그 경우는 제외해야 한다. 코드 #include #include #include using namespace std; int house[1001][3]; int cache[1001][3]; int main() { io..

문제 풀이 다이나믹 프로그래밍 문제로 S와 E가 입력될 때마다 처음부터 검사하면 시간초과이다. S와 E가 같다면 무조건 팰린드롬이다. S와 E가 1차이라면 num[S]와 num[E]만 검사하면 된다. S와 E에서부터 시작해서 num[S]와 num[E]가 같으면서 사이의 수열이 팰린드롬이라면 그 수열은 팰린드롬이다. 여기서 S와 E의 값을 각각 1늘리고 1줄이는 방식으로 검사하면서 num[S]와 num[E]가 같지않다면 그 수열은 팰린드롬이 아니다. '\n' 을 사용해야 한다. endl을 사용할 경우 시간초과가 발생한다. 코드 #include using namespace std; bool cache[2001][2001]; int num[2001]; int main() { ios_base::sync_with..

문제 풀이 다이나믹 프로그래밍 문제로 string 2차원 배열을 사용해서 cache와 같이 추가하면 시간초과가 발생한다. cache를 갱신시키면서 cache의 경로를 따로 저장하거나, 결과값에서부터 역추적하여 정답에 접근해야 한다. 코드 경로를 저장하는 방법 #include #include #include using namespace std; int cache[1001][1001]; // 경로를 저장하는 배열 pair path[1001][1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); string a; string b; cin >> a >> b; a = '0' + a; b = '0' + b; for (int ..

문제 풀이 백트래킹을 사용한다. 행별로 입력된 숫자, 열별로 입력된 숫자, 블럭 별로 입력된 숫자에 해당하는 배열을 생성하고 관리한다. 스도쿠 칸의 0번째 부터 시작한다. 현재 검사하는 칸을 1씩 증가시켜서 검사한다. 현재 검사하는 칸의 행은 (current / 9)이며, 검사하는 칸의 열은 (current % 9)이다. 검사하는 칸이 0이라면 1부터 9까지의 숫자 중 현재 배열에 입력되지 않은 값으로 설정하고, 다음 칸으로 넘어간다. 검사하는 칸이 0이 아니라면 다음 칸으로 넘어간다. 현재 칸의 검사를 마치면 백트래킹을 실시한다. 코드 #include using namespace std; int ground[9][9]; bool num_vertical[10][9]; // 행 숫자 입력된 것 bool n..

문제 풀이 2중 for문을 사용하면 시간초과가 발생한다. 두 포인터 알고리즘을 사용한다. start에서 end 까지의 합이 S미만이라면 end를 증가한다. 수열의 길이를 늘린다. S이상이라면 start를 증가시켜서 수열의 길이를 줄인다. 코드 #include #include using namespace std; int num[100'002]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int N, S; int sum = 0; int answer = INT_MAX; cin >> N >> S; for (int i = 1; i > num[i]; } int start = 0; int end = 0; while (start

문제 풀이 최소 스패닝 트리 문제로 크루스칼 알고리즘으로 해결하였다. 최소 스패닝 트리는 총 간선의 수가 (정점의 수 - 1)로 이루어져 있다. 문제에서 마을은 2개로 분할하기 때문에 총 간선의 수가 (정점의 수 - 2)로 이루어진다. 그러므로 간선을 선택할 때, 선택한 간선의 수가 (정점의수 - 2)라면 알고리즘을 종료하면 된다. 단, 집이 전체 2개일 경우에는 연결할 필요가 없으니 바로 0을 출력하면 된다. 코드 #include #include #include using namespace std; typedef struct { int v1; int v2; int dist; }edge; int parent[100001]; bool compare(const edge e1, const edge e2) { ..