컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 문제 해결 알고리즘 플로이드 와샬 응용 문제 플로이드 와샬로 각 노드에서 노드로 가는 배열들을 모두 구한 후 그 배열에서 INF값이 아닌 값들의 개수를 따로 구해주어서 그 값보다 작거나 같은 값의 개수가 그 값과 같다면 자신의 키가 몇 번째인지 알 수있는 학생이다. 소스 코드 #include using namespace std; const int INF = 1e9; int N, M; int arr[..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 해결 알고리즘 Union find 문제 parent 배열이 무조건 그 노드의 조상노드를 가리키는 게 아니기 때문에 조상 노드 비교 해줄 때는 find_parent 함수를 써줘야한다. 소스 코드 #include using namespace std; int n, m; int parent[1000001]; int find_parent(int x){ if(x..

https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍으로 푸는 문제 next_permutation으로 일일히 순서대로 구하면 K가 최대 10억이기 때문에 시간초과를 받는다. a문자의 개수와, z문자의 개수로 이중배열을 선언해준다. dp[a문자의 개수][z문자의 개수] = dp[a문자의 개수 - 1][z문자의 개수] + dp[a문자의 개수][z문자의 개수-1] 위의 식대로 dp배열을 만들어주고 K가 a가 하나 적은 dp값보..

https://www.acmicpc.net/problem/21757 21757번: 나누기 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어 www.acmicpc.net 문제 해결 알고리즘 수열의 누적합 배열을 만들어 준 후에 수열의 총합을 구하고, 총합이 0인 경우와 아닌 경우 두 가지로 나눠서 풀어줘야한다. 0인 경우는 마지막 0빼고 나머지 0의 개수에서 3개를 뽑는 조합으로 개수를 구해주면된다. 0이 아닌 경우는 다이나믹 프로그래밍을 이용해서 풀어줄 수 있는데 총합에서 4를 나누면 공차가 나오고 그 공차대로 늘어나는 길이 4의..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 해결 알고리즘 벨만 포드 알고리즘 음의 사이클의 존재 여부를 판단하는 문제. 출발점이 어디든 음의 사이클 존재만 판단하면 되므로 한 번만 벨만 포드 알고리즘을 돌리면 된다. (굳이 모든 출발점에서 음의 사이클 존재 여부 판단할 필요 X, 시간 초과남) if(d[cur_node] != INF && d[next_node] > d[cur_node] + cost) 보통의 벨만 포드 알고..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 문제 해결 알고리즘 벨만 포드 알고리즘 INF값은 충분히 크게 잡아주어야한다. 오버 플로우가 나기 때문에 int 대신 long long 자료형을 써주어야한다. 소스 코드 #include #define ll long long using namespace std; const ll INF = 1e9; const int MAX = 6001; l..

https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 www.acmicpc.net 문제 해결 알고리즘 세그먼트 트리에 인덱스 값을 넣는데 이 때, 인덱스에 해당하는 배열 값과 항상 비교해서 작은 배열 값의 인덱스 값을 리턴해준다. 소스 코드 #include using namespace std; const int MAX = 100000; int arr[MAX+1], tree[4*MAX+1]; int ..

https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 문제 해결 알고리즘 ccw알고리즘을 이용해 푸는 문제 입력된 점들을 순서대로 이은 선분 두개의 좌표를 외적해서 값이 음수이면 -1 양수이면 1 일직선이면 0을 출력한다. 소스 코드 #include using namespace std; int main(){ int x_1, y_1, x_2, y_2, x_3, y_3; cin >> x..

https://www.acmicpc.net/problem/5569 5569번: 출근 경로 상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대 www.acmicpc.net 문제 해결 알고리즘 방향 전환이 가능한지, 방향이 아래인지 오른쪽인지 이 네가지로 나눠서 다이나믹 프로그래밍을 진행주어야한다. 소스 코드 #include using namespace std; const int mod = 100000; int arr[101][101][2][2]; // 행, 열, 방향 전환 가능 여부, 방향 아래 0 오른 1 int main(){ int w, h; cin ..

https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍을 활용해서 풀어주는 문제 배열에 0부터 20까지 두고 첫번 째 수부터 그 안에 속하는 등식이면 배열에서 그 해당하는 값의 개수를 더해주면서 동적계획을 해준다. 소스 코드 #include using namespace std; int N; long long arr[103], dp[21][103]; long long result = 0; int main()..