SubClass인 스크립트가 실행될 때 SubClass의 Start() 나 Update()가 명시되어 있지않으면

명시되어 있지않은 함수가 SuperClass에서 호출됨

정확히는 Prefab에 부착된 스크립트의 멤버변수 값을 바꿀때인데

멤버변수의 접근제한지시자가 

private일 경우, 다른 스크립트에서 prefab의 멤버함수를 통해 값을 바꿔도 적용이 안됨

public일 경우, 다른 스크립트에서 prefab의 멤버함수를 통해 값을 바꾸면 바뀐 값이 적용됨

'Unity > 몰랐던 개념' 카테고리의 다른 글

Unity 상속관계인 클래스 Start(), Update() 호출  (0) 2019.09.26

문제

-어느 순서로 도시락을 데워야 가장 빨리 점심시간을 마칠 수 있나?

 

예제 입력

2 //testcase
3 //도시락 수
2 2 2 //데우는데 걸리는 시간
2 2 2 //먹는데 걸리는 시간
3
1 2 3 
1 2 1

예제 출력

8
7

 

중요한 개념

-모든 도시락을 먹는데 같은 시간 C가 걸릴경우 , 어떤 순서로 도시락을 데우건 간에

점심 시간의 길이 = 모든 도시락을 데우는 시간 + 도시락 하나를 먹는 시간

*대신, 가장 먼저 데운 도시락이 마지막으로 데운 도시락을 먹고도 아직 먹고 있는 경우가 있음

(밑에 코드에서 max로 계산)

 

알고리즘 구상

-먹는 시간이 오래걸리는 순서대로 도시락을 데우기

 

코드

#include <iostream>
#include <fstream>
#include <vector>'
#include <algorithm>

int Heat(int boxNum, std::vector<int>& eat, std::vector<int>& cook)
{
	std::vector<std::pair<int,int>> order;
	for (int i = 0; i < boxNum; ++i)
	{
		//먹는데 걸리는 시간을 내림차순으로 편하게 정렬하기 위해 마이너스 붙여줌
		//이러면 가장 큰 수가 가장 작은수가 되고 오름차순 정렬했을 때 원래 가장 큰수가 맨 앞에옴
		order.push_back(std::make_pair(-eat[i],i));
	}
	std::sort(order.begin(), order.end());	

	int eatAndCookTimeSum = 0; 
	int beginEat = 0;
	for (int i = 0; i < boxNum; ++i)
	{
		int box = order[i].second;
		
		beginEat += cook[box];		
		//max(전 도시락까지 다 먹는데 걸리는 시간, 지금도시락을 요리하고 먹는데 까지 걸리는 시간) 비교
		eatAndCookTimeSum = std::max(eatAndCookTimeSum, beginEat + eat[box]);		
	}
	
	return eatAndCookTimeSum;
}

void Solution(std::ifstream& ifstream)
{
	int testcases=0;
	
	ifstream >> testcases;	
	
	for (int i = 0; i < testcases; ++i)
	{		
		int boxNum;
		ifstream >> boxNum;		

		std::vector<int> eat;
		std::vector<int> cook;
		for (int i = 0; i < boxNum; ++i)
		{			
			int tmp;
			ifstream >> tmp;			
			cook.push_back(tmp);
		}
		
		for (int i = 0; i < boxNum; ++i)
		{
			int tmp;
			ifstream >> tmp;			
			eat.push_back(tmp);
		}

		std::cout<<Heat(boxNum, eat, cook) << std::endl;
		
	}

}

int main(void)
{
	std::ifstream ifstream;
	ifstream.open("Input.txt");

	Solution(ifstream);
	return 0;
}

 

시간복잡도 : O(nlgn)

-처음에 모든 도시락을 먹는데 걸리는 시간의 역순으로 정렬하기 위한 시간

문제 : 각 팀에는 n명씩 있고 1:1경기를 하는 대회에서, 상대팀의 출전 순서를 알 경우 어느 순서대로 선수를 내보내야 승수를 최대화 할 수 있는지?

 

