it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

시간초과가 나는 이유가 궁금합니다! 공부왕 1일 전

아래와 같은 코드로 하니 하나 뺴고 시간초과가 되어서 궁금합니다.

강의랑 비슷한 코드인데 왜 제 코드는 시간초과일까요?!

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N, M;
vector<pair<int, int> > pizza;
vector<pair<int, int> > people;
int ch[13];
int res = 987654321;

int cal(int x1, int y1, int x2, int y2) {
	return abs(x1 - x2) + abs(y1 - y2);
}

void dfs(int index, int cnt) {
	if (cnt == M) {
		int min = 0;
		for (int i = 0; i < people.size(); i++) {
			int dis = 987654321;
			for (int j = 0; j <M; j++) {
				int x = cal(people[i].first, people[i].second, pizza[ch[j]].first, pizza[ch[j]].second);
				if(dis > x) dis = x;
			}
			min += dis;
		}
		if (min < res) res = min;
		return;
	}
	for (int i = index; i < pizza.size(); i++) {
		ch[cnt] = i;
		dfs(index + 1, cnt+1);
	}
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <=N; i++) {
		for (int j = 1; j <= N; j++) {
			int x;
			scanf("%d", &x);
			if (x == 1) people.push_back({ i,j });
			else if (x == 2) pizza.push_back({ i,j });
		}
	}
	dfs(0, 0);
	printf("%d\n", res);
	
	return 0;
}

41번 연속된 자연수의 합 ) 질문드립니다. tlswodnr427 3일 전

우선 소스코드는 위와 같은데요 

제가 생각한 방법은 

n이라는 수가 주어졌을때 

1부터 n/2까지 반복문을 돌리면서 ,

1+ 2+3+ ....     

   2+ 3+ 4+ ... 

        3+ 4+ 5+ ..... 

4+ 5+ ......

                 5+ 6+... .

                     6+7+....

7+8....  

이중 합이 15가 나오는경우만 count하는 방법을 생각해봤는데 

이 방법으로도 가능할것 같은데 계속 고민해가며 고쳐봐도 틀리게 나와 질문드립니다. 

#include <stdio.h>

int temp[100],cnt=0;

void Clear(int temp[],int p){
	for(int i=0; i<=p; i++){
		temp[i]=0;
	}
}

int main(void){
	int n,sum=0,p=1,i,j;
	scanf("%d",&n);
	
	for(i=1; i<n/2; i++){  
		int k=i;
		while(1){
			if(sum==n){
				cnt++;
				for(j=1; j<p; j++){
					if(j==p-1){
						printf("%d = %d\n",temp[j],n);
					}
					else{
						printf("%d + ",temp[j]);
					}
				}
				Clear(temp,p);
				p=1;
				sum=0;
			}
			else if(sum>n){
				Clear(temp,p);
				p=1;
				sum=0;
				break;
			}
			sum+=k;
			temp[p++]=k++;
		}
	}
	
	printf("%d",cnt);
}

선생님 c++ 라이브러리? 를 사용하는것에 큰 문제가 없나요? kiryanchi 3일 전

코딩 테스트나 코딩 대회에서는 시간 복잡도와 공간 복잡도까지 고려해야한다고 알고 있습니다. 이 문제를 저는 vector 라이브러리를 활용해서 (erase, pop_back, insert 등) 풀었습니다. 이 라이브러리를 활용하는 것이 코딩 테스트나 대회에서 불리하게 작용하나요?

비슷한 느낌으로 scanf, printf 말고 cin, cout 을 쓰는것도 살짝 느리다고 알고 있습니다. 이런 이유에서 선생님께서는 scanf, printf 를 사용하시는건가요?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int s, n, idx = 0, i, tmp;
	bool isValue = false;
	scanf("%d %d", &s, &n);
	vector<int> cache(s);
	for (i = 0; i < n; i++) {
		isValue = false;
		scanf("%d", &tmp);
		for (int j = 0; j < cache.size(); j++) {
			if (tmp == cache[j]) {
				isValue = true;
				idx = j;
			}
		}
		if (!isValue) {
			cache.insert(cache.begin(), tmp);
			if (cache.size() > s)
				cache.pop_back();
		}
		else {
			cache.erase(cache.begin() + idx);
			cache.insert(cache.begin(), tmp);
		}
	}
	for (unsigned i = 0; i < cache.size(); i++)
		cout << cache[i] << ' ';
	cout << endl;
	return 0;
}

