'알고리즘'에 해당되는 글 8건

  1. 2010.07.13 C- ACM - 휴대폰번호 정렬
  2. 2010.07.07 C- ACM - 대지
  3. 2010.07.02 C- ACM - 다운로드
  4. 2010.06.12 C- ACM - 수 뒤집기
  5. 2010.06.07 C- ACM - 더하기
  6. 2010.05.22 C - 알고리즘 - 퀵정렬 (1)
  7. 2010.05.15 C - 알고리즘 - 삽입정렬 (3)
  8. 2010.05.14 C - 알고리즘 - 버블정렬
엑셀을 만들라는 문제..드뎌 온갖 야매란 야매는 다 써서 풀었답니다~ ㅋㅋㅋ
D. 휴대폰번호 정렬
(Time Limit: 2 seconds)
LK 텔레콤에 근무하는 신입사원 정희에게 부장님이 새로운 업무를 지시했다. 고객들의 휴대폰 전화번호를 정렬하는 작업이다.
휴대폰 번호는 국번 3 자리와 중간국번 3자리 또는 4자리, 그리고 뒷 자리 수 4 자리로 총 10 개 혹은 11 개의 숫자로 이루어진다.
그리고 휴대폰 국번은 010, 011, 016, 017, 018, 019 의 여섯 가지가 존재한다. 국번과 중간국번, 뒷자리 수는 하이픈(“-”)으로 구분된다. 부장님이 원하는 요구사항은 다음과 같다. 우선, 특정 국번 번호 순서로 정렬이 되어야 하며, 국번이 같은 경우에는 중간국번 숫자끼리 비교해서 오름차순 정렬이 되어야 하며, 중간국번도 같은 경우에는 뒷자리 번호를 비교해서 오름차순으로 정렬이 되야 한다. 단, 부장님이 원하는 정렬순서는 국번이 같을 경우 중간국번 4 자리인 휴대폰 번호가 중간국번 3 자리인 휴대폰 번호보다 항상 정렬 우선순위가 높다. 즉, 국번이 같은 경우 중간국번 4 자리인 휴대폰 번호가 중간국번 3자리인 휴대폰 번호보다 정렬 시 항상 먼저 등장한다. 예를 들어, 다음과 같은 휴대폰 번호를 정렬한다고 하자.

011-275-3587
017-1111-2600
019-222-2222
017-111-1234
018-275-9562
010-333-1111
016-1235-3333
이 번호들을 017 / 011 / 018 / 019 / 010 / 016 국번 순으로, 그리고 중간국번 4 자리가 중간국번 3자리보다 우선순위가 높도록 정렬을 한다면, 아래와 같이 정렬이 될 것이다.
017-1111-2600
017-111-1234
011-275-3587
018-275-9562
019-222-2222
010-333-1111
016-1235-3333
위의 결과에서 첫 번째 라인의 017-1111-2600 과 두 번째 라인의 017-111-1234 를 비교해보면, 중간국번 111 은 1111 보다 작으므로 일반적으로는 정렬 시 017-111-2600 이 먼저 등장해야 하나, 부장님의 요구사항에서 중간국번 4 자리가 중간국번 3 자리보다 항상 정렬 우선순위가 높다는 규칙 때문에 017-1111-2600 이 017-111-1234 보다 먼저 등장한 것을 알 수 있다.
Input
첫 줄에는 테스트 케이스의 개수 T ( 0 < T <= 20 ) 가 주어진다.각각의 테스트케이스의 첫 번째 줄에는 정렬할 휴대폰 번호의 개수 N(0 < N <= 50) 이 주어진다.테스트케이스의 두 번째 줄에는 0, 1, 6, 7, 8, 9 의 6개의 숫자가 임의의 순서로 표시된다.이 숫자들은 휴대폰 국번을 의미하며, 6개의 숫자들이 나열되는 순서는 테스트 케이스마다 바뀔수 있다. 당신은 이 순서대로 국번 별 순서로 휴대폰번호를 정렬해야 한다.예를 들어, 숫자 7 1 8 9 0 6 이 표시됐다면 017 / 011 / 018 / 019 / 010 / 016 국번 순으로 정렬해야 한다. 세 번째 줄부터는 라인 당 하나씩의 휴대폰 번호가 N 개 만큼 입력된다. 휴대폰 번호에서 국번은
010, 011, 016, 017, 018, 019 의 여섯 가지만 입력되며, 휴대폰 번호는 0 부터 9 까지의 숫자와 “–“ 로 구성되며, 빈칸을 포함하지 않으며 그 외 다른 문자는 포함되지 않는다. 참고로, 우리나라 휴대폰 번호에서 010 국번의 경우 중간국번은 항상 4 자리지만 이 문제에서는 010 국번도 중간 국번이 3 자리가 될 수 있다고 정의한다. 즉, 모든 휴대폰번호는 국번에 상관없이 중간국번이 세자리 혹은 네 자리가 될 수 있다.
#include 
#include 		// atoi
#include 		// abs