#include <iostream>
#include <fstream>
#include <vector>
#include <set>

int order(const std::vector<int>& russian, const std::vector<int>& korean)
{
	int n = russian.size();
	//인자로 넘어간 range의 elements로 multiset 생성
	std::multiset<int> korean_multiset(korean.begin(),korean.end());
	int wins=0;
	
	std::multiset<int>::iterator iter;

	for (int i = 0; i < n; ++i)
	{
		//korea팀원중 가장 높은 점수가 지금 russian팀원의 점수보다 작은 경우
		if (*korean_multiset.rbegin() < russian[i])
		{
			korean_multiset.erase(korean_multiset.begin());
		}
		//korean팀원중 한명이라도 지금 russian팀원의 점수보다 높은 경우
		else
		{
			//russian팀원의 점수보다 작지않은 korean팀원의 점수중 가장 처음 팀원의 점수가 russian팀원가 동점이라면
			if (*korean_multiset.lower_bound(russian[i]) == russian[i])
			{
				std::multiset<int>::iterator iter_tmp = korean_multiset.lower_bound(russian[i]);
				//동점이 아닐 때까지 점수 높은 다음 korean팀원을 고름
				do 
				{
					++iter_tmp;
				} while (*iter_tmp == russian[i]);

				korean_multiset.erase(iter_tmp);
				++wins;
			}
			else
			{
				korean_multiset.erase(korean_multiset.lower_bound(russian[i]));
				++wins;
			}
			
		}

		/*for (iter = korean_multiset.begin(); iter != korean_multiset.end(); ++iter)
		{
			std::cout << *iter << " ";
		}
		std::cout << "/" << russian[i] << std::endl;*/
		
	}

	return wins;

}

void Solution(std::ifstream& ifstream)
{
	std::vector<int> russian;
	russian.push_back(3000);
	russian.push_back(2700);
	russian.push_back(2800);
	russian.push_back(2200);
	russian.push_back(2500);
	russian.push_back(1900);

	std::vector<int> korean;
	korean.push_back(2800);
	korean.push_back(2750);
	korean.push_back(2995);
	korean.push_back(1800);
	korean.push_back(2600);
	korean.push_back(2000);

	std::cout<<order(russian, korean)<<std::endl;
}

int main(void)
{
	std::ifstream ifstream;
	ifstream.open("Input.txt");

	Solution(ifstream);
	return 0;
}

문제

회사에 회의실이 하나밖에 없는데, n(100개이하)의 팀이 각각 회의하고 싶어할 때, 두 팀이 회의실을 같이 쓸수없기 때문에 이 중 서료 겹치지 앟는 회의들만을 골라서 진행해야 할 때, 최대 몇개나 선택할 수 있을까?

 

해결법

1.진행하는 시간 길이와 상관없이 가장 먼저 끝나는 회의부터 선택하는 것

 

시간복잡도

O(nlgn)

 

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

//가능한 최대 회의 수 계산
int Schedule()
{
	int n;
	int begin[100];
	int end[100];

	//1. 회의 추가 및 끝나는 시간으로 오름차순 정렬
	std::vector<std::pair<int, int>> order;
	for (int i = 0; i < n; ++i)
	{
		order.push_back(std::make_pair(end[i], begin[i]));
	}
	//회의가 끝나는 시간으로 오름차순 정렬
	std::sort(order.begin(), order.end());

	//2.끝나는 시간에 맞춰서 가능한 최대 회의 수 계산
	//현시점 회의가 시작할 수 있는 가장 빠른 시간
	int earliest = 0; 
	//가능한 회의 수
	int selected = 0;

	for (int i = 0; i < order.size(); ++i)
	{
		int meeting_begin = order[i].second;
		int meeting_end = order[i].first;
		//현재의 회의가 지금 order에 들어간 회의의 마지막 시간 이후라면
		if (earliest <= meeting_begin)
		{
			earliest = meeting_end;
			++selected;
		}
	}
	
	return selected;
}

Greedy method(탐욕법)

