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..

이 문제를 풀면서 아직 실력이 많이 부족하다는 것을 느꼈다. 처음 생각해낸 방법은 덱을 사용해서 문제마다 모든 조건을 처리해주는 정신 나간 짓을 하려고 하였다. 2번 3번 조건을 만족하기 위해 현재 내가 풀고있는 문제(now)가 있고 이 문제를 풀기 이전 풀어야할 문제(pre)를 설정하고 이상한 뻘짓을 많이 하였다... 문제를 보는 순간 어떤 알고리즘을 물어보는지 감이 오지 않아 어떻게든 내가 알고있는 알고리즘 내에서 최대한 풀어보려고 시도하였다. 또한 문제가 잘 이해되지 않았다. 처음에 답이 두개인가?? 생각도 하고 질문 답변을 확인한 결과 조금 이해가 되었다. 어느덧 3시간 고민 후... 각 N 마다 먼저 풀어야하는 문제를 우선순위 큐에 넣어 DFS 탐색까지 도달였다. 하지만 결과는 DFS로는 풀수 ..

문제를 보고 몇시간 정도 풀이를 생각해보다가 도저히 떠오르지 않아 다른 사람 풀이를 참고하여 아이디어를 얻었다. 문제에 간선의 가중치는 100보다 크지 않는 양의 정수라고 하여 특정 노드에서 가장 깊이 들어가야 최소한 최대 길이가 될것 같다는 생각을 하였다. DFS를 생각한것이다. 하지만 DFS 한번만으로 도저히 답을 찾아낼 수 없었다. 풀이를 보니 DFS를 두번 사용 해야 한다고 하였다. 왜 DFS를 두번 사용해야 하는지 이해가 안되다가 다음과 같은 특징을 이해한 다음에 문제를 해결할 수 있었다. 하나의 정점에서 가장 멀리 있는 정점은 원의 지름 부분에 해당하는 정점이다. 즉 어느 점에서 DFS를 통해 가장 긴 점을 찾으면 그 점은 가장 지름이 긴 원의 시작 점이 된다. 이후 그 시작점에서 또 가장 긴..

N개의 수 중에서 M 개의 수가 존재하는지 여부를 0,1로 출력하는 문제이다. 총 M 개의 수가 N에 존재 하는지 알기 위해서 브루트포스 알고리즘을 사용한다면 N*M 즉 10000000000으로 시간초과가 발생한다. 때문에 이분탐색으로 logN 의 시간복잡도를 활용하여 문제를 풀어야 한다. 입력 N은 정렬되어 들어오지 않기 때문에 이분탐색을 위해 정렬이 필요하다. 처음에 STL algorithm에 있는 sort를 활용하여 정렬하였는데 제출하고 나니 시간초과가 발생하였다. 원인이 뭔지 찾아보다가 어떤 사람은 qsort를 직접 구현하면 된다고 하는데, 실제 qsort는 STL에서 제공하는 sort보다 시간이 느리다. 한참 찾아보다가 발견한 원인은 재귀함수 파라미터에 vector를 call by referen..

물의 높이가 0~100 까지 변하는 동안 각 높이마다 잠기지 않는 안전한 영역이 존재한다. 문제 해결 방법은 각 높이에서 안전한 영역의 최대 갯수를 구하는 것이다. 안전한 영역 즉 섬의 갯수를 구하기 위해서 물의 높이보다 높은 영역을 기준으로 DFS를 적용하였다. 핵심은 방문한 영역을 표시 하고 한번 방문한 영역은 DFS에서 제외시켜야 한다. #include #include #include using namespace std; int n; int map[102][102]; bool visit[102][102]; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; void dfs(int x, int y, int height) { if(visit[x][y]) { re..