MZ 개발자

NxN 행렬로 동전이 앞 뒤로 놓여 있고 1번 연산에 행 또는 열 전체를 뒤집을 수 있다. 이때 뒷면이 위를 향하는 동전의 개수를 최소로 하는 연산의 수를 구하는 문제이다. 이 문제를 완전 탐색을 한다면 행을 바꿀때마다 열의 상태도 같이 변한다. 따라서 행을 바꾸는 경우의수 2^20, 열을 바꾸는 경우의수 2^20 총 2^40이 된다. 루트포스 알고리즘을 이용하여 완전 탐색을 한다면 시간 초과 발생 핵심은 우리의 목표는 T가 최소가 되도록 뒤집어야 한다. 만약에 어떤 상태를 미리 알 수 있다면 그 상태에서 어떤 행 또는 열을 뒤집을지 빠르게 판단할 수 있다. 여기서 어떤 상태를 미리 알기위해 비트마스킹 개념을 도입한다. 비트마스킹이란 n

동전의 갯수가 최소가 되기 위해 5원짜리를 최대한 많이 사용하여 거슬러주면된다. 하지만 여기서 핵심은 무조건 5원짜리를 가자 많이 사용한다고 최대가 되지 않는다. 예를들어 13원일 경우 5원 2개로 거슬러주면 나머지 3원은 2원 짜리로 거슬러 줄 수 없다. 따라서 5원 1개 2원 4개 총 5개의 동전이 최소가 된다. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; int result = 99999999; for(int i = 0; i n) { cout

다음 두가지 조건을 역으로 계산 하여 B 에서 A로 만들수 있는지 없는지 찾아가면 된다. 이때 중요한점은 B가 홀수 인지 짝수 인지 판단하고, 홀수일경우 일의 자리가 1 인지 아닌지 확인하고 1이 아닐경우 A를 절때 만들 수 없다는 것을 찾아내면 된다. 만약 B가 짝수라면 2로 계속 나눠준면된다. 위의 조건을 적용하여 새로 만들어진 B`이 A보다 작아진경우 반복문을 멈추고 A와 B`이 같을경우 결과에 1을 더해준다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int a, b; cin >> a >> b; int result = 0; while(b > a) { if(b % 2 ..

두 수를 묶거나 더하여 합이 최대가 되게 하는 문제이다. 상식적으로 오름 차순으로 정렬하여 앞에서부터 두개씩 묶으면 될것 같은 생각이 들지만 문제에서 음수와 0이 존재하기 때문에 다른 방법을 선택하야한다. 경우의 수는 1. 모두 양수인 경우 2. 음수의 갯수가 짝수이면서 0이 포함 된 경우 3. 음수의 갯수가 홀수이면서 0이 포함된경우 한편 묶음의 기준은 두 수를 뽑은 후 두 수의 곱이 합보다 클경우 묶어주면 된다. (즉 a*b > a+b) 따라서 입력을 양수,음수로 나눈 후 각각을 조건에 맞게 독립적으로 계산하고 이후 두 결과를 합하면 된다. #include #include #include #include using namespace std; bool cmp(int a, int b) { return a..

N개의 단어가 주어졌을 때 알파벳의 숫자(0~9)를 결정하고 단어를 숫자로 치환하여 수의 합을 최대로 만드는 문제이다. 처음에는 자릿수를 생각하지 않고 단순히 길이가 긴 단어의 첫번째 알파벳을 큰 값으로 설정하면 될것 같다고 생각하였다. 그래서 N개의 단어를 길이 기준으로 우선순위 큐에 넣고 하나씩 뽑으면서 subString을 구한 후 다시 큐에 넣어주는 방법으로 구현하였다. 예제는 모두 통과하였지만 1%에 틀렸다고 나왔다. 😂 그리고 질문 개시판을 확인해보다가 반례를 찾을 수 있었고 틀린 이유는 각 알파벳 마다 자릿수 가중치가 존재하고 이 가중치에 따라 결과가 달라질 수 있다는 것을 알게 되었다. 예를들어 N=10 ABB BC BC BC BC BC BC BC BC BC 다음과 같이 주어졌을 경우 길이를..

문자열 파싱을 연습해볼수 있는 괜찮은 문제이다. 풀이 방법은 여러가지 존재하는데 보통 풀이는 다음과 같다. 최솟값을 만들기 위해 가능한 가장 큰 숫자를 빼야 한다. 따라서 - 를 기준으로 문자를 나누고 다음 - 를 만나기 전까지 모두 더해서 한번에 빼주면 된다. 나는 조금 고전적이지만 스택을 사용하여 숫자와 - 기호를 쌓았다. 이후 하나씩 빼면서 - 를 만나기 전까지 결과를 모두 더하고 - 를 만나면 더한 값을 -1곱하여 누적 시켜주었다. #include #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); string s; cin >> s; stack..

하나의 회의실을 여러 회의가 사용하는데 각각의 시작 시간과 끝나는 시간이 주어진다. 회의를 잘 스케쥴링 하여 회의실을 사용할때 최대 몇개의 회의가 회의실을 사용할수 있는지 구하는 문제이다. 처음에 어렵게 꼬아 생각하여 시작 시간이 빠른 순서대로 정렬하고 끝나는 시간이 빠른 순서대로 정렬하여 두개를 어떻게 지지고 볶아 비교하려고 하였다.(생각해보면 다음 회의 시작 가능 여부는 이전 회의의 종료 시간에 따라 결정된다.) 따라서 끝나는 시간을 기준으로 정렬 하여 제일 일찍 끝나는 회의를 기준으로 다음 회의 시작 시간을 결정하면 된다. 한편 문제에서 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의 시작시간과 끝나는 시간이 같을 수도 있다. 라고 주어졌기 때문에 다음과 같은 반례가 생길 수 있다..

문제를 읽어보면 OS 스케쥴링에서 SJF 알고리즘인것을 확인할 수 있다. 기존 1번 방식으로 모든 사람이 돈을 인출하는데 걸리는 wating time은 FIFO 스케쥴링에 의해 39 분을 기다려야 한다. 반면 SJF 는 가중치(P)가 가장 작은 순서 우선으로 처리한다. n=[2,5,1,4,3] p=[1,2,3,3,4] 일때 일을 끝내는데 걸리는 시간은 다음과 같다 2= 1 5= 1+2 1= 1+2+3 4= 1+2+3+3 5= 1+2+3+3+4 위의 결과를 다 더하는것이 답이므로 다음과 같은 식을 구할 수 있다. i=n result += i*p[n-i] #include #include #include using namespace std; int main() { ios_base::sync_with_stdio..