-각 단계마다 지금 당장 가장 좋은 방법만을 선택하는 방법

-지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않음

 

1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적계획법보다 수행 시간이 훨씬 빠르기 때문에 유용

2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어려운 경우 최적해 대신 적당히 괜찮은 답(근사해)를 찾는 것으로 타협함

 

Greedy method algorithm 구상 방법

-간단한 입력을 몇 개 손으로 풀어보면서 패턴을 찾기

 

Greedy method algorithm의 정당성 증명

-정당성 증명(Greedy method algorithm이 항상 최적해를 찾아낼 수 있다는 것)은 많은 경우 일정한 패턴을 가짐

 

1. 탐욕적 선택 속성

-탐욕적으로 선택하더라도 최적해를 구할 수 있다는 것

 

-방법

1. 우리가 선택한 방법을 포함하지 않는 최적해의 존재를 가정

2. 이것을 적절히 조작해 우리가 선택한 방법을 포함하는 최적해를 만듬

 

-예시

회의실 예약 문제를 예로 들면,

조건 : 가장 종료 시간이 빠른 회의를 포함하는 최적해가 반드시 존재

탐욕적 선택 속성이 성립한다는 말은 위의 조건이 성립한다는 의미

 

이 조건을 증명하자면,

1.S(전체 회의 집합)의 최적해 중에 Smin(가장 빨리 종료되는 회의)를 포함하지 않는 답이 있다고 가정(우리가 선택한 방법을 포함하지 않는 최적해의 존재를 가정)

2.이 목록에서 첫번째로 개최되는 회의를 지우고 Smin을 대신 추가해서 새로운 목록 만듬(이것을 적절히 조작해 우리가 선택한 방법을 포함하는 최적해를 만듬)

3.Smin은 S에서 가장 일찍 끝나는 회의이기 때문에 지우진 회의는 Smin보다 일찍 끝날 수 없음

4.따라서, 두번째 회의와 Smin이 겹치는 일은 없고, 새로 만든 회의목록도 최적해중 하나가 됨

5.결과, 항상 Smin을 포함하는 최적해는 존재함

 

이렇게, 증명은 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 불가능해지는 경우는 없음을 보여줌

 

 

 

2. 최적부분구조

-부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보이는 것
-예시

첫번째 회의를 잘 선택하고 겹치는 회의를 모두 걸러냈다면, 남은 회의 중에 최대한 많은 회의를 선택해야함

 

============================================================================

요약

Greedy method algorithm 만드는 순서

1. 문제의 답을 만드는 과정을 여러 조각으로 나눔

2. 각 조각마다 어떤 우선순위로 선택을 내려야할지 결정

3. 어떤 방식이 동작할 것 같으면 두가지속성(탐욕적 선택속성, 최적부분구조)를 증명

 

 

 

차이점

-삽입과 삭제 그리고 임의의 원소에 접근하는데 드는 시간

-삽입과 삭제 경우, Linked list

-탐색 시, Dynamic Array

'Data Structure > By C++' 카테고리의 다른 글

Linked list(연결 리스트)  (0) 2019.08.28
동적 배열(Dynamic array)  (0) 2019.08.28
BFS(너비우선탐색)  (0) 2019.07.30
DFS(깊이우선 탐색)  (0) 2019.07.30

Linked list 

-linked list는 원소들이 메모리 여기저기 흩어져 있고, 각 원소들이 다음 원소를 가리키는 포인터를 가지는 방식으로 구현됨

-임의의 위치에 원소를 삽입, 삭제하는 것이 시간이 오래걸리는 문제를 해결하기 위해 사용

-linked list를 사용하면 특정위치에서의 삽입과 삭제를 상수시간에 할 수 있음

-linked list는 첫번째 node(Head)와 마지막 node(Tail)에 대해 포인터의 가짐

 

 

Node(노드) : 사각형으로 표현된 원소와 포인터의 집합들을 list의 Nod라고 부름

struct ListNode
{
	int element; //담고 있는 원소
    ListNode* prev, next; //이전 노드, 다음 노드의 포인터
}