BFs jfmam 5일 전

그래프 상의 최단거리의 경우 전에 BFS문제를 사용했던 걸로 알고있습니다. 다익스트라도 최단거리 관련문제인데

다익스트라는 BFS의 한종류의 알고리즘으로 보면되나요?

BFS와 다익스트라의 차이점이 있다면 궁금합니다

선생님, 질문있습니다. celestial_ 6일 전

선생님, 안녕하세요?

저는 선생님의 가르침처럼 a가 들어오면 캐시에 있는 작업번호들과 하나하나 비교해보는 것이 아닌 

함수를 하나 만들어서 현재 들어온 a에 대하여(제 코드 상에서는 income에 해당합니다) 캐시 전체를 일괄 탐색한 다음 

만일 캐시 안에 a가 있다면 그에 맞는 작업을 진행하고 없다면 맨 앞에서부터 밀어내는 방식으로 코드를 만들어봤습니다. 

이러한 방식도 그럴듯한 답이 될 수 있는가 궁금합니다.

항상 강의 감사드립니다.

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int S; // 저장용량
int N; // 작업개수

bool isincache(int* cache, int income) {
	int income_ = income;
	for (int i = 0; i < S; i++) {
		if (income_ == cache[i]) { return true; break; }
	}
	return false;
}

int main() {
	
	srand(time(NULL));

	scanf("%d", &S);
	scanf("%d", &N);

	int* cache = (int*)malloc(sizeof(int) * S);
	int* work_list = (int*)malloc(sizeof(int) * N);
	int income = 0;
	int index = 0;
	int current_cache_capacity = 0;

	for (int i = 0; i < N; i++) {
		work_list[i] = (rand() % 100) + 1;
	}
	//임의의 작업 번호를 다 집어넣음


	printf("현재 작업번호 리스트 : ");
	for (int i = 0; i < N; i++) { printf("%d ", work_list[i]); }
	printf("\n");
		
		int count1 = 0;
		//애초에 빈 상태이니까 채우도록 하겠습니다.
		while (S - current_cache_capacity >= 0) {
			cache[S - current_cache_capacity] = work_list[count1++];
			current_cache_capacity++;
		}
		
		
		//이렇게 되면 current_cache_capacity == S가 되어서, 캐시는 모두 차있는 상태


		for (int i = 0; i < N; i++) {
			income = work_list[i]; // income으로 for문이 돌때마다 초기화를 합니다. 
			//income이 work_list 안에 있는가? 없는가?를 분기로 하여 알고리즘 작성
			
			if (isincache(cache, income)) {
				int index = i;
				int before = i - 1;
				while (before >= 0) {
					cache[before + 1] = cache[before];
					before--;
				}
				cache[before + 1] = income;
			}
			else {
				for (int i = S-1; i > 0; i--) {
					cache[i] = cache[i - 1];
				}
				cache[0] = income;
			}
		
		}

		for (int i = 0; i < S; i++) {
			printf("%d ", cache[i]);
		}

}

문제푸는방법에대해서 jfmam 7일 전

안녕하세요 

75번을 풀다가 궁금한게 생겨서 질문 올립니다.

처음이문제를 봤을때 저는 vector<pair<int,int> v 를 써서

money와 when을 묶어주려고했는데 구조체를 쓰는이유가있을까요? pair를 썼을때 보다 장점이있을까요?

visual studio에서는 jfmam 7일 전

vs에서도 bits/stdc++.h를 넣으면 되나요?

vs는 없는거같은데 업그레이드를 시켜야하나요?

36번 다소 헷갈려서 질문을 드립니다. celestial_ 11일 전

for(j = i-1; j>=0; j--){ // 1

        if(a[j]>tmp) a[j+1] = a[j];

        else break;

}

