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

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

(13개의 수강평)

358명의 수강생
77,000원
지식공유자 · 김태원
110회 수업· 총 21시간 42분수업
평생 무제한 시청
수료증 발급 강의
수강 난이도 '초급'
jfmam 프로필

해싱에대해서 jfmam 4시간 전

해싱이란 방법으르 사용하는게 가장좋다고 설명이나왔는데

해싱이 단순히 배열을만들어서 비교하는 방법인가요?

해싱의 정의에 대해 궁금합니다

0
tlswodnr427 프로필

46번 먹방문제) 소스코드좀 봐주세요. tlswodnr427 1일 전

int a[100001];

int main(void)
{
	int n,k,i;
	scanf("%d",&n);
	for(i=1; i<=n; i++)
	{
		scanf("%d",&a[i]);
	}
	scanf("%d",&k);
 	
 	i=1;
 	int time=0;
 	while(1)
	{
		if(a[i]!=-1)
		{
			a[i]=a[i]-1;
			if(a[i]==0)
			{
				a[i]=-1;
			}
			time++;
		}	
		if(time==k)
		{
			i++;
			break;	
		}
		i++;
		if(i==n+1)
		{
			i=1;
		}
	}	
	
	while(1)
	{
		if(i==n+1)
		{
			i=1;
		}
		if(a[i]!=-1)
		{
			printf("%d",i);
			break;
		}	
		i++;	
	}
}

위처럼 했는데 채점해보니 나머지는 괜찮은데 2번이 시간초과가 나와서 80점이 나옵니다..  어디가 잘못된걸까요? 

2번 입력을 보니 3 1 2 3 6 이라, 시간초과가 나올리가 없는데 시간초과가 나오네요. 

1
tlswodnr427 프로필

44번 질문드립니다. tlswodnr427 1일 전

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며,

-> 이렇게 되어있는데 y축을 고려하지 않아도 되는건가요?

교수님께서는 1번째 사진처럼 그려서 풀이를 하셧는데 위에 문제데로 그려보면 2번째 사진처럼 되어서 y축도 고려해야 하는게 아닌가 싶어 질문드립니다. 

1
jfmam 프로필

string 타입 jfmam 1일 전

안녕하세요

데이터 타입중 string보다 char배열을 많이 쓰시는데 혹시 속도 측면에서 char이 더빨라서 쓰시는건가요??아니면 코딩스타일 상 더편해서 사용하시는건가요?

1
CHANGJUN KIM 프로필

안녕하세요. 선생님 CHANGJUN KIM 1일 전

안녕하세요. 선생님! 명절 연휴 잘 보내셨나요?

다름이 아니라.. 제가 작성한 코드가 -1이 발생하는 경우에 time_limit이 발생하는데.. 원인을 못 찾겠어서 이렇게 찾아왔습니다..ㅎㅎ

알고리즘 상 선생님과 다른 부분은 거의 없습니다.

dis배열에 거리를 판단하는게 아니라 그냥 map 배열에 거리를 늘려가면서 거리자체가 체크역할도 하는 것입니다. map에 덧씌워서 하기 때문에 초기거리값은 1부터 시작해야 했고 마지막 거리를 출력할 땐 -1을 해서 출력하도록 하였습니다.

그리고 -1을 출력하는 경우는 모두 다 훑어서 0이 나오면 -1을 출력하는 방식이 아니라 처음 map배열을 입력받을 때, 0의 개수를 파악해놓은 다음 0을 처리할때마다 감소시켜서 이값이 하나라도 남아있으면 0보다 크므로 0이 아닐때 -1을 출력하도록 하였습니다..

이렇게 그냥 부수적인 처리방식만 다를뿐.. 어디서 dfs를 타임리밋 뜨게 하는지 도통 모르겠습니다.. ㅠ 

//[쟁점] 매 토마토마다 새로운 배열로 초기화해야 하나? 주객전도x
//BFS에서 time_limit이 발생하는 이유는 ?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;
int map[1005][1005];	//거리를 한꺼번에 표시. 0은 익지 않은 토마토인 동시에 방문하지 않은 토마토
queue<pair<int, int > > q;
int maxval = -2147000000;
int dis;
int dr[4] = { 1, 0, -1, 0 };
int dc[4] = { 0, 1, 0, -1 };
int untom;
int main() {
	freopen("data.txt", "rt", stdin);
	int n, m;
	cin >> m >> n;
	for (int i = 0; i < n; i++) {	//map 입력 및 토마토 위치 파악
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1)
				q.push(make_pair(i, j));
			else if (map[i][j] == 0)
				untom++;
		}
	}
	pair<int, int> fr;
	while (!q.empty()) {
		fr = q.front();
		q.pop();
		dis = map[fr.first][fr.second];
		if (maxval < dis)
			maxval = dis;
		for (int i = 0; i < 4; i++) {
			int rr = fr.first + dr[i];
			int cc = fr.second + dc[i];
			if (rr < 0 || rr >= n || cc < 0 || cc >= m)
				continue;
			if (map[rr][cc] == 0) {
				untom--;
				map[rr][cc] = map[fr.first][fr.second] + 1;
				q.push(make_pair(rr, cc));
			}
		}
	}
	if (untom == 0)
		cout << maxval - 1 << endl;
	else
		cout << -1 << endl;
}

2
김태형 프로필

안녕하세요 51번 질문입니다! 김태형 3일 전

비쥬얼스튜디오에서 51번 700x700 배열을 선언하면 입력하기 전에 종료되는데 어떻게 하면 되나요??

2
blizzarduser 프로필

선생님이 짜주신 코드 실행시 이런 화면이 나옵니다. blizzarduser 4일 전