Linked list의 종류

-양방향 연결 리스트(Doubly linked list) : 각 원소가 이전과 다음 원소에 대한 정보를 모두 가짐

-단방향 연결 리스트(Singly linked list) : 각 원소가 다음 원소를 가리키는 포인터만 가짐

 

Linked list의 장점

-삽입과 삭제가 상수 시간에 이루어짐(포인터만 변경하면 되기 때문에)

 

Linked list의 단점

-Linked list는 메모리 여기저기에 Node들이 흩어져 있음

-따라서, 탐색의 경우 list의 머리에서 부터 시작해 하나씩 포인터를 따라가며 다음 Node를 찾을 수 밖에 없음

-걸리는 시간은 O(N) - list 길이에 선형 비례

 

삭제했던 Node 돌려놓기

-Doubly linked list의 장점

-삭제된 Node의 포인터들은 원래 자기가 들어가 있던 위치를 알고 있기 때문에 가능

-다만, 항상 삭제한 순서의 반대로 복구해야함(이전노드나 이후 노드 또한 삭제된 상태에서 수행하면 list를 망가뜨리기 때문)

 

*C++ STL의 list는 splice()멤버 함수를 통해 잘라 붙이기 연산을 지원하는 대신, list의 크기를 구하려면 O(N)의 반복문을 수행해야함 // 잘라 붙이기 연산을 할 때는 몇 개의 원소가 추가되는지 알 방법이 없기 때문에

반대로, Java,C#은 size()연산을 O(1)에 하는대신 잘라붙이기 연산 포기

 

'Data Structure > By C++' 카테고리의 다른 글

Dynamic Array와 Linked list의 비교  (0) 2019.08.28
동적 배열(Dynamic array)  (0) 2019.08.28
BFS(너비우선탐색)  (0) 2019.07.30
DFS(깊이우선 탐색)  (0) 2019.07.30

동적 배열 : 자료의 개수가 변함에 따라 크기가 변경되는 배열

-메모리 상의 연속적인 공간을 할당

-동적배열은 동적으로 할당받은 배열(new를 통한)을 사용

 

 

동적배열은 배열에 비해 다음과 같은 특성을 지님

-resize() 연산 가능 - 배열의 크기를 변경하는 //  배열의 크기 N에 비례하는 시간 걸림

-append()연산 - 주어진 원소의 배열의 맨끝에 원소 추가하는 

 

동적배열의 메모리 할당방법

-capacity메모리 정책 사용

-메모리를 할당받을 때 배열의 크기가 커질 때를 대비해서 여유분의 메모리(capacity)를 미리 할당받음

-size가 capacity를 넘어서는 경우, 기존메모리 size의 반만큼 늘리고 (결과값이 소수점이면 내림) 배열의 원소를 그쪽으로 옮김

int size; //배열의 크기
ElementType* array; //실제 배열을 가리키는 포인터

동적배열의 append() 연산 시간 복잡도

-size < capacity 경우 O(1) 걸리다가, 

 size  = capacity 경우 재할당 연산을 수행해야 돼서 O(N+M)이 걸림 // N : 원래 원소갯수 , M : 추가 여유 공간 크기

 

-이를해결하기 위해서 재할당을 할때 마다 정해진 크기(상수)를 확보하는 것이 아니라, 현재 가진 원소의 개수에 비례해서 여유크기를 확보

-이런 식이면, 평균적으로 O(1)이 걸림

 

*제일 좋은 방법은 배열의 최종 크기를 미리 안다면, 동적 배열의 용량을 사전에 충분히 늘려둬서 재할당에 드는 비용을 없앰 ( C++의 reserver()이용해서)

 

 

'Data Structure > By C++' 카테고리의 다른 글

Dynamic Array와 Linked list의 비교  (0) 2019.08.28
Linked list(연결 리스트)  (0) 2019.08.28
BFS(너비우선탐색)  (0) 2019.07.30
DFS(깊이우선 탐색)  (0) 2019.07.30

+ Recent posts