#define SWAP(x,y,t) (t=x), (x=y), (y=t)		//스왑정의

typedef struct phone_num
{
	unsigned int fst_num;	//사업자번호 (010등)
	unsigned int snd_num;	//나머지번호
}num;

int main(void)
{
	num list[50];			//스트럭쳐 50개
	num list_temp;			//스왑에 사용할 스트럭쳐 한개 
	char in_txt[14];		//문자열 배열
	int N, repeat, temp;	//번호갯수, 테스트케이스, 스왑용변수
	int st_num[6];			//사업자번호 끝자리 정렬용

	scanf("%d",&repeat);
	
	for(int z=0; z[repeat; z++)
	{
	scanf("%d",&N);		
	scanf("%d %d %d %d %d %d ",&st_num[0], &st_num[1], &st_num[2], &st_num[3], &st_num[4], &st_num[5]);
	
	for(int i=0; i[N; i++)
	{
		gets(in_txt);

		list[i].fst_num=atoi(in_txt+2);		//사업자번호 끝자리만 숫자로 변경하여 구조체에 넣음 
		list[i].snd_num=atoi(in_txt+4)*10000+abs(atoi(in_txt+8));	// 중간자리를 받아 10000을 곱함 + 끝자리를 받아 중간자리에 더함
	}

	for(int i=0; i[N; i++)	// 삽입정렬
	{
		if(list[i].snd_num>list[i-1].snd_num){temp=list[i].snd_num;}else{continue;}
		
		for(int j=0; j[N; j++)
		{
			if(list[j].snd_num[temp){SWAP(list[i], list[j], list_temp);}
		}
	}
	printf("------------------\n");

	for(int j=0; j[6; j++)	//정렬된 수를 사업자 번호의 순서에 맞게 출력
	{
		for(int i=0; i[N; i++)
		{
			if(st_num[j]==list[i].fst_num){printf("01%d-%d-%d\n", list[i].fst_num, list[i].snd_num/10000, list[i].snd_num%10000);}
		}
	}
	printf("------------------\n");
	}

	return 0;
}
 
저작자 표시
신고

'3_ 담백한알고리즘' 카테고리의 다른 글

알고리즘 사이트 모음  (0) 2011.09.19
Algorithm - Counting Sort  (1) 2011.03.30
C- ACM - 휴대폰번호 정렬  (0) 2010.07.13
C- ACM - 대지  (0) 2010.07.07
C- ACM - 양말 짝 맞추기  (0) 2010.07.02
C- ACM - 다운로드  (0) 2010.07.02
Posted by 준환이형님

댓글을 달아 주세요

예전에 우리 벽보를 함부로 덮은 타동아리 포스터 면적을 계산해서 따지러가는 문제가 있었는데 그거랑 유사하네요. 스토리도 은근탄탄 ㅋ


 임씨는 1950년 한국전쟁으로 많은 손해를 본 사람들 중 하나다. 전쟁 통에 손해보지 않은 사람이 어디 있을까 만은 그는 6.25가 일어나기 전만 해도 충청도 지방에 넓은 대지를 소유한 큰 부자였다. 전쟁이 나자 임씨는 땅문서와 값 나가는 것들만 챙겨서 일본으로 피난을 가지만 피난 중에 그만 땅문서를 잃어버리고 만다. 전쟁이 끝난 후에 임씨의 땅은 이미 다른 사람들의 논밭이 되어 있었고, 임씨는 땅을 되찾으려 했지만 문서가 없으니 생떼 쓰는 것과 다를 바 없었다. 이러다가 임씨는 길바닥에 나앉게 생겼다.
이 때, 임씨에게 좋은 생각이 떠올랐으니 바로 자신이 습관처럼 땅 깊숙이 뭔가 표식을 해놓았던 사실이다. 임씨는 한적할 때마다 자신의 논밭을 거닐다가 땅속 깊은 곳에 자신의 이름이 씌어진 옥구슬을 묻어놓았던 것이다. 즉, 어떤 지점에서 그의 이름이 적힌 옥구슬이 나온다면 그 지점은 예전에 임씨의 땅이었다는 것을 증명하는 것이다.
  임씨는 즉시 민사소송을 통해 자신의 땅을 찾고자 했고 논리적인 근거를 들어 옥구슬이 나오는 지점이 원래 자신의 땅의 한 지점이었다는 것을 주장하여 결국 담당판사를 설득하는 데에 성공하였다. 담당판사는 다음과 같은 판결을 내렸다. "6.25이전의 개인소유 대지들은 99%가 남북, 동서 방향으로 평행한 직사각형 모양이었으므로, 임씨의 이름이 새겨진 옥구슬이 나오는 모든 지점을 포함하는 가장 작은 남북, 동서 방향으로 평행한 변을 갖는 직사각형의 대지를 임씨의 소유로 인정한다." 임씨는 많은 손해를 보는 셈이지만 더 이상을 요구할 만한 근거가 없었기 때문에 이 판결을 따르기로 했다.

  임씨의 이름이 새겨진 옥구슬의 위치 N 개가 주어질 때에, 임씨에게 돌아갈 대지의 넓이를 계산하는 프로그램을 작성하시오. 단, 옥구슬의 위치는 2차원 정수 좌표로 주어지고 옥구슬은 같은 위치에 여러 개가 발견될 수도 있으며, x축의 양의방향을 동쪽, y축의 양의방향을 북쪽이라고 가정한다. 
 

   예를 들어 위와 같이 (2, 1), (3, 2), (5, 2), (3, 4) 네 점에서 옥구슬을 발견하였다면, 임씨에게 돌아갈 대지는 (2, 1), (5, 1), (2, 4), (5, 4)를 네 꼭지점으로 하는 직사각형이며, 넓이는 (5 - 2) × (4 - 1) = 9가 된다.
 
입력
입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에는 점의 개수 N (1 ≤ N ≤ 100,000) 이 주어진다. 이어지는 N 줄에는 각 점의 좌표가 두 개의 정수로 한 줄에 하나씩 주어진다. 각각의 좌표는 -10,000 이상 10,000 이하의 정수이다.

출력
출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 N 개의 점을 둘러싸는 최소 크기의 직사각형의 넓이를 출력하시오.

#include 
#include 

int main(void)
{
	int num,x,y,dir_N,dir_E,dir_W,dir_S;
	
	dir_N=dir_E=-10000;		//디폴트
	dir_W=dir_S=+10000;

	scanf("%d",&num);

	for(int i=0; i[num; i++)
	{		
		scanf("%d %d",&x,&y);

		if(y]dir_N){dir_N=y;}
		if(y[dir_S){dir_S=y;}
		if(x]dir_E){dir_E=x;}
		if(x[dir_W){dir_W=x;}
	}
	printf("%d\n",abs(dir_E-dir_W)*abs(dir_N-dir_S));
	return 0;
} 
저작자 표시
신고

'3_ 담백한알고리즘' 카테고리의 다른 글

Algorithm - Counting Sort  (1) 2011.03.30
C- ACM - 휴대폰번호 정렬  (0) 2010.07.13
C- ACM - 대지  (0) 2010.07.07
C- ACM - 양말 짝 맞추기  (0) 2010.07.02
C- ACM - 다운로드  (0) 2010.07.02
C- ACM - 지뢰찾기  (4) 2010.06.23
Posted by 준환이형님

댓글을 달아 주세요

ㅋㅋㅋ 이런 문제 좋음~
정희는 한 음악 포털 사이트에서 일정 금액을 충전하여 mp3파일을 다운로드 받아서 사용해 왔다.
지금 이 사이트에서 k곡을 다운받으면 한 곡을 무료로 다운받을 수 있는 이벤트를 진행 중이고, 현재 정희가 다운받을 수 있는 mp3파일의 개수는 n개이다. 이벤트 기간 중 정희가 다운받을 수 있는 총 mp3파일의 개수는 몇 개인가?
첫 줄에는 테스트 케이스의 개수 T ( 0 < T <= 100000 ) 가 주어진다.
한 줄당 하나의 입력이 입력되며, 각 입력 케이스는 n과 k 두 개의 정수로 이루어져 있고, 하나의 스페이스로 구분된다. ( 0 < n < 1000000, 1 < k <= 21)
각 테스트 케이스에 대해 각 케이스마다 정희가 다운받을 수 있는 총 mp3파일의 개수를 출력한다.
4 3   ->5
10 3  ->14
100 5 -> 124
#include 

int main(void)
{
	int n ,k, plus;
	scanf("%d %d",&n, &k);
	
	plus=n/k;
	plus+=plus/k;
	
	printf("%d %d -> %d\n",n,k,plus+n);

	return 0;
} 
저작자 표시
신고

'3_ 담백한알고리즘' 카테고리의 다른 글

C- ACM - 대지  (0) 2010.07.07
C- ACM - 양말 짝 맞추기  (0) 2010.07.02
C- ACM - 다운로드  (0) 2010.07.02
C- ACM - 지뢰찾기  (4) 2010.06.23
C- ACM - 수 뒤집기  (0) 2010.06.12
C- ACM - 소수판정  (0) 2010.06.09
Posted by 준환이형님

댓글을 달아 주세요


언뜻 배열을 생각 할 수도 있으나 10진수 쉬프트의 개념으로 접근한다면 깔끔하게 풀수 있다는 조언을 받았죠.
즉, 변수 하나를 만들어서 
1234  -> NULL
123   ->       4
12    ->      43
1     ->     432
이런식으로 원본(좌측)수는 나머지를 구한뒤 10씩 나누고 사본(우측) 은 원본의 나머지를 가져온뒤 10씩 곱해가는 과정입니다. 아 신기하당~ㅋㅋ

  
#include 

int swapnum(int num_temp)		//뒤집은 수를 만드는 함수
{
	int num_next=NULL;			// 1. 빈 변수를 하나 만든뒤

	while(num_temp>0)			// 2. 원본의 수가 한자리가 될때까지 반복
	{
		num_next*=10;			// 3. 사본에 10씩 곱해서 앞으로 채워 넣습니다
		num_next+=num_temp%10;	// 4. 원본의 끝자리를 사본에게 보냅니다
		num_temp/=10;			// 5. 원본을 10씩 나누어서 다음수가 오게 합니다
	}
	return num_next;			// 6. 뒤집힌 수 출력
}

int main(void)
{
	int repeat=NULL;	
	int num1, num2;
	num1=num2=NULL;

	scanf("%d", &repeat);	// 입력반복 횟수

                for(int i=0; i< repeat; i++)
               {
		scanf("%d", &num1);
		num2=swapnum(num1)+num1;	//원본과 뒤집힌 수를 더합니다

		if(swapnum(num2)==num2){printf("YES\n");}else printf("NO\n");	//두번째 원본과 뒤집힌수의 비교

		num1=num2=NULL;	// 다음 씬을 위한 초기화
	}
	return 0;
}
저작자 표시
신고

'3_ 담백한알고리즘' 카테고리의 다른 글

C- ACM - 다운로드  (0) 2010.07.02
C- ACM - 지뢰찾기  (4) 2010.06.23
C- ACM - 수 뒤집기  (0) 2010.06.12
C- ACM - 소수판정  (0) 2010.06.09
C- ACM - 문자열  (0) 2010.06.08
C- ACM - Coin  (0) 2010.06.08
Posted by 준환이형님

댓글을 달아 주세요

 대학생 경시대회의 기초 알고리즘 문제를 풀어봅시다. 이 코너는 부산-경남지역 알고리즘의 마스터 사로자바님과 함께 합니다 :D


#include <stdio.h>

int main(void)
{
 int set, num, repeat;
 int sum=NULL;

 scanf("%d", &repeat);

 for(int i=0; i<repeat; i++)
 {
  scanf("%d",&set);

  for(int i=0; i<set; i++)
  {
   scanf("%d",&num);
   sum+=num;
  }
  printf("%d\n",sum);
  sum=NULL;
 }
 return 0;
}

저작자 표시
신고

'3_ 담백한알고리즘' 카테고리의 다른 글

C- ACM - 지뢰찾기  (4) 2010.06.23
C- ACM - 수 뒤집기  (0) 2010.06.12
C- ACM - 소수판정  (0) 2010.06.09
C- ACM - 문자열  (0) 2010.06.08
C- ACM - Coin  (0) 2010.06.08
C- ACM - 더하기  (0) 2010.06.07
Posted by 준환이형님

댓글을 달아 주세요

아휴, 이게 며칠동안 왜 이리 이해가 되지 않았을까요ㅎ

#include <stdio.h>
#define SWAP(x,y,t) (t=x), (x=y), (y=t); //스왑을 간단하게

void partition(int data[],int length){
 int temp=NULL;
 int head=-1;
 int tail=length-1;
 int pivot=data[tail]; //끝자락의 아무 아이가 합격선이 되겠네요.. 좋은 방법은 아니라지만 전 쉬워서 좋아요 :D
 if(length<1){return;}  
 while(true)
 {
  while(data[++head]<pivot); //머리에서부터  잡아냄
  while(data[--tail]>pivot); 
  if(head>=tail) break;  //머리가 추월시 끝냄
  SWAP(data[head],data[tail],temp);
 }
 SWAP(data[length-1],data[head],temp); //마지막에는 기준을 가운데 쏙 넣어줌

 partition(data,head);//첨부터 가운데까지
 partition(data+head+1,length-head-1);//가운데서 끝까지
 return;}

int main(void)
{
 int data_box[]={6,4,7,3,8,2,9,0,1,5};
 int box_lenth= sizeof data_box/sizeof data_box[0];
 partition(data_box,box_lenth);
 for(int i=0;i<box_lenth;i++){printf("%d ",data_box[i]);}printf("\n");
 return NULL;}

저작자 표시
신고
Posted by 준환이형님

댓글을 달아 주세요

  1. 2010.05.24 03:11 Address Modify/Delete Reply

    비밀댓글입니다

코드가 길어 행을 줄였습니다. 이렇게 하면.. 예쁘지는 않지만~ (사랑스러워~)
삽입정렬은.. 마치 [왕자와 거지]게임 같아서 한번 내동댕이 쳐진 숫자는 밑바닥에서부터 자리를 찾아 쏙 넣어진답니다..(-_-?)

리스트를 이용한 삽입정렬은 링크를 참조하세요(http://topnanis.tistory.com/176)

그림을 보면-


#include <stdio.h>

#include <string.h>                                            //memmove함수사용


int main(void)

int temp=NULL;

int data_set[]={8,6,7,9,4,3,5,2,1,10};

for(int i=0; i<9; i++)

if(data_set[i-1]>data_set[i]) temp=data_set[i];  //정렬되지 않은 수를 temp에 태워 처음으로 보냄

else continue;


for(int j=0; j<i; j++)

{  

if(temp<data_set[j]) //자리를 찾았다면

{                                                               // 이사  될 자리- 예전자리 범위를 전체 우로 일보.

memmove(&data_set[j+1], &data_set[j], sizeof(data_set[0])*(i-j)); 

data_set[j]=temp;

break;

}

for(int i=0; i<10; i++) printf("%d ",data_set[i]);

return 0;

}



 

사로자바님의 말에 따르면 리소스의 사용은 [크기비교]가 아닌 [교환]에서 일어나는 것이랍니다. 교환횟수를 비교해 보았을때 삽입정렬은 뽀글정렬과 비교가 안될정도로 우수한 성능을 자랑하는군요 :D




저작자 표시
신고
Posted by 준환이형님

댓글을 달아 주세요

  1. mindle 2014.04.15 22:16 신고 Address Modify/Delete Reply

    memmove함수 사용 없이 작성하려면 어떻게 해야되나요 ?

  2. mindle 2014.04.15 22:16 신고 Address Modify/Delete Reply

    memmove함수 사용 없이 작성하려면 어떻게 해야되나요 ?

  3. mindle 2014.04.15 22:16 신고 Address Modify/Delete Reply

    memmove함수 사용 없이 작성하려면 어떻게 해야되나요 ?

글씨가 한단계씩 정렬되는 모습을 본떠 버블정렬이라 했다네요. 리스트를 이용한 버블정렬은 링크를 참조하세요(http://topnanis.tistory.com/176)


아래코드는 엔터를 칠때마다 글자가 정말 뽀글뽀글 옆으로 이동한답니다~ 궁금하지 않나요? ㅋ

#include <stdio.h>

#include <conio.h>

#include <windows.h>


int main(void)

{

int DataSet[]={6,4,2,3,1,5};

int temp=NULL;

int stop;

int time=0;


printf("Bubble Algorithm\n");


for(int i=0; i<6; i++)

{

printf("%d ",DataSet[i]);

}

for(int i=0; i<5; i++)

{

for(int j=0; j<5-i; j++)

{   

if(DataSet[j]>DataSet[j+1])

{

temp=DataSet[j];


DataSet[j]=DataSet[j+1];


DataSet[j+1]=temp;


stop=getch();

time++;

system("cls");

printf("Bubble Algorithm : %d times\n",time);


for(int i=0; i<6; i++) printf("%d ",DataSet[i]);

}

}

printf("\n");

return 0;

}


저작자 표시
신고
Posted by 준환이형님

댓글을 달아 주세요