a[j+1]=tmp; // 2

처음 for문이 시행될 때에 j는 i가 1이기 때문에, 

j는 0으로 초기화가 된 상태에서 for문 안에 있는 일련의 if문을 

거치고 난 뒤에 j--에 의해 j가 -1로 바뀐 상황에서,

이미 j>=0이라는 컨디션에 해당안하기에 

바로 a[0]=tmp;

가 된다고 이해하였습니다. 이게 다른건 몰라도 삽입은 할 때마다 이상하게 상기 ㅈ주석으로  표시한 2코드의 의미가 이해가 안된다기보다는 오히려 확 와닿지를 않는다고 표현하는게 더 적절하네요ㅜㅜㅜ

그렇다면 for문 대신

while(j>=0&&a[j]>tmp){

    if(a[j]>tmp){a[j+1] = a[j];}

    else break;

     j--;

}

a[j+1]=tmp;

}

라고 표현해도 괜찮을까요?

늘 감사드립니다. 

35번 궁금합니다. celestial_ 11일 전

선생님, 선생님의 코드에 비해 저의 코드에 어떠한 불필요한 과정이 있는지 알려주시면 대단히 감사하겠씁니다. 많이 까주세요. 감사합니다.

#include<iostream>
#include<vector>

using namespace std;

void swap(int* a, int* b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}


int main() {
	int N;
	int negative = 0; //입력받은 음수의 개수 
	int start = 0; //음수가 맨 앞으로 도달하면 그 다음으로 인덱스를 설정 
	int positive = 0; //양수의 시발점을 표현하기 위한 인덱스
	cin >> N;

	vector<int>index(N);
	vector<int>arr(N);
	
	for (int i = 0; i < N; i++) { index[i] = i; }
	for (int i = 0; i < N; i++) { cin >> arr[i]; if (arr[i] < 0) { negative++; } }

	

	for (int i = 0; i < N; i++) {
		if (start == negative) { break; }
		if (arr[i] < 0) { swap(&arr[start], &arr[i]); swap(&index[start], &index[i]); start++; }
	}

	for (int i = 0; i < N; i++) {
		if (arr[i] < 0) { positive++; }
	}
	for (int i = positive; i < N; i++) {
		int min = index[i];
		for (int j = i + 1; j < N; j++) {
			if (min > index[j]) {
				swap(&index[i], &index[j]); swap(&arr[i], &arr[j]);
			}
		}
	}
	
	for (int i = 0; i < N; i++) { printf("%d ", arr[i]); }

}

질문있습니다. jfmam 11일 전

좀 이상한 질문이긴한데...

check함수를 미로찾기에서는 2차원배열로 쓰고 경로탐색에서는 1차원배열로 쓰셨는데...이게 1차원으로 해야하는지 2차원으로 해야하는지 어떻게 알수 있는방법이있을까요?

인접리스트 jfmam 12일 전

안녕하세요
인접배열로도 문제를 푸는데 지장없다고 하셨는데

그러면 인접리스트를 썻을때의 장점이나 문제를 풀때 써야하는경우가 생길까요?

46번 질문입니다. Dong Kyun Kang 13일 전

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int p[2001];
int main(){
	freopen("input.txt","rt",stdin);
 	int n,k,pos=0,bp=0,tot=0;
// 	vector<int> p(n+1);
 	cin>>n;
 	for(int i=1;i<=n;i++) {
 		cin>>p[i];	
 		tot+=p[i];
	}
	if(k>=tot) {
		printf("-1\n");
		return 0;
	}
 	cin>>k;
 	while(1){
 		pos++;
 		if(pos>n) pos=1;
 		if(p[pos]==0) continue;
		p[pos]--;
 		bp++;
 		if(bp==k) break;
	 }
	 while(1){
	 	pos++;
	 	if(pos>n) pos=1;
	 	if(p[pos]!=0) break;
	 }
	 cout<< pos;
	return 0;
}

위 코드에서 주석해놓은 벡터배열로 선언해서 실행하면 타임리밋이고 int 배열로 선언하면 잘 되는데 왜 그런건가요? 처음에 벡터로 풀었는데 당황스러웠어요

