월 15,400원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
C++를 사용하지 않고 문제를 해결하고싶습니다.
문제에서 sort함수를 이용하여 정렬을 해주는데 만약 C++ 함수들을 사용하지 않고 C로만 문제를 해결하려고 하는데 방법이 있을까요? #include<stdio.h> #include<math.h> #include <stdlib.h> #define MAX(x, y) x > y ? x : y int main(void) { int s,n,m,a,i,j,pos=0; scanf("%d",&n); int *arr=(int*)malloc(sizeof(int)*n); for(i=0;i<n;i++) { scanf("%d",&arr[i]); } scanf("%d",&m); int *brr=(int*)malloc(sizeof(int)*m); for(i=0;i<m;i++) { scanf("%d",&brr[i]); } int *sum=(int*)malloc(sizeof(int)*MAX(n,m)); int left=0,right=0; while(left<n && right<m) { if(arr[left]==brr[right]) { sum[pos++]=arr[left++]; right++; } else if(arr[left]<brr[right]) { left++; } else if(arr[left]>brr[right]) { right++; } } for(i=0;i<pos;i++) { printf("%d ",sum[i]); } free(arr); free(brr); free(sum); return 0; } 저는 이 부분에서 정렬을 하지못하여 막혀있습니다.
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다.
54. 올바른괄호 (STL stack 자료구조 활용) 문제를 강의 내용대로 코드를 짜서 해결을 했습니다. 그런데 소스파일을 보니 #include<bits/stdc++.h> using namespace std; int main(){ //freopen("input.txt", "rt", stdin); stack<char> s; string str; cin>>str; for(auto x : str){ if(x=='(') s.push(x); else{ if(s.empty() || s.top()!='('){ cout<<"NO"; return 0; } s.pop(); } } if(s.empty()) cout<<"YES"; else cout<<"NO"; return 0; } 코드가 이런식으로 나와있는데 여기에서 굵은 글씨 친 부분의 의미가 무엇인지 궁금합니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
10번 자릿수의 합에서 질문이 있습니다.
main 코드는 정답에 있는 그대로 작성하고 digit_sum만 제가 작성한것으로 돌렸는데 에러는 발생하지 않지만 실행이 안됩니다(print가 아예 안됩니다ㅠ) int digit_sum(int x){ int n, sum=0; for(;x>10;x/10){ n = x%10; sum += n; } sum += x%10; return sum; } 어떤것에 문제가 생긴건가요? 제가 의심되는 부분은 for문 (;;) 안에서 변화식을 x/10으로 작성한 부분이 걸립니다. 구글링으로 본 다른 코드에서는 for문에서 선언한 변수를 제어하는 부분이라고 i++과 비슷한 형태로만 작성되었더군요. 저는 단순히 for(반복문 돌리기전 초기 실행 ; 조건식 ; 1회 반복 후 실행) 으로 생각하고 작성했는데 혹시 for(;;)에서 작성할때 유의사항이 있나요? 다음은 전체 코드입니다. #include <iostream> using namespace std; int digit_sum(int); int main(){ freopen("input.txt", "rt", stdin); int n, num, i, sum, max=-2147000000, res; scanf("%d", &n); for(i=0; i<n; i++){ scanf("%d", &num); sum=digit_sum(num); if(sum>max){ max=sum; res=num; } else if(sum==max){ if(num>res) res=num; } } printf("%d\n",res); return 0; } int digit_sum(int x){ int n, sum=0; for(;x>10;x/10){ n = x%10; sum += n; } sum += x%10; return sum; }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
동적 할당 정적할당
선생님의 풀이를 보면 매우 큰 배열 일때는 동적할당을 하고 100정도의 작은 배열에서는 정적할당을 하시던데 1000정도의 애매한 크기에서는 정적으로 선언할 떄도 있고 정적으로 선언할 떄도 있네요. 그리고 어떨 때는 전역으로 선언하고 어떤떄는 지역으로 선언하시던데 혹시 그 기준이 있으신가요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 선생님 풀이 가운데 struct로 생성된 State는 생성자가 있는데 Lion은 왜 생성자가 없나요? 생성자를 만들어야하는거 아닌가요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
mid 질문있습니다
while문 안에서 lt rt를 경우에 따라 mid-1, mid+1로 재설정하시는데 그냥 둘다 mid로 재설정해도 동일한 값이 나오는데 그렇게 해도 문제가 없나요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
채점 질문
안녕하세요 선생님. 설명 잘 들었습니다. 선생님의 설명을 듣고, 구현을 하여 채점을 했는데요, 선생님의 코드와 완전히 같지는 않지만, 로직은 동일하게 작성하였습니다. 그결과 input data 1,2,4,5에 대해서는 success가 나왔는데 input data 3에 대해서는 exit code -182485 과 같은식으로 나오길래 input data 3의 값을 copy and paste 하여 직접 실행해 보았고, 그 결과는 output data 3과 일치하였습니다. 이런 경우, 단순히 실행과정에서 오류가 난것으로 생각하면 될까요? ======================================== (참고용 코드) #include <stdio.h> #include <stdlib.h> #include<algorithm> #include <math.h> int main(){ int height, width; int y , x ; int **arr; int i,j; int max = -1; int tmp; //1_1. 전체 땅의 가로 세로를 입려갇는다 (세로 먼저 입력 후 가로 입력) scanf("%d%d",&height, &width); //1_2. 주의할 점은, 가장자리 부분에 000000..0000을 추가하기 위해, 기존 height * width 사이즈 보다 //1씩 키워 height+1 x width+1의 크기로 다이나믹 테이블을 생성해야 한다 arr = (int**)calloc(height+1, sizeof(int*)); for(i=0; i<width+1; i++) arr[i] = (int*)calloc(width+1, sizeof(int)); //1_3. 이때, 가장자리 부분에는 0으로 초기화 되어있으므로(calloc() 함수에 의해) 그 0을 이용하여, // 일관된 규칙을 기반으로 다이나믹 테이블을 완성시킨다 for(i=1; i<=height; i++){ for(j=1; j<=width; j++){ scanf("%d",&tmp); arr[i][j] = arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1] + tmp; } } //1_4. mask의 size를 입력받는다 scanf("%d%d",&y, &x); //2. 다이나믹 테이블의 특성을 이용하여, 각 mask 안에 포함된 element의 합을 (일정한 규칙의 식을 통해) 구한다 int idx1, idx2; for(i=1; i<=(height+1-y); i++){ for(j=1; j<=(width+1-x); j++){ idx1 = i+y-1; idx2 = j+x-1; tmp = arr[idx1][idx2] - (arr[idx1][idx2-x] + arr[idx1-y][idx2]) + arr[idx1-y][idx2-x]; if(tmp > max) max = tmp; } } //3. 결국 max에는 최댓값이 남아있게 되고, 남게 되는 최댓값을 출력한다 printf("%d\n", max); //clean Up return 0; }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
동적 할당 구현 방식 질문 있습니다.
안녕하세요 선생님. 구현 방식에 있어 질문이 있습니다. 저의 경우는 전체 땅을 저장할 2차원 배열을 이런식으로 동적할당 하여 사용하였습니다. int **arr = (int**)malloc(height*sizeof(int*)); for(i=0; i<width; i++){ arr[i] = (int*)malloc(width*sizeof(int)); } //height : 전체 땅의 높이 , width : 전체 땅의 너비 이후 arr[i][j]와 같은 인덱스 기반 접근이 아니라, *(arr + i*width + j) 와 같은 포인터 연산으로, 별도의 함수를 정의하여 각 element에 접근하였는데요, 그결과 매번 오류가 났습니다. 제가 생각하는 오류의 원인은, 동적할당이 아니라 기본적인 2차원 배열로 선언하면 실제로는 메모리에 거대한 1차원 배열로 할당되기 때문에 위와같은 포인터 연산으로도 각 element에 접근할 수 있지만, 제가 구현한 방식과 같이 , 1차원 배열들을 각각 동적할당하여 하나의 2차원 배열을 구성한 경우, 해당 1차원 배열들이 메모리상에 인접하게 할당된다는 보장이 없기 때문에, 오류가 났다 라고 생각하였습니다. 제가 생각한 원인이 맞는지 여쭤보고 싶습니다.
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
Queue 자료구조 사용시 시간초과 문제
강사님, 안녕하세요. 토마토문제 testcase 4, 5에서 시간초과 오류가 발생하고 있습니다. 정답코드를 넣어봐도 같은 문제가 발생합니다. 다른 학생분들이 올린 질문에 답변하신 것을 찾아보니, 정답코드를 넣어도 시간초과가 발생하는 것은 컴퓨터 성능문제라고 하셨습니다. 그런데 다른 문제에서는 안그러는데 자꾸 queue를 사용하는 경우에만 이런 성능문제로 인한 시간초과가 발생하는데 이유가 뭔가요? queue가 다른 자료구조보다 사용하는데 시간이 많이 걸리나요? 감사합니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
구현 방식 질문
안녕하세요 선생님! 구현 방식에 있어 질문드릴게 있습니다. 1. 저는 c 문법만 알고, c++문법은 모르는 상태인데요, 그래서 이전 문제들도 vector가 아닌 전부 배열로 해결하였습니다. 혹시 앞으로 스택 등의 자료구조 를 사용하는 문제가 있는것 같은데, c문법만으로도 해결해도 문제 없는지 궁금합니다. 2. 또한 전역변수는 되도록 사용하지 않는것이 좋다고 알고있어, 지금까지의 모든 문제를 동적할당으로 배열을 할당하여 해결하였는데요, 실제 코딩테스트 문제를 해결할 때 동적할당을 금지하는 방식으로 조건이 주어지기도 하는지 여쭤보고 싶습니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
구현 질문
안녕하세요 선생님. 항상 강의 잘 듣고있습니다. 다름이 아니라, 제가 공부하고 있는 언어가 C와 JAVA정도 입니다. 그래서 채점을 위해 먼저 C로 구현한 후, 해결한 경우는 C로 해결한 과정과 동일하게 JAVA로도 구현해보고 있는데요, 혹시 이런 공부 방법이 비효율적인 공부 방법인지 여쭤보고 싶습니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다
#include <iostream> #include <algorithm> #include <queue> #include <stack> using namespace std; int arr[21]; vector<pair<int,int> > v[21]; int n,m; void dijstra(int k){ if(k == n){ return; } else { for(int i = 0; i < v[k].size(); i++){ int next = v[k][i].first; int nextval = v[k][i].second; if(nextval + arr[k] < arr[next]) arr[next] = nextval + arr[k]; } dijstra(k+1); } } int main() { int a,b,c; scanf("%d %d",&n,&m); for(int i = 0; i < m; i++){ scanf("%d %d %d",&a,&b,&c); v[a].push_back(make_pair(b,c)); // 양방향 가중치 그래프 } for(int i = 1; i <= n; i++){ arr[i] = 2147000000; // 최댓값으로 배열 초기화 } arr[1] = 0; dijstra(1); for(int i = 2; i <= n; i++){ if(arr[i] == 2147000000){ printf("%d : impossible",i); continue; } printf("%d : %d\n",i,arr[i]); } return 0; } - 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 제가 직접 짠 코드입니다. 실행하면 문제없이 답이 출력됩니다. 하지만 선생님의 답과 많이 다른데 생각해보니 제 코드가 시간복잡도가 높다고 생각됩니다. time complexity가 어느정도 차이나는지 궁금합니다!
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다.
#include <iostream> #include <algorithm> #include <queue> #include <stack> using namespace std; int arr[30][30]; int xx[8] = {0,1,1,1,0,-1,-1,-1}; int yy[8] = {-1,-1,0,1,1,1,0,-1}; struct LOC{ int x; int y; LOC(int a, int b){ x = a; y = b; } }; int main() { int n,cnt = 0; scanf("%d",&n); queue<LOC> q; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ scanf("%d",&arr[i][j]); // 지도 만들기 } } for(int i = 1; i <= n; i++){ for(int j = 1; j<= n; j++){ if(arr[i][j] == 1) { q.push(LOC(i,j)); arr[i][j] = 0; while(!q.empty()){ LOC tmp = q.front(); q.pop(); int x1 = tmp.x; int y1 = tmp.y; for(int k = 0; k < 8; k++){ int x2 = x1 + xx[k]; int y2 = y2 + yy[k]; if(arr[x2][y2] == 1){ q.push(LOC(x2,y2)); arr[x2][y2] = 0; } } } cnt++; } } } printf("%d",cnt); return 0; } - 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 스스로 코드를 짠 뒤에 선생님의 답과 비교를 했는데 실행하는데 문제는 없으나 계속해서 답이 옳지 못하게 나옵니다. 계속 틀린부분을 찾으려 해봐도 보이지 않아 질문드립니다. 어디서 문제가 발생한거죠?ㅠㅠ
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
정답이 나오는데 0점 나옵니다.
#include <iostream> using namespace std; int a[100]; int b[100]; int i, sum = 0; int digit_sum(int x){ a[i] = x; while(x > 0){ sum += x % 10; x = x / 10; } b[i] = sum; return sum; } int main() { //freopen("input.txt", "rt", stdin); int n; int ip, max = -1, max_i = 0; scanf("%d", &n); for(i = 0; i < n; i++){ sum = 0; scanf("%d", &ip); sum = digit_sum(ip); } for(i = 0; i < n; i++){ if(b[i] > max) max = b[i]; max_i = i; } for(i = 0; i < n; i++){ if(b[i] == max){ if(a[i] > a[max_i]) max_i = i; } } printf("%d\n", a[max_i]); } 이렇게 해서 맞는 답을 얻었고 in1, 부터in5까지 다 해봤는데 출력다 정상적으로 되는데 왜 전부 Wrong anwser인지 모르겠습니다.
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
파일 입출력이 제대로 안됩니다
이렇게 똑같이 입력을 하였으나 이상하게 저는 파일 입출력을 추가 하지 않은거랑 똑같이 작동을 합니다. 자동으로 54를 출력해주지 않고요. cin 주석은 잘못처리한건이고 저것을 풀어도 되지 않습니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문 있습니다
안녕하십니까 선생님. 저의 경우는, 선생님과 같이 논리적인 최댓값을 미리 계산하여 그 값만큼의 거리를 두면서 모든 말을 각 마굿간에 배치할 수 있다면, 그 값은 실제 최댓값이 가능하다는 논리를 기반으로 해결하였으나, 그때 논리적인 최댓값을 이분검색으로 좁혀나가지 않고, 일단 가능한 가장 큰 최댓값을 구한 후, 1씩 줄여나가는 방법으로 좁혀나갔습니다. 그런데 제가 질문드리고 싶은 부분은, 저의 경우는 일단 첫번째 마굿간의 위치는 무조건 말을 배치시킨다고 가정한 후, 2번째 이후 마굿간 부터 거리를 계산하여, 논리적인 최댓값 이상의 거리라면 그 경우만 말을 배치시켰습니다. 그렇게 구현 한 경우, 채점 폴더는 모두 통과하였지만. 그러면 항상 첫번째 마굿간 위치에는 말이 항상 배치되어야 한다는 가정이 깔리기 때문에, 2번째 이상의 마굿간에 처음으로 말이 배치 되는 경우는 생각하지 않아도 되는지 궁금하였습니다. 그런데 만약 두번째 이상의 마굿간에 처음으로 말이 배치시켰을 때 예측한 논리적인 최댓값 만큼 모든 말을 떨어뜨리면서 말을 배치시키는 것이 가능하다면, 그것은 곧 첫 번째 마굿간에 배치시켰을 떄도 가능해 진다 라고 판단되었습니다. 즉, 2번째 이상 위치에 말을 처음으로 배치시키는 것이 가능한 경우라면, 당연히 1번째 위치에 말을 처음으로 배치시키는 것이 가능하지만 // 논리상 1번째 위치에 처음으로 배치시키는 것이 가능할 때, 2번째 이상의 위치에 처음으로 배치시키는 것이 불가능 할 수 있다 라고 생각이 되었습니다. 따라서 항상 첫번째 위치에 첫번째 말을 배치시키는 방식으로 구현하여도, 놓치는 case는 없다고 판단하였는데, 이렇게 생각하는 것이 맞는지 궁금합니다. (코드 참고) #include<stdio.h> #include <stdlib.h> #include<algorithm> void insertionSort(int*arr, int n){ int i, j; int tmp; for(i=1; i<n; i++){ tmp = arr[i]; for(j=i-1; j>=0; j--){ if(arr[j] > tmp) arr[j+1] = arr[j]; else break; } arr[j+1] = tmp; } } int main(){ int N,C; int *stall, *horse; int logical_max; int i, j; //1_1. 마구간의 수 N과 , 말의 수 C를 입력 scanf("%d%d",&N, &C); //1_2. stall[N] 과 horse[C]와 distance[C-1]을 동적할당 stall = (int*)calloc(N, sizeof(int)); horse = (int*)calloc(C, sizeof(int)); //1_3. 사용자로 부터 stall[N]의 element를 입력받음 for(i=0; i<N; i++) scanf("%d",&stall[i]); //2. 일단 stall[N]에 저장된 element를 오름차순으로 정렬할 필요가 있음 insertionSort(stall, N); //3. 논리적으로 가장 인접한 두 말의 거리가 최대가 될 수 있는 논리적인 최댓값을 계산 -> (9 - 1 + 1) / (3-1) == (end - start) / (C-1) int start, end; start = stall[0]; end = stall[N-1]; logical_max = (end-start) / (C-1); //4. 논리적인 최댓값 부터 시작해서 1씩 감소시켜 가면서 실제 최댓값을 구함 // 이때의 implementation specification // stall 배열에 저장된 마굿간의 각 위치에 순차적으로 접근하면서, // 현 시점 마굿간의 위치가 그 이전 시점 마굿간의 위치와logical_max 거리 이상 차이날 때에만, 그러한 마굿간의 위치를 horse배열에 저장한다 // horse배열에 저장한다는 의미는, 해당 위치에 말을 배치신다는 의미로 해석할 수 있다 // 즉 문제의 예시처럼, stall = [1, 2, 4, 8, 9]인 경우 // 일단 1을 horse[idx++]에 위치시킨 후 // 2를 읽어와, 2-horse[idx-1] >= logical_max를 검사한다 //(즉 방금 읽어온 마굿간의 위치가, 그 바로 직전 말을 배치시킨 마굿간의 위치와 거리를 계산했을 때, 논리적인 거리의 최댓값 이상인지 검사) // 만약 조건을 만족하면, 해당 위치에 말을 배치시켜도, logical_max거리만큼 떨어져서 배치시킬 수 있다는 뜻임으로 -> horse[idx++] = tmp // 그렇지 않다면 그냥 넘어간다 -> 이때 idx값이 증가되지 않는다는 것이 point -> 후에 for문을 다 돌았을 때, // idx==C(말의 수)이면 말을 배치시킬 때 logical_max만큼 거리를 띄우면서 배치시킬 수 있다는 뜻 이므로, 그 때의 logical_max가 곧 최댓값 // idx<C 라면 logical_max만큼 거리를 띄우면서 모든 말을 배치시키는 것은 불가능 하였다가 되므로, logical_max를 1줄이고 다시 검사해봐야 함 // 따라서 해당 logical_max값만큼 띄우면서 모든 말을 배치시킬 수 있는지를 검사하는 측면에서 가장 중요한 값은 idx! 이다(배치못시키면 jump하니깐) //즉 1에 배치시킨 후 (2-1)<4 이므로 jump // (4-1) < 4 이므로 jump // 8-1 >= 4 이므로 4에 배치 -> horse[idx++] = tmp; // 9-8<4 이므로 jump //결과적으로 idx==2 < 3 이므로 -> 모든 말을 3만큼 띄우면서 배치시키는 것은 불가능 -> logical_max를 3으로 줄이고 다시 try //1에 배치시킨 후 (2-1) < 3 이므로 jump // (4-1) >=3 이므로 3대입 // 8-4 >=3 이므로 8 대입 // for문이 끝나지도 않았는데 idx==3이 되어 , 어쨌든 3만큼 띄우면서 배치시키는 것이 가능해지면, 3이 곧 가능한 최댓값으로 판명남 int distance, tmp; int idx=0; while(1){ idx = 0; for(i=0; i<N; i++){ tmp = stall[i]; if(idx==0) horse[idx++] = tmp; else{ distance = tmp - horse[idx-1]; if(distance >= logical_max) horse[idx++] = tmp; else continue; } //for문이 다 끝나기도 전에 이미 다 배치가 완료되었다면, 그냥 바로 break해도 됨 -> 가능하단 case가 하나라도 존재하면, // 그떄의 logcial_max가 곧 실제 real_max가 되므로! (그런 logical_max만큼 떨어져서 배치시키는 case가 존재하는지 여부가 관건) if(idx == C) break; } if(idx == C) break; else if(idx < C) logical_max--; } //5. 실질적인, 인접한 말의 거리가 최대가 될 떄의, 인접한 말의 거리 출력 printf("%d\n", logical_max ); free(stall); free(horse); return 0; }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
풀이 방법 질문 있습니다.
안녕하세요 선생님. 질문이 길어서 죄송합니다 ㅜㅜ. 구현 부분까지가 너무 난잡하시면, 논리부분만 답변해주셔도 정말 감사할 것 같습니다. 저는 이분검색을 이용하지 않은 채 해결하였는데요, 그냥 넘어가도 괜찮은지, 아니면 이분검색으로 해결해보고 넘어가는게 좋을지 모르겠어서 질문 남기겠습니다. (저는 1씩 증가시켜가며 마치 순차탐색처럼 최솟값을 확인하였지만, 선생님께서는 이분검색을 사용하여 건너뛰면서 최솟값을 확인하셨기 때문에, 제가 해결한 방법 보다는,선생님 께서 풀어주신 방법이 시간 복잡도가 더 좋은 것 같은데요, 일단 채점 폴더는 모두 통과했습니다.) => 사실 해결 당시 이분검색을 생각하지 못했고, 저한테 좀더 직관적인 방법으로 해결하였는데, 이렇게 해결하는것이 맞는것인지도 잘 모르겠습니다. <우선 제가 해결한 논리는 이렇습니다.> * 문제의 예시처럼 1, 2, 3, 4, 5, 6, 7, 8, 9 분짜리 노래 9개가 들어왔을 때, 이를 3개의 dvd에 분배해야 한다면, 논리적으로 dvd 1개의 용량의 최솟값은 15가 된다 * 따라서 최솟값을 15로 잡고, dvd용량을 15에서 시작하여 1씩 증가시켜 가며, 입력으로 주어진 노래들을 문제 조건에 맞게 분배하였을 때, 가장 먼저 분배가 된 용량이 곧 최솟값이다. (15, 16, 17 ... 증가시켜가며 확인해보면, 17이 나옴) <구현시 주의사항> 1. 논리적인 최솟값을 구할 때, 문제의 예시처럼 나누어 떨어지는 경우도 있지만, 그렇지 않은 경우도 고려하여, 경우에 따라 올림 연산 수행 2. 논리적인 최솟값 부터 1씩 증가시켜가며 , 실제 최솟값을 찾는 부분 구현시 주의사항 (반례의 경우) -> 저의 경우 선생님이 해결하신 과정과 유사하게 - 시간을 누적시키다가 min값과 같아지면 그 누적값을 바로 dvd에 분배하고 - 누적시키다가 min값을 초과하면, 초과하기 이전까지만 분배하고, 초과시킨 값은 , 다음 dvd에 누적시켰습니다. -> 그런데 min값을 추과하는 경우 바로 다음 dvd에 분배하는게 아니라 i--만을 수행하여 다음 iteration에서 다음 dvd에 대입하면서 동시에 새롭게 누적시킨 값이 min을 초과하는지 검사하였습니다. -> 그러면 반례의 경우에도, 마지막 dvd에 초과시킨 모든 값들이 누적되어, 올바르지 않은 최솟값을 출력하지 않을 수 있었습니다. (참고용 코드) int main(){ int N, M; int *arr, *dvd; // *arr : 입력한 노래의 시간 저장 , dvd : M개의 dvd를 의미 int i,j; //1_1. N, M입력 scanf("%d%d",&N, &M); //1_2. arr[N] 동적할당 arr = (int*)malloc(N * sizeof(int)); dvd = (int*)calloc(M , sizeof(int)); //1_3. arr의 element를 입력받음 for(i=0; i<N; i++) scanf("%d",&arr[i]); //2_1. (arr[N]의 element의 합 / M) 를 수행하여, 이론적으로 가능한 DVD하나의 최소 용량을 구함 int min, mod; int sum=0; for(i=0; i<N; i++) sum += arr[i]; mod = sum % M; // case 1. 나누어 떨어지는 경우 (후처리x) if(mod == 0) min = sum / M; // case 2. 나누어 떨어지지 않는 경우 -> 올림 수행 else min = (int)(((double)sum/(double)M)+1); //2_2. 이후 이론적으로 가능한 최솟값 부터 시작하여 1씩 증가시켜 가며, 실제 가능한 DVD 하나의 최소 용량을 구함 int cnt; int sub_sum; int idx; while(1){ cnt = 0; // 분배한 횟수를 count하기 위한 변수 sub_sum = 0; //실제 분배하기 전, 각 노래 시간의 합 idx = 0; // dvd배열에 접근하기 위한 index // dvd 배열 초기화 과정 for(i=0; i<M; i++) dvd[i] = 0; // 각 노래를, 최솟값 min값을 기준으로 dvd에 분배 // 마지막 M-1번째 dvd에 분배할 차례가 아닌 나머지의 경우 // -> 각 노래 시간을 누적시켜 가다가, // i) 누적시킨 sub_sum값이 최솟값 min과 같으면 -> 그대로 분배하고 cnt++ // ii) 누적시킨 sub_sum 값이 최솟값 min보다 크게 되면 -> 초과한 시간은 제외하고 나머지 누적값을 분배 후 cnt++ // 이때 i--도 진행하여, 초과시킨 값은 다음 dvd에 분배한다 // 마지막 M-1번째 dvd에 분배할 경우 //앞에서 M-2번째 dvd까지만 분배한 이후, 분배하지 못한 시간들을 모두 누적하여 M-1번째 dvd에 분배 for(i=0; i<N; i++){ sub_sum += arr[i]; if(cnt < M-1){ if(sub_sum == min){ dvd[idx++] = sub_sum; sub_sum = 0; cnt++; } else if(sub_sum > min){ dvd[idx++] = sub_sum - arr[i]; sub_sum = 0; cnt++; i--; } } if(i == N-1){ dvd[idx++] = sub_sum; } } // 최솟값 min에 따라 분배했을 때, 확인 과정 // : 각 dvd에 분배된 시간이 최솟값 min을 초과하였으면 -> 최솟값을 증가시켜 다시 분배해야 함. // 그렇지 않고 모든 dvd에 min값 이하의 시간으로 분배되어 있으면 -> 그때 min이 곧 실제 최솟값 for(i=0; i<M; i++){ if(dvd[i] > min) break; } if(i==M) break; else min++; } ///3. 최소 용량 출력 printf("%d\n", min); free(arr); free(dvd); return 0; }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
구현 측면 질문이 있습니다.
안녕하세요 선생님. 저의 경우에는 39번 문제의 두 배열을 합치는 매카니즘을 이용하여 해결하였습니다. 0. 사용자로 부터 두 배열을 입력 1. 입력받은 두 배열을 각각 정렬 알고리즘을 사용하여 오름차순으로 각각 정렬 2. 오름차순으로 정렬된 두 배열을 합친다 3. 이후 합쳐진 결과가 저장된 배열에서 중복된값만을 출력한다 저의 경우는 위의 논리를 기반으로 구현하였습니다.(사실상 39번 구현 코드와 큰 차이가 없습니다) 제 생각으로는 이렇게 구현하여도, 시간복잡도 측면을 생각해 본다면 선생님이 설명해 주신 투포인터 알고리즘으로 구현하든, 제 방식으로 구현하든 , 시간복잡도 측면은 동일하다고 생각되는데요, 제가 맞게 생각한건지 궁금합니다. -> 어차피 논리가 다른 부분은 위의 과정에서 두 배열을 합치냐 아니면 vs 바로 비교하냐 인데 , 두배열을 합치든 바로 비교하든 결국 두 방법에서 사용되는 loop은 어차피 배열 하나만을 scan하는 O(n)의 시간복잡도를 갖는다고 생각합니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
75번 최대 수입 스케줄과 79번 해당문제와의 차이점
안녕하세요. 해당 문제는 vector에서 pair를 활용하고, priority_queue에서는 구조체를 활용하고 sort를 사용하는 않는 반면, 75번 최대 수입 스케줄 문제는 vector에서 구조체를 활용하고, priority_queue는 int형으로 sort를 사용하였습니다. 그 차이가 해당 문제는 인접리스트로 해결하였고, 75번 최대 수입 스케줄 문제는 vector를 배열로 사용하였기 때문인가요? 감사합니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
구조체와 pair 질문입니다.
안녕하세요. pair 보다 구조체를 사용하시는 이유가 해당 문제에서 vector<Data> T로 벡터를 생성하면, sort를 통해 보다 쉽게 오름차순,내림차순으로 할 수 있다는 것을 알고있습니다. 하지만 pair를 사용하면 sort를 통해 오름차순이나 내림차순으로 원하는 대로 쉽게 바꿀수 없다는 점에서 구조체가 더 사용하기 좋아서인가요? 감사합니다.