SWSSM TEAM BLOG

한 쪽 배열을 오름차순으로 정렬하고

다른 한 쪽 배열을 내림차순으로 정렬하여 해결한다.

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

조합(combination)을 구하는 문제로 해석할 수 있다.

보통 고등학교에서 배우는 방법대로 조합을 구하다 보면 integer overflow가 발생할 수 있고

반복된 연산으로 Time-Limit 될 수 있다.

그렇기 때문에 배열을 이용하여 조합을 나타내 보기로 했다. (Dynamic Programming)

아래는 nCr을 나타낸 표이다.

이 표를 배열로 나타낸다고 했을 때

arr[i][j] = arr[i-1][j-1] + arr[i][i-1][j] 라는 규칙을 찾을 수 있다.

이 규칙을 이용하여 표를 모두 채우고 시작한다면 조합을 쉽게 찾을 수 있다.

문제 출처 : http://www.acmicpc.net/

8진수를 2진수로 바꾸라는 문제다.

복잡하게 문제를 해결하던 중 직관적이고 간단한 해법이 생각났다.

8진수, 0부터 7까지의 모든 경우의 수를 배열에 저장해보았다.

문제 출처 : http://www.acmicpc.net/

우리 실전알고리즘은

ACM-ICPC (대학생 프로그래밍 경시대회) 형식의 문제를 풀어보고자 그룹 스터디를 시작하게 되었습니다.

교재는 따로 없으며 http://www.acmicpc.net/ 의 문제를 풀어갈 계획입니다.

경찰 & 전화 & 병원 시리즈 script

Question]

You may chat on the phone. With whom do you usually talk and how often do you talk on the phone? And what topic do you talk about?

Answer]

Yes, I love chatting on the phone. I chat with my friends most of time. I talked to my college friend last night. We just talked about our situation .Both of us are unemployed at the moment and we are both hunting for a new job. She told me to come with her next week for a walk-in application in one company. We also talked in relation to the recent updates in our friend's and experiences. We always have a lot to talk about. different topics every night and we never run out of topics to discuss over the phone. It is good to keep in touch with my friends through the phone.

Question]

For how long do you talk over the phone? And tell me about the advantages of using a phone for chatting.

Answer]

When I am not working and i'm just at home, I chat over the phone for hours. I always call all my friends and sometimes do a call conference with them. it takes more than an hour when we have a call conference. I spend almost my entries day just chatting with my friends. I think chatting over the phone has plenty of advantages. you can send SMS and music through your mobile phone. You'll be able to see face to face with the person on the other line and you can do a conference all. It it fun to talk to many people at their same time. Phones also come in handy to use

Question]

When was the time when you had a long chat for a long time recently? Was it about a good thing or bad thing? Please tell me in as much detail as possible.

Answer]

I had a very long chat with my colleague from my previous company last night. it was a good thing at first because we got to talk about the past and our recent endeavors. She told me about her promotion at work. I got really envious of her and her higher position. I thought that I have always worked harder than her. But, actually, I'm not in a good state right now. I just thought that it was unfair. I asked her secret to her success and she gave me some tips, so maybe I can also be successful. I am still very upset for myself, yet it was good to hear her secret to success.

가족 & 집 역할 연기 관련 script

Question]

I am going to give you a situation for you to act out. Let's assume that you need new furniture at home but your parent don't want to have it. Explain why you need new furniture and convince them to get it by giving two alternatives.

Answer]

I really think we should buy new furniture for our house. We have to purchase a new kitchen cabinet and a study table. It is for our own benefit and we could use them for a long time. Our study table is too small for our documents and books now. So we must buy a bigger one to accommodate them. Our kitchen is also out of storage that's why I suggest that we purchase new storage furniture, where we could store the dry goods we have in the kitchen. I think it'll give more space to organize the house. if you don't want to buy furniture, we can pay for a laborer or a carpenter to make a storage cabinet and a study table for us. Which do you prefer?

