컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/1060 1060번: 좋은 수 정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다. A와 B는 양의 정수이고, A < B를 만족한다. A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다. 정수 www.acmicpc.net 문제 해결 알고리즘 S에 속한 숫자들을 먼저 우선순위 큐에 넣고 (이 때, 들어오는 S의 원소들은 정렬되지 않았기 때문에 정렬을 꼭 해주어야한다.) 좋은 구간의 개수는 0이긴 하지만 1로 해주어야 나중에 2 1 3 3 같은 반례로부터 자유롭다. 우선순위 큐에 있는 수들은 작은 수가 먼저 나오게 정렬해준다. 그리고 큐에서 나온 수의 1 큰 수와 1 작은 수의 좋은 구간 개수를..

https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 문제 해결 알고리즘 우선순위 큐를 이용하는 문제. 메모리 관리가 빡세다. 그냥 곱한 값들을 전부 우선순위 큐에 집어넣는 방식으로 하면 메모리 초과를 피할 수 없다. 우선순위 큐의 크기가 N보다 크고 최댓값보다 그 값이 크다면 건너뛰고 중복은 받지 않는 식으로 메모리 관리를 해주어야한다. 시행착오가 참 많았던 문제 소스 코드 #include #define ll long l..

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 해결 알고리즘 세그먼트 트리 문제인데, 곱이기 때문에 구간 합 구하기 문제와는 좀 다르게 update 함수를 아래부터 위로 다시 곱하는 방식으로 구해주어야한다. 왜냐면 0이 있기 때문 오버플로우가 날 수 있으므로 long long 자료형을 써야한다. 소스 코드 #include #define ll long long using nam..

https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 알고리즘 dfs를 이용해 자리를 바꿔보고 K번 만큼 바꾼 후 가장 큰 값을 출력한다. 이 때 같은 수가 나올 수 있으므로 visited배열을 이용해 중복되는 값은 배제한다. 소스 코드 #include using namespace std; bool check[1000001][11]; string str; int m; int result = 0; void dfs(int K){ if(str[0] == '0') return; if(K == 0){ result = ..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 문제 해결 알고리즘 최댓값을 찾는 세그먼트 트리와 최솟값을 찾는 세그먼트 트리를 각각 만들어 범위내 최댓값 최솟값을 출력해준다. 소스 코드 #include using namespace std; const int MAX = 100001; int arr[MAX], minTree[4*MAX], maxTree[4*MAX]; int maxinit(int start, i..

https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 문제 해결 알고리즘 최솟값이 있는 인덱스를 계속 업데이트해주는 세그먼트 트리를 이용해 풀 수 있는 문제 소스 코드 #include #define ll long long int using namespace std; #define MAX 100001 int N; ll arr[MAX], tree[4*MAX]; int minIndex(int x, i..

https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제 해결 알고리즘 최소 스패닝 트리를 구하는 문제이다. 크루스칼 알고리즘으로 문제를 풀었다. https://kimmessi.tistory.com/74?category=871925 [알고리즘] 그리디 알고리즘 - 최소비용신장트리, 스케줄 짜기 탐욕 알고리즘이란? 작은 사례로 나누지 않고 탐욕스러운 선택을 sequence로 계속하면 답에 가까워진다. 선택과정(selection procedure) : 집합에 추..

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 문제 해결 알고리즘 위상 정렬문제인데 인접리스트를 이중배열로 구현해야한다는 점과 "?"과 "impossible"을 구분해주어야하는 점이 어려웠다. (두 팀의 순서를 바꿀 때 좀 복잡하기 때문에 이중배열이 더 편했다.) q에 원소가 2개 이상이면 "?"를 출력해주고 q에 원소가 없고 방문하지 않은 노드가 있다면 "impossible"을 출력해준다. 2개 이상도 아니고 모든 노드를 방문했다면 ..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 해결 알고리즘 다익스트라 + 경로 출력해줘야하는 문제. 다익스트라 알고리즘에서 더 값이 적은 경로가 나왔을 때, 해당 위치가 어떤 위치에서 왔는지 기록하는 배열을 만들어서 추적했다. 아래의 링크에 다익스트라 알고리즘에 대한 설명되어있다. https://kimmessi.tistory.com/185?category=871925 [알고리즘] 다익스트라 - 선형 탐색..

https://codeforces.com/problemset/problem/1700/A Problem - 1700A - Codeforces codeforces.com 문제 해결 알고리즘 $n \times m$ 배열이 위의 내용처럼 $a_{ij} = (i-1)m + j$이라면, 최소 경로는 맨위의 행과 맨 오른쪽 열의 합을 더해준 값과 같다. 그러므로 각각의 값을 구한 뒤 겹치는 $a_{1m}$값을 빼주면 최소 경로 값이 나온다. 소스 코드 #include #define ll long long int using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; ll n, m, result = 0; w..