컴퓨터하는 kimmessi

www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 해결 알고리즘 1. N과 M 값을 입력을 받고 주어진 수들을 벡터(v)에 저장한 다음 정렬해주고 dfs()함수를 실행해준다. 2. dfs 함수에서 만약 n이 M과 같으면서, func 함수의 반환 값이 true라면, 배열(arr)에 있는 값들을 출력해준다. 같지 않다면 배열에 벡터(v)에 저장되어 있는 수들을 배열에 각각 넣고 dfs함수에 n+1 값을 파라미터로 넣어준다. (func함수는 이 배열에..

www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 알고리즘 1. N과 M 값을 입력을 받은 다음 dfs()함수를 실행해준다. 2. dfs 함수에서 만약 n이 M과 같으면서, func 함수의 반환 값이 true라면, 배열(arr)에 있는 값들을 출력해준다. 같지 않다면 배열에 숫자들을 1에서 N까지 순서대로 넣고 dfs함수에 n+1 값을 파라미터로 넣어준다. (func함수는 이 배열에 있는 원소들이 비내림차순으로 정렬되어 있는지 확인해주는 함수이다...

www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 알고리즘 이 문제는 N과 M (1), (2)과 달리 next_permutation으로 구현하기 어렵다. 그러므로 이제부터 제대로된 백 트래킹 알고리즘으로 구현을 해야한다. 1. N과 M 값을 입력을 받은 다음 dfs()함수를 실행해준다. 2. dfs 함수에서 만약 n이 M과 같다면 배열(arr)에 있는 수들을 모두 출력해주고, 같지 않다면 배열에 숫자들을 1에서 N까지 순서대로 넣고 dfs함수에 n..

www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 알고리즘 이 문제는 N과 M (1) 문제에서 이 수열이 오름차순인지 아닌지만 판별하고 출력해주면 된다. 소스 코드 #include using namespace std; int pac(int x){ int result = 1; while(x!=0){ result *= x; x--; } return result; } int main(){ int N, M; cin >> N >> M; vector v(N)..

www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 문제 해결 이 문제는 매우 간단하게 c++에 있는 라이브러리인 next_permutation 함수를 이용하면 쉽게 풀 수 있는 문제였다. 이 문제에서 중요한 건 중복된 출력이 있으면 안되므로 팩토리얼 함수를 따로 만들어서 그만큼을 건너뛰고 출력한 것을 볼 수 있다. 그리고 또 M까지의 숫자만 출력하는 것도 포인트이다. 소스 코드 #include using namespace std; int pac(in..

www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 문제 해결 알고리즘 이 문제는 플로이드 와샬 알고리즘을 이용해서 풀면 쉽게 풀리는 문제이다. 1. 배열에 최댓값(INF)보다 큰 값을 할당해준다. 2. 부모 자식 관계로 주어진 배열의 위치에 값을 모두 1로 할당해준다. 3. 플로이드 와샬 알고리즘을 이용해서 사람들의 촌수를 모두 계산하여준다. 4. 구하고자하는 관계에 해당하는 배열의 값이 INF와 같으면 -1을, 같지 않으면 그에 해당하는 배열의..

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍을 이용해서 풀면 시간초과가 난다 (O($ \mathrm{n^2}$)) 그러므로 이분탐색 (O($ \mathrm{ nlogn}$))으로 문제를 풀어야한다. lower_bound : 해당 원소보다 큰 작은 원소를 찾음. (이분탐색) 1. 벡터(v)에 주어진 원소들을 입력받는다. 2. 벡터(vt)에 가장 작은 원소 (-1)를 넣는다. 3. 만약 v[i]의 크기가 vt의 마지막 ..

www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 해결 알고리즘 1. 회의가 끝나는 시간을 기준으로 정렬을 한 후, 만약 같다면 시작하는 순서대로 정렬을 해준다. 2. 그 다음 회의가 가장 빠르게 끝나는 회의 시간(pivot)를 시작으로 다음 회의 시작 시간과 비교한다. 3. 만약 다음 회의 시작시간이 더 크다면 횟수(cnt)를 하나 더해주고 피봇을 다음 회의 시작하는 시간으로 바꿔준다. 그걸 계속 반복해준다. 4. 횟수(cnt)를 출력한다. 소스 코드 #include using namespace std; bool cmp(pair a, pair b){ if(a.second..

벡터공간 체 $F$에 대한 가군 $(V,+,\cdot)$을 벡터공간이라한다. $+:V \times V \rightarrow V$인 함수. 이 연산을 벡터 덧셈이라고 한다. $\cdot: F \times V \rightarrow V$인 함수. 이 연산을 벡터의 스칼라 배라고 한다. 위의 식들은 다음과 같은 공리를 만족시켜야한다. $1. (V,+)$는 아벨군이다. $(u,v,w \in V)$ $1)(u+v)+w = u+(v+w)$ $2)u+v = v+u$ $3)u + \vec{0} = u$인 $\vec{0}$가 $V$에 존재한다. $4)u+(-u)=\vec{0}$인 $-u$가 $V$에 존재한다. $2. (V,+,\cdot)$는 $F$의 가군이다. $(k,m \in F)$ $1) k \cdot (m \cdot..

www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 해결 알고리즘 1. 처음에 결과 문자열(result)에 주어진 문장을 넣는다. 2. 그 문장의 인덱스(idx)가 폭발 문자열(bomb)과 같고, 인덱스(idx)가 폭발 문자열의 길이보다 크거나 같다면 폭발 문자열(bomb)과 결과 문자열(result)의 일부분이 같은지 확인해준다. 3. 만약 같다면 폭발 문자열의 길이(B)만큼 인덱스(idx)에서 빼준다. 4. 인덱스(idx)의 길이가 0이면..