terminate called after throwing an instance of 'std::bad_alloc' what()…

콘솔창에 이렇게 나오고 실행이 되질않아요..

1
blizzarduser 프로필

이건 무슨차이인가요? blizzarduser 4일 전

배열크기를 300001로 하는거랑 30001로 하는거랑

success 갯수가 다른데 무슨차이인가요?

300001로하면 4번까진 성공나오고 5번은 타임리밋인데

30001로 배열크기로하면 2번부터 타임리밋이 나옵니다..

#pragma warning(disable:4996)
#include <stdio.h>
#include <string.h>
#include <math.h>
#include<time.h>
#include<iostream>
#define endl '\n';

using namespace std;


int a[300001];
int b[300001];
int r[300001];

int main() {
   int n1,n2,k=0,j=0,max=0;
   
   scanf("%d",&n1);
   for(int i=1;i<=n1;i++)
      scanf("%d",&a[i]);
      
   scanf("%d",&n2);
   for(int i=1;i<=n2;i++)
      scanf("%d",&b[i]);
      
   for(int i=1;i<=n1;i++) {
      
      k=a[i];
      
      if(k>max)
      max=k;
      
      r[k]++;
   }
   
   for(int i=1;i<=n2;i++) {
      j=b[i];
      if(j>max)
      max=j;
      r[j]++;
   }
   
   for(int i=1;i<=max;i++) {   
      if(r[i]==2)
      printf("%d ",i);
   }
   

}

1
자바스크립터 프로필

직접 조합을 구해서 문제를 풀어서 얻는 이점이 무엇인가요? 자바스크립터 6일 전

피자 배달 거리를 직접 조합을 구하지않고 푸는 방식으로 구현하였는데 시간복잡도에서 유의미한 차이가 있나요..?

똑같은 복잡도 아닌가요?

1
SEED 프로필

안녕하세요. 강사님 SEED 7일 전

안녕하세요 강사님.

강의를 수강 중인 학생입니다. 제가 강의를 들으면서 풀은 문제의 코드를 문제는 올리지않고 코드만 github에 올려놓으려고 하는데 강사님이 제공해주신 풀이 를 참조한 코드도 존재해서 저작권 문제가 혹시 있을까해서 먼저 여쭈어 보고자합니다.

아 또한 질문목록을 읽던 중에 대기업 코딩테스트 준비 하시는 분에게 메일를 보내시면 풀어볼만한 백준 문제 목록을 보내주신다는 답변을 봤는데 실례가 안된다면 저도 메일을 보내봐도 괜찮을까요? 

좋은 강의 감사드리고 다음에 나올 강의도 꼭 수강하겠습니다. 감사합니다. 

1
acoustic0419 프로필

문제 오류 acoustic0419 8일 전

문제에는 s 가 10 이하라고 했는데 채점폴더 input 을 보니 4번과 5번은 s 가 각각 15 과 17로 10을 넘어서 틀린 답으로 뜨네요. 

1
한정용 프로필

if문을 통해서 2중 for문으로 봉우리 찾는 것보다 한정용 15일 전

if문을 통해서 2중 for문으로 봉우리 찾는 것보다

dx, dy 를 통해 3중 for문으로 봉우리를 찾는게 더 효율적인가요? 어떤 접근이 더 효율적인기 궁금합니다.

1
헤이호 프로필

12. 숫자의 총 개수. 소스 코드 헤이호 16일 전

안녕하세요 강사님. 제가 12번 문제를 스스로 풀었는데 채점을 해보니 3~5에서 wrong_answer 가 떴습니다.

 잘못된 부분이 무엇인지 계속 훑어보았는데 문제점이 무엇인지 잘 모르겠습니다.

제 소스코드가 .. 아주 지저분하지만 한번 봐주 실 수 있으실까요? 감사합니다.

#include <stdio.h>
//12번, 숫자의 총 개수 (어엄청 큰 수를 구할때는 어케 하냐.)

int main(){
//	freopen("input.txt","rt",stdin);
	int n,cnt=1,i,j,res=0;
	scanf("%d",&n);
	for(i=0,j=9;((i*10)+9)<n;j=i*10){	
		res=res+(j*cnt);
		i=(i*10)+9;//9,99,999,9999~~~~
		cnt++;
	}
	res= res+(cnt*(n-i));
	printf("%d",res);
	return 0;

}

1
헤이호 프로필

10번 )자릿수의 합. sum>=max 일때 헤이호 17일 전

안녕하세요.

다른 분이 질문했는지 찾아봤는데 딱히 보이지 않아 질문드립니다.

10번. '자릿수의 합 '문제의 코드에서 

20번째 줄 if(sum>max) 부분을 if(sum>=max) 로 바꾸니

채점 결과 , 

case 1,2,5 번에서 Wrong_Answer로 뜨더라구요.

sum>=max 로 하면 안되는 이유가 있나요?

2
CHANGJUN KIM 프로필

안녕하세요. 선생님 CHANGJUN KIM 20일 전

강의 너무 잘 듣고 있습니다. 선생님 덕분에 그동안 산재되어있던 지식을 잘 정리해서 큰 도움이 되었습니다.

2주 안에 이 강의를 완료하게 되고, 이후에는 어떻게 학습하는 것이 좋은 방법일지 여쭤보고 싶습니다.

목표는 대기업 코딩테스트입니다.

1
지식공유자 되기
많은 사람들에게 배움의 기회를 주고,
경제적 보상을 받아보세요.
지식공유참여
기업 교육을 위한 인프런
“인프런 비즈니스” 를 통해 모든 팀원이 인프런의 강의들을
자유롭게 학습하는 환경을 제공하세요.
인프런 비즈니스