'백준 알고리즘' 카테고리의 글 목록 (13 Page)

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

길이가 짧은 것부터
길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

예제 입력 1

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

예제 출력 1

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

Solution

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

char temp[20000][51]={'\0', };

void merge(char **str,int start,int end,int mid,int N)
{
	int i=start, j=mid+1;

	for(int k=start;k<=end;k++)
		if(j>end)
			strcpy(temp[k],str[i++]);
		else if(i>mid)
			strcpy(temp[k],str[j++]);
		else if(strlen(str[i])<strlen(str[j]) || strlen(str[i])==strlen(str[j])&&strcmp(str[i],str[j])<0)
			strcpy(temp[k],str[i++]);
		else
			strcpy(temp[k],str[j++]);

	for(int k=start;k<=end;k++)
		strcpy(str[k],temp[k]);
}

void merge_sort(char **str,int start,int end,int N)
{
	if(start<end)
	{
		int mid=(start+end)/2;
		merge_sort(str,start,mid,N);
		merge_sort(str,mid+1,end,N);
		merge(str,start,end,mid,N);
	}
}

int main(void)
{
	int N;
	char **str=NULL;

	scanf("%d", &N);
	getchar();
	str=(char **)malloc(N*sizeof(char *));
	for(int n=0;n<N;n++)
		str[n]=(char *)calloc(51,sizeof(char));

	for(int n=0;n<N;n++)
		scanf("%s", str[n]);

	merge_sort(str,0,N-1,N);

	printf("%s\n", str[0]);
	for(int n=1;n<N;n++)
		if(strcmp(str[n],str[n-1])!=0)
			printf("%s\n", str[n]);
	for(int n=0;n<N;n++)
		free(str[n]);
	free(str);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 1264번: 모음의 개수 (0)	2021.07.12
<백준 알고리즘> 2108번: 통계학 (0)	2021.07.01
<백준 알고리즘> 1654번: 랜선 자르기 (0)	2021.06.30
<백준 알고리즘> 10814번: 나이순 정렬 (0)	2021.06.25
<백준 알고리즘> 11651번: 좌표 정렬하기 2 (0)	2021.06.25

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

예제 입력 1

4 11
802
743
457
539

예제 출력 1

200

힌트

802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.

Solution

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

int main(void)
{
	long long int K, N, *lan=NULL, count=1, min=0, max=999999999999, mid;

	scanf("%lld %lld", &K, &N);
	lan=(long long int *)malloc(K*sizeof(long long int));

	for(int k=0;k<K;k++)
		scanf("%lld", &lan[k]);

	while((min+max)/2!=mid)
	{
		long long int num=0;
		mid=(min+max)/2;

		for(int k=0;k<K;k++)
			num+=lan[k]/mid;

		if(N>num)
			max=mid;
		else
			min=mid;
	}

	printf("%lld\n", mid);
	free(lan);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 2108번: 통계학 (0)	2021.07.01
<백준 알고리즘> 1181번: 단어 정렬 (0)	2021.07.01
<백준 알고리즘> 10814번: 나이순 정렬 (0)	2021.06.25
<백준 알고리즘> 11651번: 좌표 정렬하기 2 (0)	2021.06.25
<백준 알고리즘> 11650번: 좌표 정렬하기 (0)	2021.06.25

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

예제 입력 1

3
21 Junkyu
21 Dohyun
20 Sunyoung

예제 출력 1

20 Sunyoung
21 Junkyu
21 Dohyun

Solution

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

int age_temp[100000];
char name_temp[100000][101]={'\0', };

void merge(int *age,char **name,int start,int end,int mid,int N)
{
	int i=start, j=mid+1;

	for(int k=	start;k<=end;k++)
		if(j>end)
		{
			age_temp[k]=age[i];
			strcpy(name_temp[k],name[i]);
			i++;
		}
		else if(i>mid)
		{
			age_temp[k]=age[j];
			strcpy(name_temp[k],name[j]);
			j++;
		}
		else if(age[i]>age[j])
		{
			age_temp[k]=age[j];
			strcpy(name_temp[k],name[j]);
			j++;
		}
		else
		{
			age_temp[k]=age[i];
			strcpy(name_temp[k],name[i]);
			i++;
		}

	for(int k=start;k<=end;k++)
	{
		age[k]=age_temp[k];
		strcpy(name[k],name_temp[k]);
	}
}

void mergesort(int *age,char **name,int start,int end,int N)
{
	if(start<end)
	{
		int mid=(start+end)/2;
		mergesort(age,name,start,mid,N);
		mergesort(age,name,mid+1,end,N);
		merge(age,name,start,end,mid,N);
	}
}

int main(void)
{
	int N, *age=NULL;
	char **name=NULL;

	scanf("%d", &N);
	age=(int *)malloc(N*sizeof(int));
	name=(char **)malloc(N*sizeof(char *));
	for(int n=0;n<N;n++)
		name[n]=(char *)calloc(101,sizeof(char));

	for(int n=0;n<N;n++)
		scanf("%d %s", &age[n], name[n]);

	mergesort(age,name,0,N-1,N);

	for(int n=0;n<N;n++)
		printf("%d %s\n", age[n], name[n]);
	free(age);
	for(int n=0;n<N;n++)
		free(name[n]);
	free(name);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 1181번: 단어 정렬 (0)	2021.07.01
<백준 알고리즘> 1654번: 랜선 자르기 (0)	2021.06.30
<백준 알고리즘> 11651번: 좌표 정렬하기 2 (0)	2021.06.25
<백준 알고리즘> 11650번: 좌표 정렬하기 (0)	2021.06.25
<백준 알고리즘> 11055번: 가장 큰 증가 부분 수열 (0)	2021.06.22

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

예제 입력 1

5
0 4
1 2
1 -1
2 2
3 3

예제 출력 1

1 -1
1 2
2 2
3 3
0 4

Solution

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

int xtemp[100000], ytemp[100000];
void merge(int *x,int *y,int start,int end,int mid,int N)
{
	int i=start, j=mid+1;

	for(int k=	start;k<=end;k++)
		if(j>end)
		{
			xtemp[k]=x[i];
			ytemp[k]=y[i];
			i++;
		}
		else if(i>mid)
		{
			xtemp[k]=x[j];
			ytemp[k]=y[j];
			j++;
		}
		else if(y[i]<y[j] || y[i]==y[j]&&x[i]<x[j])
		{
			xtemp[k]=x[i];
			ytemp[k]=y[i];
			i++;
		}
		else
		{
			xtemp[k]=x[j];
			ytemp[k]=y[j];
			j++;
		}

	for(int k=start;k<=end;k++)
	{
		x[k]=xtemp[k];
		y[k]=ytemp[k];
	}
}

void mergesort(int *x,int *y,int start,int end,int N)
{
	if(start<end)
	{
		int mid=(start+end)/2;
		mergesort(x,y,start,mid,N);
		mergesort(x,y,mid+1,end,N);
		merge(x,y,start,end,mid,N);
	}
}

int main(void)
{
	int N, *x=NULL, *y=NULL;

	scanf("%d", &N);
	x=(int *)malloc(N*sizeof(int));
	y=(int *)malloc(N*sizeof(int));

	for(int n=0;n<N;n++)
		scanf("%d %d", &x[n], &y[n]);

	mergesort(x,y,0,N-1,N);

	for(int n=0;n<N;n++)
		printf("%d %d\n", x[n], y[n]);
	free(x);
	free(y);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 1654번: 랜선 자르기 (0)	2021.06.30
<백준 알고리즘> 10814번: 나이순 정렬 (0)	2021.06.25
<백준 알고리즘> 11650번: 좌표 정렬하기 (0)	2021.06.25
<백준 알고리즘> 11055번: 가장 큰 증가 부분 수열 (0)	2021.06.22
<백준 알고리즘> 14002번: 가장 긴 증가하는 부분 수열 4 (0)	2021.06.22

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

예제 입력 1

5
3 4
1 1
1 -1
2 2
3 3

예제 출력 1

1 -1
1 1
2 2
3 3
3 4

Solution

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

int xtemp[100000], ytemp[100000];
void merge(int *x,int *y,int start,int end,int mid,int N)
{
	int i=start, j=mid+1;

	for(int k=	start;k<=end;k++)
		if(j>end)
		{
			xtemp[k]=x[i];
			ytemp[k]=y[i];
			i++;
		}
		else if(i>mid)
		{
			xtemp[k]=x[j];
			ytemp[k]=y[j];
			j++;
		}
		else if(x[i]<x[j] || x[i]==x[j]&&y[i]<y[j])
		{
			xtemp[k]=x[i];
			ytemp[k]=y[i];
			i++;
		}
		else
		{
			xtemp[k]=x[j];
			ytemp[k]=y[j];
			j++;
		}

	for(int k=start;k<=end;k++)
	{
		x[k]=xtemp[k];
		y[k]=ytemp[k];
	}
}

void mergesort(int *x,int *y,int start,int end,int N)
{
	if(start<end)
	{
		int mid=(start+end)/2;
		mergesort(x,y,start,mid,N);
		mergesort(x,y,mid+1,end,N);
		merge(x,y,start,end,mid,N);
	}
}

int main(void)
{
	int N, *x=NULL, *y=NULL;

	scanf("%d", &N);
	x=(int *)malloc(N*sizeof(int));
	y=(int *)malloc(N*sizeof(int));

	for(int n=0;n<N;n++)
		scanf("%d %d", &x[n], &y[n]);

	mergesort(x,y,0,N-1,N);

	for(int n=0;n<N;n++)
		printf("%d %d\n", x[n], y[n]);
	free(x);
	free(y);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 10814번: 나이순 정렬 (0)	2021.06.25
<백준 알고리즘> 11651번: 좌표 정렬하기 2 (0)	2021.06.25
<백준 알고리즘> 11055번: 가장 큰 증가 부분 수열 (0)	2021.06.22
<백준 알고리즘> 14002번: 가장 긴 증가하는 부분 수열 4 (0)	2021.06.22
<백준 알고리즘> 2011번: 암호코드 (0)	2021.06.22

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

예제 입력 1

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1

113

비슷한 문제

<백준 알고리즘> 11053번: 가장 긴 증가하는 부분 수열

<백준 알고리즘> 11054번: 가장 긴 바이토닉 부분 수열

<백준 알고리즘> 11722번: 가장 긴 감소하는 부분 수열

<백준 알고리즘> 14002번: 가장 긴 증가하는 부분 수열 4

Solution

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

int main(void)
{
	int N, *A=NULL, *sum=NULL, max=0;

	scanf("%d", &N);
	A=(int *)malloc(N*sizeof(int));
	sum=(int *)calloc(N,sizeof(int));

	for(int n=0;n<N;n++)
	{
		scanf("%d", &A[n]);
		sum[n]=A[n];

		for(int i=0;i<n;i++)
			if(A[i]<A[n] && sum[i]+A[n]>sum[n])
				sum[n]=sum[i]+A[n];
		max=sum[n]>max?sum[n]:max;
	}

	printf("%d\n", max);
	free(sum);
	free(A);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 11651번: 좌표 정렬하기 2 (0)	2021.06.25
<백준 알고리즘> 11650번: 좌표 정렬하기 (0)	2021.06.25
<백준 알고리즘> 14002번: 가장 긴 증가하는 부분 수열 4 (0)	2021.06.22
<백준 알고리즘> 2011번: 암호코드 (0)	2021.06.22
<백준 알고리즘> 1965번: 상자넣기 (0)	2021.06.22

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4
10 20 30 50

비슷한 문제

<백준 알고리즘> 11053번: 가장 긴 증가하는 부분 수열

<백준 알고리즘> 11054번: 가장 긴 바이토닉 부분 수열

<백준 알고리즘> 11055번: 가장 큰 증가 부분 수열

<백준 알고리즘> 11722번: 가장 긴 감소하는 부분 수열

Solution

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

int main(void)
{
	int N, *A=NULL, *count=NULL, max=0, max_index, *prev=NULL, *stack=NULL, index;

	scanf("%d", &N);
	A=(int *)malloc(N*sizeof(int));
	count=(int *)malloc(N*sizeof(int));
	prev=(int *)malloc(N*sizeof(int));

	for(int n=0;n<N;n++)
	{
		prev[n]=n;
		count[n]=1;
		scanf("%d", &A[n]);

		for(int i=0;i<n;i++)
			if(A[i]<A[n] && count[n]<=count[i])
			{
				count[n]=count[i]+1;
				prev[n]=i;
			}

		if(count[n]>max)
		{
			max=count[n];
			max_index=n;
		}
	}

	stack=(int *)malloc(max*sizeof(int));
	index=max;
	while(index>0)
	{
		stack[--index]=A[max_index];
		max_index=prev[max_index];
	}

	printf("%d\n", max);
	for(int i=0;i<max;i++)
		printf("%d ", stack[i]);
	printf("\n");
	free(stack);
	free(prev);
	free(count);
	free(A);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 11650번: 좌표 정렬하기 (0)	2021.06.25
<백준 알고리즘> 11055번: 가장 큰 증가 부분 수열 (0)	2021.06.22
<백준 알고리즘> 2011번: 암호코드 (0)	2021.06.22
<백준 알고리즘> 1965번: 상자넣기 (0)	2021.06.22
<백준 알고리즘> 11054번: 가장 긴 바이토닉 부분 수열 (0)	2021.06.21

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
상근: 얼마나 많은데?
선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

예제 입력 1

25114

예제 출력 1

6

Solution

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

int main(void)
{
	char password[5001]={'\0', };
	int *code=NULL;

	scanf("%s", password);
	code=(int *)calloc(strlen(password),sizeof(int));

	if(password[0]=='0')
		code[0]=code[1]=0;
	else if(password[1]=='0')
		if(password[0]<'3')
			code[0]=code[1]=1;
		else
			code[0]=code[1]=0;
	else
	{
		code[0]=code[1]=1;
		if(password[0]<'2' || password[0]=='2'&&password[1]<'7')
			code[1]=2;
	}

	for(int i=2;i<strlen(password);i++)
	{
		code[i]=code[i-1];
		if(password[i]=='0')
		{
			if(password[i-1]>'0' && password[i-1]<'3')
				code[i]=code[i-2];
			else
				code[i]=code[i-1]=0;
		}
		else if(password[i-1]=='0');
		else if(password[i-1]<'2' || password[i-1]=='2'&&password[i]<'7')
			code[i]+=code[i-2];

		code[i]%=1000000;
	}

	printf("%d\n", (code[strlen(password)-1]));
	free(code);
	return 0;
}

728x90

'백준 알고리즘' 카테고리의 다른 글

<백준 알고리즘> 11055번: 가장 큰 증가 부분 수열 (0)	2021.06.22
<백준 알고리즘> 14002번: 가장 긴 증가하는 부분 수열 4 (0)	2021.06.22
<백준 알고리즘> 1965번: 상자넣기 (0)	2021.06.22
<백준 알고리즘> 11054번: 가장 긴 바이토닉 부분 수열 (0)	2021.06.21
<백준 알고리즘> 9251번: LCS (0)	2021.06.18