Question]

I live in an apartment/house, too. Please ask me three or four questions that you wish to know about the place where I now live in.

Answer]

- Do you have a 24 hour transportation available in your neighborhood?

- Do you have 24 hours security in you vicinity?

- Can you tell me the design of your apartment? Is it more of an elegant apartment or just a typical apartment?

- Is your place accessible to markets, schools, and churches?

Question]

I am going to give you a situation for you to act out. One of your relatives wants you to take care of the house while he/she is on vacation. Ask three or four questions that you wish to know about ti.

Answer]

- When are you coming back from your trip?

- Where are you planning to travel?

- Can I invite my sister along to look after your house?

- Do you have any security systems to set up every night?

Question]

Unfortunately, you have a problem to solve. When you arrived at his/her house, the door was wide open and you are sure that someone broke in. First, look arount the house. Then, call the police to report burglary. explain the situation and offer them the right reason to come as soon as possible.

Answer]

Hello, police station? This is an emergency call. I am here at No.276 New Street, at my aunt's house. I think a burglar broke into the house. I don't know what to do. Will you come immediately? My Aunt and cousins went off for a trip early this morning so it is impossible for them to come back. The lights inside are off for a trip early this morning so it is impossible for them to come back. The lights inside are off and I can't hear anything. The door at the back of the house is wide open. Can you come as soon as possible? What can you suggest me to do while waiting for you? I really am in a panic here. There is a motorcycle parked beside the sidewalk and I think it is the burglar's. Please take action on this matter right away. The burglar might seize all our valuables.

스포츠 콘서트 관련 Script

Question]

You replied in ther Background Survey that you watch sports games. What kind of sports games do you like to watch? Tell me about the reason you watch them in detail.

Answer]

I am not really a sporty person, yet I love watching ball games on TV. My most favorite game would be soccer. I think soccer player are very strong and well disciplined. The action in their court is really exiting and the fans are very supportive to their favorite player or team. I also think that soccer is a physical game but it has good rules and regulation for the benefit of the players. Most of soccer player are friendly to their fans. I say the because I usually see them waving or shaking hands with their fans after every games

Question]

You have answered that you go to concerts. How frequently and with whom do you go there?

Answer]

I go to concerts maybe thrice a year of more if there are really good artist that i'd like to see perform. But mostly it's three times a year. I commonly go with friends and family. I once went to Rain's Concert in seoul with my foreign friend who just visited Korea. I think that was two years ago. The concert made me become a huge fan of Crayon-Pop. Everybody enjoyed the concert and Crayon-Pop left us wanting more. I think the artist is very sociable. They are so entertaining and they has greate moves. Though their voice is not amazingly beautiful, I can say the they are talented and ther are a good entertainer.

Question]

I'd like to know about your activities at the concert hall. Can you tell me about all of your activities before the concert starts and after it ends?

Answer]

I went to Crayon-Pop's Concert in Seoul with my foregin friend last month. The things I do at concert are pretty much similar with other people. Before the concert starts, I ask my friend to go and buy something to eat, because I want to be ready for the concert. We usually buy a can of soda and cheese burger from a stall. After having a snack, I am ready to enjoy the night. After the concert, I take some pictures inside the hall. I also go to the autograph signing in front of the stage, but sadly I haven't got any autographs from any singers yet because there are always too many people waiting in line. So I normally just go to the souvenir shop and buy some merchandise ther I set off back home.

끝까지 유종의 미를 거둬봐요 ㅋ

Devide and Conquer~

ch12_분할정복.pptx

struct linkedlist{
	int data;
	struct linkedlist *next;
	struct linkedlist *prev;
};
typedef	struct linkedlist LINKEDLIST;
typedef LINKEDLIST *LINK;