마지막에서 시간 초과 나오는 이유는 뭘까요? 공부왕 13일 전

시간초과가 나오지 않게 하려고 시간복잡도 N^2를 피했는데 마지막에서 시간초과가 나요 왜그럴까요 if에서 배열++하는 작업이 시간이 많이 드는 건가요?

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;
int check[30001];

int main() {
	int N, M;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		check[x]++;
	}
	cin >> M;
	vector<int> arr;
	for (int i = 0; i < M; i++) {
		int x;
		cin >> x;
		if (check[x] > 0) {
			arr.push_back(x);
			check[x]--;
		}
	}
	sort(arr.begin(), arr.end());
	for (int i = 0; i < arr.size(); i++) {
		cout << arr[i] << " ";
	}
	return 0;
}

39번 두 배열 합치기에서 celestial_ 14일 전

선생님, 안녕하세요? 저는 선생님께서 코드를 ㅈ작성하시기 이전에 제가 코드를 먼저 ㅈ작성하는 편인데요

강의 중에 포인터? 포인트??? 를 언급하시길래 아 포인터를 사용해야하나 보다 싶어서 포인터를 써서 ㅈ작성을 해봤습니다. 

그랬더니 코드는 다음과 같은데요

원래 index1 index2 index3 이거 없이 그냥 

a, b, c(c는 a,b각각을 합친 배열)에 대한 포인터를 각각

p1 p2, p3로 잡고 

조건에 따라 p1++ p2++ 이렇게 포인터를 증가시키면서 코드를 작성하려 하였더니 합쳐진 p3에서 엑세스 위반이 일어난다고 합니다. 그래서 index1 index2 index3를 각각 0으로 놓고 궁여지책으로라도 코드를 작성해봤는데요

코드는 잘 동작하는 것으로 보입니다.

1) 왜 p1++ p2++할 때에는 액세스 위반이 생기는 건가요?

2) 제 코드에 불필요한 부분이나 부ㅈ족한 부분이 있다면, 가르침을 주시면 감사하겠습니다. 

#include<stdio.h>
#include<stdlib.h>

int main() {
	int* p1, * p2, * p3;
	int* a, * b, * c;
	int N, M;
	int index1 = 0, index2 = 0, index3 = 0;
	scanf("%d", &N);

	a = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++) { scanf("%d", &a[i]); }
	
	scanf("%d", &M);
	b = (int*)malloc(sizeof(int) * M);
	
	for (int i = 0; i < M; i++) { scanf("%d", &b[i]); }

	c = (int*)malloc(sizeof(int) * (N + M));

	p1 = a, p2 = b, p3 = c;

	for (int i = 0; i < N; i++) { printf("%d ", *(p1+i)); }
	for (int i = 0; i < M; i++) { printf("%d ", *(p2+i)); }


	//if (*p1 < *p2) { *c = *p1; }
	while (index1 < N && index2 < M) {
		if (*(p1 + index1) < *(p2 + index2)) { *(p3 + index3) = *(p1 + index1); index3++; index1++; }
		if (*(p1 + index1) > * (p2 + index2)) { *(p3 + index3) = *(p2 + index2); index3++; index2++; }
		if(*(p1+index1)==*(p2+index2)){*(p3+index3)=*(p2+index2); index3++; index2++; }
	}

	//a배열이 남은 경우
	printf("%d %d %d \n", index1, index2, index3);


	if (index1 == N) {
		for (int i = index2; i < M; i++) {
			*(p3 + index3) = *(p2 + i);
			index3++;
		}
	}


	for (int i = 0; i < index3; i++) { printf("%d", c[i]); }




}

dev c++ 컴파일 에러 BMO 15일 전

문제를 풀고 f9,f10을 누르면  현재 코드를 작성한대로 나오는게 아니라 이전 코드로 컴파일한 내용이 나옵니다. 컴파일러 설정에서 -static-libgcc를 추가해봐도 해결되지 않습니다.. 이런 경우는 어떻게 해결해야되는지 질문 남깁니다.