기록공간

동적계획법(Dynamic Programming)을 사용하여 가장 긴 최장증가수열(LIS)을 구하는 문제이다. 동적계획법 : https://lipcoder.tistory.com/49 동적계획법(Dynamic Programming) 동적계획법 이란? 동적계획법(다이나믹 프로그래밍)은 큰 문제를 작은 문제로 나누어 푸는 알고리즘 방법이다. 다이나믹 프로그래밍이란 명칭은 그냥 알고리즘 창조한 사람이 단지 이름이 멋지다는 이유로 붙여진.. lipcoder.tistory.com 최장증가수열 : https://lipcoder.tistory.com/50 최장증가수열 - LIS(Longest Increasing Subsequence) LIS(최장증가수열)는 동적계획법으로 풀 수 있는 알고리즘 문제 중 하나이다. 어떤 임..

행렬의 행(N)이나 열(M)의 크기가 하나라도 3보다 작은 경우에는 원소 뒤집기 작업(XOR)이 불가능하기 때문에 A와 B가 서로 같은지만 확인하면 된다. 만약 둘 다 3보다 큰 경우 1행부터 N - 3행까지 그리고 1열부터 M - 3열까지 A와 B가 특정위치에서 서로 같은지를 검사하며 다른 경우 그 위치에서부터 XOR를 진행한다. 모두 끝난 후에 행렬 A와 B가 같은지 확인하면 끝이 난다. 코드는 다음과 같다. #include #include #include using namespace std; void XOR(char** mat, int N, int M) { for (int i = N; i < N + 3; ++i) { for (int j = M; j < M + 3; ++j) { char temp = ..

K개의 부등호가 있을때 각각 최대값, 최소값이 되기 위해서는, 최대값은 9부터 9 - k까지, 그리고 최소값은 0부터 0 + k까지 차례대로 가지고 와야한다. 그리고 가지고 온 숫자들의 수열을 이용하여 입력한 부등호가 만족할때 까지 검사하면 각각 부등호에 맞는 최대값, 최소값이 나온다. 최대값은 현재 수열의 이전 수열을, 최소값은 현재 수열의 다음 수열을 차례대로 가져오며 검사를 진행해야 한다. 코드는 다음과 같다. #include #include #include using namespace std; bool check(char* num, char* symbol, int size) { for (int i = 0; i ': if ..

그리디 알고리즘 문제이다. 끊어진 (적어도)N개의 기타줄을 사기위한 최소 비용을 구하기 위해서는 우선 브랜드 별로 오름차순으로 정렬하여 가장 싼 패키지 가격과 가장 싼 낱개 가격을 각각 구해준다. N이 6이상일 경우 패키지 가격으로 살 것인지 아니면 낱개 가격을 살것인지를 먼저 정해야 한다. 전자의 경우 N을 6과 나누어 나온 값 만큼 패키지 가격을 곱하여 최종 가격에 더해준다. 그리고 만약에 나머지 사야할 기타줄이 있는 경우, 그 갯수와 낱개의 곱이 패키지의 가격을 넘는다면 패키지 가격을 최종 가격에 더해주고 아닌경우 (낱개가격 * 사야할 기타줄 수)를 더해준다. 후자의 경우에는 그냥 (낱개가격 * 사야할 기타줄 수)를 더해주면 된다. 코드는 다음과 같다. #include #include using n..

그리디 알고리즘 문제이다. 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다. 예를 들어 A의 지원자가 B 지원자보다 서류 심사나 면접시험 중 하나라도 더 높다면 선발이 되고, 둘 다 낮다면 절대 선발되지 않는다. 알고리즘은 다음과 같다. 우선 서류 전형 순위를 오름차순으로 정렬한다. 정렬 후 가장 첫번째에 있는 사원은 조건에 무조건 만족하므로 선발한다. 선발된 사원의 면접 순위를 N에 기록하고 다른 지원자들의 면접 점수를 검사한다. 만약 지원자의 면접 순위가 N보다 작은 경우 조건에 만족하므로 선발하고 순위를 다시 N에 기록한다. 코드는 다음과 같다. #include #include using namespace std; struct ..

A가 B보다 작으므로 A를 앞에서 부터 한칸씩 옮기면서 B와 검사한다. 그리고 차이가 최소로 나는 값을 출력하면 된다. 앞이나 뒤에서 추가하는 작업을 할 필요는 없다. 왜냐하면 A에 앞이나 뒤로 B와 알맞은 값을 채워 넣는다고 가정하여, 추가한 위치의 알파벳은 항상 같기 때문이다. 코드는 다음과 같다. #include #include using namespace std; int main() { string A, B; cin >> A >> B; int min = 50; int diffSize = B.size() - A.size(); for (int i = 0; i

최소 값으로 만들기 위해서는 뺄셈 이후에 나오는 모든 더하기 연산에 괄호를 하면된다. 이 말은 즉슨, 최초로 나오는 뺄셈 이후부터 식이 끝날때까지 뺄셈 연산을 해주면 최소 값을 만들 수 있다. #include #include using namespace std; int main() { string input; cin >> input; string temp = ""; bool checkMinus = false; int result = 0; for (int i = 0; i

우선 최대 구성할 수 있는 팀 수를 구한다. 그리고 인턴쉽 프로그램에 참여하는 수를 남은 학생 수와 빼준다. 하지만 그래도 인턴쉽에 참여해야 할 수가 남아 있으면 구성한 팀에 있는 학생에서 채우면 된다. 남은 인턴쉽 참여 인원을 3으로 나누면 인턴쉽을 보내야 할 팀 수가 나오며, 3으로 나누었을때 한 팀이 또 깨지게 되므로 구한 팀 수에서 1을 더한다. 그리고 앞서 구했던 최대 구성 팀수와 빼주면 된다. #include #include using namespace std; int main() { int girl, boy; int intern; cin >> girl >> boy >> intern; int maxTeam = 0; int tGirl = girl; int tBoy = boy; while (tru..