void heapTree( LINK *node, int data ){
	if( *node == NULL ){
		*node = newList(data);
	}else{
		if( (*node)->data > data ){
			heapTree( &(*node)->prev , data );
		}else{
			heapTree( &(*node)->next , data );
		}
	}
}

void preorder( LINK node ){
	if(node->data != NULL)
		printf("%d",node->data);
	if(node->prev != NULL)	
		preorder(node->prev);
	if(node->next != NULL)
		preorder(node->next);
}

void postorder( LINK node ){
	if(node->prev != NULL)	
		preorder(node->prev);
	if(node->next != NULL)	
		preorder(node->next);
	if(node->data != NULL)
		printf("%d",node->data);
}

void inorder( LINK node ){
	if(node->prev != NULL)
		preorder(node->prev);
	if(node->data != NULL)
		printf("%d",node->data);
	if(node->next != NULL)
		preorder(node->next);
}
void main(void){
	LINK root = NULL;//= (LINK)malloc(sizeof(LINKEDLIST));	
	heapTree(&root,11);
	heapTree(&root,10);
	heapTree(&root,12);

	printf("  PREORDER : ");
	preorder(root);
	printf("  POSTORDER : ");
	postorder(root);
	printf("  INORDER : ");
	inorder(root);
}

1 - 1 싱글 링크드 리스트

struct linkedlist{
	int data;
	struct linkedlist *next;
};
typedef	struct linkedlist LINKEDLIST;
typedef LINKEDLIST *LINK;
LINK newList( int data ){
	LINK list;
	list = (LINK)malloc(sizeof(LINKEDLIST));
	list->data = data;
	list->next = NULL;
	return list;
}
void appendList( LINK list, LINK argu ){
	list->next = argu;
}
LINK findList( LINK head, int value ){
	LINK list = head;
	while(list->data != value){
		list = list->next;
		if(list->next == NULL){
			break;
		}
	}
	return list;
}
void deleteList( LINK head, LINK find ){
	find->prev->next = find->next;
	free(find);
}
void printList( LINK head ){
	LINK print = head->next;
	while(print != NULL){
		printf("%d\n",print->data);
		print = print->next;
	}
}
void main(void){
	head = newList(-1);
	appendList( head, newList(4) );
	appendList( head, newList(3) );
	appendList( head, newList(2) );
	appendList( head, newList(1) );
	deleteList( head, findList( head, 1 ) );
	deleteList( head, findList( head, 3 ) );
	printList(head);
}

2 - 1 더블 링크드 리스트

struct linkedlist{
	int data;
	struct linkedlist *next;
	struct linkedlist *prev;
};
typedef	struct linkedlist LINKEDLIST;
typedef LINKEDLIST *LINK;

LINK newList( int data ){
	LINK list;
	list = (LINK)malloc(sizeof(LINKEDLIST));
	list->data = data;
	list->next = NULL;
	list->prev = NULL;
	return list;
}
void appendList( LINK list, LINK argu ){
	list->next->prev = argu;
	argu->next = list->next;
	list->next = argu;
	argu->prev = list;
}

LINK findList( LINK head, int value ){
	LINK list = head;
	while(list->data != value){
		list = list->next;
		if(list->next == NULL){
			break;
		}
	}
	return list;
}
void deleteList( LINK head, LINK find ){
	find->next->prev = find->prev;
	find->prev->next = find->next;
	free(find);
}
void printList( LINK head ,LINK tail){
	LINK print = head->next;
	while(print != tail){
		printf("%d\n",print->data);
		print = print->next;
	}
}
void init( LINK head, LINK tail ){
	head->next = tail;
	tail->prev = head;
}
void main(void){
	head = newList(-1);
	tail = newList(-1);
	init( head, tail );
	appendList( head, newList(4) );
	appendList( head, newList(3) );
	appendList( head, newList(2) );
	appendList( head, newList(1) );
	deleteList( head, findList( head, 1 ) );
	deleteList( head, findList( head, 3 ) );
	printList(head,tail);
}