[STL]벡터(vector) 심화 - erase(), resize()로 인한 원소 처리
소스는 없다.
이전 포스팅을 첨고로 봐보도록 하자.
-------------------------------------------------------
벡터(vector)는 크기(size), 용량(capacity)를 별도로 가지고 있다.
capacity는 현재 벡터가 차지할 수 있는 메모리 전체영역이고
size는 영역내에 채워져서 사용되고 있는 부분이다.
배열이 고정된 메모리를 가지고 처리한다면
벡터는 유동적인 메모리 공간을 가질 수 있다.
벡터는 유동적인 배열로 불러도 손색이 없다.
그럼 여기서 궁금한 것이 생각났다.
erase와 resize로 벡터의 원소를 빼앗을 경우 어떻게 되겠는가?
예를 들어본다.
용량은 8이고 원소는 아래와 같이
100 200 300 400 500
5개의 원소를 집어 넣었다.
그럼 현재 벡터의 메모리 내부는
100 200 300 400 500 ? ? ?
이렇게 채워져 있을 것이다.
벡터를 이용한 접근 가능한 부분을 파란색
접근 불가한 부분을 붉은 색으로 재표시 해보자.
100 200 300 400 500 ? ? ?하지만 at()으로 접근 할 수 있는 것은
벡터 begin() + 4 까지이다.(여기서 begin()은 end() - 5와 같고 begin() + 4는 end() - 1과 같다.)
5이상 부터는 에러가 난다.
여기서 erase(begin() + 4)을 하면 500을 지우라는 명령이 된다.
하지만 실제 500이 지워지는가?
아니다. 지워지지 않는다. 그대로 그자리에 남아있다.
단 벡터를 이용한 접근이 불가할 뿐이다.
색을 주어서 표시해보자.
100 200 300 400 500 ? ? ?
위처럼 메모리 상에 값은 남아있다.
하지만 저 주소를 알지 못하는 이상 접근 할 수 없다.
다시 300을 뺀다면 어떻게 될까?
300은 400에 덮여씌워져 지워진다. 하지만 400이 남는다.
100 200 400 400 500 ? ? ?여기서 또 100을 지웠다고 해보자.
그럼 아래와 같이 메모리내에 값 구성이 된다.
200 400 400 400 500 ? ? ?
이제 대충 보이는가?
[조사식 분석]
resize()도 마찬가지이다.
5개 원소가 들어있을 때
resize(3)을 하면
3 만큼만 접근 가능 하게 만들고
나머지 4, 5번째는 접근이 안되게 만들 뿐 내부에 데이터는 남아 있다.
평소에는 생각해보지 못하고 그냥 사용했었지만
이렇게 하나하나 분석을 하고 나니 더욱
벡터와 친해진 느낌이다.
'공부 > c++(c, STL)' 카테고리의 다른 글
| cout 출력 컨트롤 - fixed, scientific, hexfloat, defaultfloat (0) | 2016.10.05 |
|---|---|
| 퀵정렬(quick sort) (0) | 2016.08.02 |
| [STL]벡터(vector)의 메모리 재할당에 대해 (0) | 2016.07.18 |
| [코딩문제]n번째 피보나치 나머지 구하기 - 2 (0) | 2016.07.11 |
| [코딩문제]n번째 피보나치 나머지 구하기 - 1 (0) | 2016.07.10 |
[STL]벡터(vector)의 메모리 재할당에 대해
#include <iostream>
#include <vector>
//벡터 출력 함수
void Print(std::vector<int>& myvector)
{
std::vector<int>::iterator it;
std::cout << "myvector contains:";
for (it = myvector.begin(); it < myvector.end(); it++)
{
std::cout << ' ' << *it;
}
std::cout << '\n';
}
void main()
{
std::vector<int> myvector(3, 100); // size : 3, capacity : 3 , 맨처음 메모리 할당
std::vector<int>::iterator it;
Print(myvector); //myvector contains: 100 100 100
it = myvector.begin();
it = myvector.insert(it, 200); // size : 4, capacity : 4 , 새로운 메모리 공간에 전부 재 할당
Print(myvector); //myvector contains: 200 100 100 100
it = myvector.insert(it, 1, 300); // size : 5, capacity : 6 , 새로운 메모리 공간에 전부 재 할당
Print(myvector); //myvector contains: 300 200 100 100 100
it = myvector.insert(it, 1, 302); // size : 6, capacity : 6
Print(myvector); //myvector contains: 302 300 200 100 100 100
it = myvector.insert(it, 1, 303); // size : 7, capacity : 9 , 새로운 메모리 공간에 전부 재 할당
Print(myvector); //myvector contains: 303 302 300 200 100 100 100
it = myvector.insert(it, 1, 304); // size : 8, capacity : 9
Print(myvector); //myvector contains: 304 303 302 300 200 100 100 100
it = myvector.insert(it, 1, 305); // size : 9, capacity : 9
Print(myvector); //myvector contains: 305 304 303 302 300 200 100 100 100
it = myvector.insert(it, 1, 306); // size : 10, capacity : 13 , 새로운 메모리 공간에 전부 재 할당
Print(myvector); //myvector contains: 306 305 304 303 302 300 200 100 100 100
it = myvector.begin(); //이터레이터 변수 다시 시작지점으로 초기화
std::vector<int> anothervector(2, 400); // 다른 벡터
myvector.insert(it + 2, anothervector.begin(), anothervector.end()); // size : 12, capacity : 13
Print(myvector); //myvector contains: 306 305 400 400 304 303 302 300 200 100 100 100
int myarray[] = { 501, 502, 503 }; // size : 15, capacity : 19 , 새로운 메모리 공간에 전부 재 할당
myvector.insert(myvector.begin(), myarray, myarray + 3);
Print(myvector); //myvector contains: 501 502 503 306 305 400 400 304 303 302 300 200 100 100 100
myvector.pop_back(); // size : 14, capacity : 19 , 동일한 메모리 공간, 뒤에 것만 삭제, 반환값 없음
Print(myvector); //myvector contains: 501 502 503 306 305 400 400 304 303 302 300 200 100 100
myvector.reserve(5); // size : 14, capacity : 19 , 이전 capacity보다 같거나 작으면 동작하지 않음
Print(myvector); //myvector contains: 501 502 503 306 305 400 400 304 303 302 300 200 100 100
myvector.reserve(20); // size : 14, capacity : 20 , 새로운 메모리 공간 전부 재 할당
Print(myvector); //myvector contains: 501 502 503 306 305 400 400 304 303 302 300 200 100 100
myvector.resize(5); // size : 5, capacity : 20 , 동일한 메모리 공간, 사이즈 외에 것은 삭제
Print(myvector); //myvector contains: 501 502 503 306 305
myvector.shrink_to_fit(); // size : 5, capacity : 5 , 새로운 메모리 공간 전부 재 할당, 벡터 용량(capacity)을 크기(size)에 맞춤. c++11에 추가
Print(myvector); //myvector contains: 501 502 503 306 305
getchar();
}
c++ 에서 class나 데이터를 한 군데 모아 사용하는데에
가장 잘 사용했던 것이 vector였는데
이전 까지는 내부 메모리를 무시하고 사용했었다.
그래서 단편화 현상 유발이나
여러 다른 문제들을 야기 할 수 있다는 것을 간과했다.
하지만 위와같이 테스트해본 결과 메모리 처리가
다른 STL들과는 다른 점이 있어서
정리를 해두려고 한다.
벡터는 size와 capacity가 별도로 있다.
capacity는 벡터에 허용된 용량을 나타내고
size는 그 용량 내에 차지하고 있는 크기를 나타낸다.
테스트 결과 벡터에서는 capacity가 바뀌는 상황이 되면
메모리 재할당이 이루어 지는 것을 발견 할 수 있었다.
벡터 내에서는 data들이 일렬로 배열처럼 들어 있는데
일렬로 원하는 용량이 들어 갈 수 있는 공간을 찾아서
메모리와 data들이 재 할당 되는 것이다.
기존의 공간은 이제 비게 되고 다른 곳에서 사용가능해진다.
현재공간에서 size 외에 남은 용량은 다른 곳에서 사용하지 못한다.
용량을 함수로 늘리거나 줄이는거 외에
insert나 push_back으로 추가 삽입이 이루어 질때
capacity를 넘기게 되면 자동으로 메모리 재할당이 이루어 진다.
하지만 1씩 증가되는 것이 아니라 현재 capacity의 1.5배로 늘어나는 것을 확인했다.
capacity 변화 순서 : 3 -> 4(4.5지만 소수 버림) -> 6 -> 9 -> 13(13.5지만 소수 버림) -> 19(19.5지만 소수 버림)
벡터는 리스트보다 데이터 검색이 빠르다.
하지만 추가 삭제가 빈번하여
메모리 재할당이 자주 일어나면 성능이 낮아질 수 밖에 없다.
그만큼 단편화도 자주 일어날 가능성이 크다.
벡터(vector)의 좋은 사용법은
추가 삭제가 자주 일어나지 않아야 하고
미리 reserve로 최대 용량을 잡아주거나
resize로 원하는 만큼만 생성해 그 안에서 컨트롤 하는 것이다.
최대 용량은 단편화를 낮추기 위해 2의 배수가 좋을 것 같다고 생각한다.
'공부 > c++(c, STL)' 카테고리의 다른 글
| 퀵정렬(quick sort) (0) | 2016.08.02 |
|---|---|
| [STL]벡터(vector) 심화 - erase(), resize()로 인한 원소 처리 (0) | 2016.07.19 |
| [코딩문제]n번째 피보나치 나머지 구하기 - 2 (0) | 2016.07.11 |
| [코딩문제]n번째 피보나치 나머지 구하기 - 1 (0) | 2016.07.10 |
| Swap (베타적 OR - XOR 사용) (0) | 2016.06.24 |
[코딩문제]n번째 피보나치 나머지 구하기 - 2
#include <iostream>
using namespace std;
/*
피보나치 수열이란,
첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때,
이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다.
예) 0, 1, 1, 2, 3, 5, 8, 13
피보나치 수열의 n번째 수를 4,294,967,291으로 나누었을 때의
나머지를 출력하는 프로그램을 작성하시오.
정수 n이 입력으로 주어진다. (1 <= n <= 10^100000)
*/
#define MAXNUM 4294967291 //unsigned int 최대인 4294967295 보다 4 작음
unsigned int first = 0;
unsigned int second = 1;
int fibonacciCount = 0; //숫자 1, 2, 그외 체크용 카운트
//피보나치 계산 함수
unsigned int Fibonacci()
{
fibonacciCount++;
//cout << fibonacciCount << "번째";
if (fibonacciCount == 1) return first;
else if (fibonacciCount == 2) return second;
else if (fibonacciCount > 2)
{
fibonacciCount--; //카운트를 3이상 늘릴 필요는 없다
unsigned int temp = 0;
temp = first;
first = second;
if (MAXNUM - second < temp)
{
second = temp - (MAXNUM - second);
}
else
{
second += temp;
}
return second;
}
}
//0 체크 함수
bool NumIsZero(char* numChar, int size)
{
int count = 0;
for (int i = 0; i < size; i++)
{
if (*(numChar + i) == '0')
{
count++;
}
else
{
break;
}
}
if (count == size)
{
return true;
}
else
{
return false;
}
}
//숫자 -1 시키는 함수
void NumMinus(char* numChar, int size)
{
int idx = size - 1;
while (!NumIsZero(numChar, size)) //숫자가 0이 아니라면
{
if (*(numChar + idx) != '0') //자릿수가 0이 아니라면
{
*(numChar + idx) = *(numChar + idx) - 1; //1 빼주고 나옴
break;
}
else
{
*(numChar + idx) = '9'; //자릭수가 0이면 9로 바꾸어 주고
idx--; //다음 자릿수를 찾기로 함
}
}
}
void main()
{
char n[256]; //숫자를 넣을 char 배열 - 높은 숫자를 하기 위해선 자리수만큼 더 늘려야 한다
cin >> n; //입력
char* charTemp = n;
while (*charTemp != '\0')
{
charTemp++;
}
int charSize = charTemp - n; //들어온 수의 사이즈
while (!NumIsZero(n, charSize))
{
cout << n << endl; //진행도를 알기 위한 출력
NumMinus(n, charSize);
Fibonacci();
}
cout << endl << second << endl;
getchar();
getchar();
}
어제 했었던 문제와 같은 문제이다.
하지만 어제 무시했었던 10^100000을 처리하기 위해
char배열로 n값을 받고 char배열에 있는 값을 변환하여 처리하도록 하였다.
메모리 공간을 256이 아니라 더 많이 늘리면 자료형의 최대값(맥스값)보다 더 큰 값도 구하는 것이 가능하다.
이 코딩에는 큰 문제가 하나 발생하는데
엄청 느리다
숫자를 char배열로 하나하나 컨트롤 하니 느리다곤 생각하고 있었지만
느려도 너무 느리다.
1000000000000000(1천조)를 처리하는데 대략 10개월 정도의 시간이 걸릴것 같다.
이런 프로그램을 짜서는 안되겠지만
그래도 짤려면 이렇게라도 짤 수 있단걸 보여주기 위해 해보았다.
문제 출처 : 코딩도장
코딩 출처 : 내 머리, 내 손
'공부 > c++(c, STL)' 카테고리의 다른 글
| [STL]벡터(vector) 심화 - erase(), resize()로 인한 원소 처리 (0) | 2016.07.19 |
|---|---|
| [STL]벡터(vector)의 메모리 재할당에 대해 (0) | 2016.07.18 |
| [코딩문제]n번째 피보나치 나머지 구하기 - 1 (0) | 2016.07.10 |
| Swap (베타적 OR - XOR 사용) (0) | 2016.06.24 |
| [코딩문제]계단 오르기 - 3 계단 (0) | 2016.06.23 |
[코딩문제]n번째 피보나치 나머지 구하기 - 1
#include <iostream>
using namespace std;
/*
피보나치 수열이란,
첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때,
이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다.
예) 0, 1, 1, 2, 3, 5, 8, 13
피보나치 수열의 n번째 수를 4,294,967,291으로 나누었을 때의
나머지를 출력하는 프로그램을 작성하시오.
정수 n이 입력으로 주어진다. (1 <= n <= 10^100000)
*/
#define MAXNUM 4294967291 //unsigned int 최대인 4294967295 보다 4 작음
unsigned int Fibonacci(unsigned long long n)
{
if (n > 2)
{
unsigned int first = 0;
unsigned int second = 1;
unsigned int temp = 0;
unsigned long long count = n - 2;
for (unsigned long long i = 0; i < count; i++)
{
temp = first;
first = second;
if (MAXNUM - second < temp)
{
second = temp - (MAXNUM - second);
}
else
{
second += temp;
}
}
return second;
}
else if (n == 2) return 1;
else return 0; //if (n <= 1)
}
void main()
{
unsigned long long n = 1000000000;
cout << Fibonacci(n) << endl;
getchar();
}
10^100000 까지 입력할 수 있는 방법을 무시하고
기본 자료형으로 최대치를 계산 할 수 있는 unsigned long long 을 사용하여 구하였다.
리턴될 수 있는 최대값는 unsigned int 보다 작기 때문에 unsigned int 을 사용하였다.
MAXNUM < temp + second 을 계산하여야 하나
temp + second을 해버리면 자료형 맥스 값을 넘어가므로
값 하나를 넘겨 MAXNUM - second < temp 로 조건을 주었다.
마차나지로 temp + second - MAXNUM 을 해야 하나
temp + second은 맥스 값을 넘기게 되므로
자료형 맥스 값을 안넘기기 위해
temp - (MAXNUM - second)로 처리하였다.
위처럼 자료형의 최대치(맥스값)를 넘기지 않게 컨트롤 하지 않고
무작정 더해버리면 원하지 않는 결과가 나와버린다.
커다란 숫자를 컨트롤 해야 할 경우에는
자료형의 최대값(맥스값)을 항상 고려하면서 코딩을 해야 한다.
문제 출처 : 코딩도장
코딩 출처 : 내 머리, 내 손
'공부 > c++(c, STL)' 카테고리의 다른 글
| [STL]벡터(vector)의 메모리 재할당에 대해 (0) | 2016.07.18 |
|---|---|
| [코딩문제]n번째 피보나치 나머지 구하기 - 2 (0) | 2016.07.11 |
| Swap (베타적 OR - XOR 사용) (0) | 2016.06.24 |
| [코딩문제]계단 오르기 - 3 계단 (0) | 2016.06.23 |
| [코딩문제]피보나치 수열 (0) | 2016.06.20 |
Camera Mirror(Reflect) - 거울(반사)
카메라를 별도로 달아서
백미러, 사이드 미러 같은 별도의 뷰 영역을 만들어 보자.
별도의 Camera Object와 Renderer Texture와 teuxture Material을 사용하여
하나의 display에서 여러 카메라를 보일수는 있지만
거울이라는 것은 좌우가 반전이 되어있어야 한다.
별도의 옵션을 찾지 못해 위와 같이 스크립트로 처리를 했다.
렌더 관련 이벤트 함수 호출 순서는
OnPreCull() -> OnPreRender() -> 오브젝트들 렌더 -> OnPostRender()
순이다.
camera.ResetProjectionMatrix(); 는 가이드를 보면
"projection이 노멀 카메라 파라미터들을 반사하도록 만들 때 사용한다."라고
되어있는데 함수 명대로 ProjectionMatrix를 Reset해주는 것이 아닐까 생각한다.
그 후 projectionMatrix의 scale을 x축으로 반전하도록 처리하고
GL.invertCulling = true; 를 하여 백페이스 컬링을 반전 시킨 것이다.
그리고 오브젝터 렌더가 끝나면
백페이스 컬링을 다시 원래 값으로 돌린다.
위처럼 카메라에 스크립트를 넣으면 거울 처럼 좌우가 반전된 영역을 얻을 수 있다.
'공부 > Unity' 카테고리의 다른 글
| 포트폴리오 잘하는 법 (0) | 2016.08.25 |
|---|---|
| NGUI 이미지 분류법 (0) | 2016.08.07 |
| There are 2 audio listeners in the scene 해결 방법 (0) | 2016.07.01 |
| MipMap(밉맵) - 이론 (0) | 2016.06.29 |
| Resources.Load<TextAsset> 가 null 일 때 (0) | 2016.06.22 |
There are 2 audio listeners in the scene 해결 방법
There are 2 audio listeners in the scene. Please ensure there is always exactly one audio listener in the scene.
위의 메세지가 Console에 계속 출력될 때에는
카메라를 뒤져보자.
씬 하나에는 Audio Listener가 하나 있어야 되는데
Camera Object를 추가하면
Audio Listener가 기본적으로 달려 있어서
Main Camera에 달린 Audio Listener와 겹치기 때문이다.
뒤에 추가한 Camera에서 Audio Listener를 찾아서
비활성화 하거나 Remove Component를 해주자
'공부 > Unity' 카테고리의 다른 글
| NGUI 이미지 분류법 (0) | 2016.08.07 |
|---|---|
| Camera Mirror(Reflect) - 거울(반사) (0) | 2016.07.04 |
| MipMap(밉맵) - 이론 (0) | 2016.06.29 |
| Resources.Load<TextAsset> 가 null 일 때 (0) | 2016.06.22 |
| NGUI 한글 입력 문제 - ime 버그 (0) | 2016.06.19 |
MipMap(밉맵) - 이론
밉맵(MipMap)이라고 불리는 맵핑(Mapping) 기법을 알게되었다.
DirectX를 할 땐 신경 쓰지 않았는데
유니티에서는 기본으로 되어있는 옵션이 있어서 알아보았다.
멀리 있는 사물이나 땅에 Texture를 씌운다고 생각을 해보자.
한 영역이 화면에서는 멀리 있어서 8 pixel 이내에 찍어야 하는데
그 영역에 들어갈 Texture가 256x256 짜리라면 이 것을 줄여
연산을 통해서 그 적은 pixel만큼 들어갈수 있게 평균을 낸 RGB값을 넣게 된다.
멀리 떨어져 있다면 그 영역의 수도 많아지게되고
연산이 많아 지는 것은 3D 에서의 큰 문제일 수 밖에 없다.
그래서 나온 방법이 미리 미리 작은 해상도의 Texture를 준비하는 것이다.(논리적이든 물리적이든)
Texture의 크기는 2의 배수로 하는 것이 최적이고
256x256이라면 128x128, 64x64, 32x32, 16x16, 8x8, 4x4, 2x2....와 같이
미리 적은 pixel의 Texture를 메모리에 넣어 놓고
나중에 연산을 할때 적절한 크기의 Texture를 꺼내 사용하는 것이다.
장점은 말그대로 런타임 시의 연산을 줄여 프레임이 떨어지는 것을 미리 방지 할 수 있다는 것이고
단점은 미리 Texture를 만들어넣기 때문에 메모리를 많이 사용한다는 것이다.
옛날에는 하드웨어 성능이 좋지 않아 메모리 문제도 생각을 많이 했지만
요즘은 모바일도 렘이 크기 때문에 MipMap을 사용하는 것이 3D게임에서는 기본이라 생각하면 된다.
2D는 오히려 버짐 현상이 나올 수 있으므로 MipMap을 사용 하지 않는 것이 좋다.
'공부 > Unity' 카테고리의 다른 글
| Camera Mirror(Reflect) - 거울(반사) (0) | 2016.07.04 |
|---|---|
| There are 2 audio listeners in the scene 해결 방법 (0) | 2016.07.01 |
| Resources.Load<TextAsset> 가 null 일 때 (0) | 2016.06.22 |
| NGUI 한글 입력 문제 - ime 버그 (0) | 2016.06.19 |
| 유니티에서의 싱글톤(Singleton) 적용 (2) (0) | 2016.06.17 |
Swap (베타적 OR - XOR 사용)
#include <iostream>
using namespace std;
void main()
{
unsigned short a = 0x1; // 0001
unsigned short b = 0x5; // 0101
cout << (a^b) << endl; // 4 = 0100
getchar();
}
컴퓨터 관련 전공이나 전산 쪽이면 XOR는 많이 봤을 것이다.
A |
B |
결과 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
A와 B의 입력이 있을 때 둘 중 하나만 1일 경우가 1이다 라는 것인데
이를 코드로 표현 할 일이 거의 없지만
두개의 변수의 값을 교환 할때 사용할 수 있단 걸 알게 되었다.
이전에는
temp = a;
a = b;
b = temp;
이런식으로 별도의 동일한 자료형의 더미를 만들어 Swap을 하였으나
아래와 같이 XOR을 3번 해주고 각각 변수 A, B, A 순으로 담아주면
더미 변수 없이도 서로 값이 바뀌는 것을 결과로서 볼 수 있다.
주석의 이진 수를 참고하여 아래의 코드를 봐보자.
#include <iostream>
using namespace std;
void main()
{
int a = 127; //1111 1111
int b = 59; //0111 1011
a = a ^ b; // a = 1000 0100
b = a ^ b; // b = 1111 1111
a = a ^ b; // a = 0111 1011
cout << a << endl;
cout << b << endl;
int c = 60817; //0000 0000 0000 0000 0000 1110 1101 1001 0001
int d = 201606; //0011 1011 0110 0100 0111 0001 0011 1000 0110
c = c ^ d; // c = 0011 1011 0110 0100 0111 1111 1110 0001 0111
d = c ^ d; // d = 0000 0000 0000 0000 0000 1110 1101 1001 0001
c = c ^ d; // c = 0011 1011 0110 0100 0111 0001 0011 1000 0110
cout << c << endl;
cout << d << endl;
getchar();
}
'공부 > c++(c, STL)' 카테고리의 다른 글
| [코딩문제]n번째 피보나치 나머지 구하기 - 2 (0) | 2016.07.11 |
|---|---|
| [코딩문제]n번째 피보나치 나머지 구하기 - 1 (0) | 2016.07.10 |
| [코딩문제]계단 오르기 - 3 계단 (0) | 2016.06.23 |
| [코딩문제]피보나치 수열 (0) | 2016.06.20 |
| [코딩문제]셀프 넘버(self-number) 풀이 (0) | 2016.06.18 |
[코딩문제]계단 오르기 - 3 계단
#include <iostream>
using namespace std;
/*
계단을 오르는 방법에는 여러가지가 있습니다.
한 계단씩만 올라가는 방법이 있고,
두 계단만 올라가는 방법이 있고 혹은
세 계단만 올라가는 방법이 있습니다.
계단의 수를 n이라 하고
한번에 올라갈 수 있는 계단의 수를 최대 세 계단이라고 했을 때
계단을 올라갈 수 있는 경우의 수를 구하시오.
*/
int Fibonacci(int n)
{
if (n == 1) return 1;
else if (n == 2) return 2;
else if (n == 3) return 4;
else if (n > 0)
{
int first = 1;
int second = 2;
int third = 4;
int temp = 0; //임시 변수
int count = n - 3; //반복을 돌릴 카운트
for (int i = 0; i < count; i++)
{
temp = first;
first = second;
second = third;
third += temp + first; //third = temp(first) + first(second) + third
}
return third;
}
else
{
return -1;
}
}
//메인함수
void main()
{
cout << Fibonacci(6) << endl;
getchar();
}
해설 :
이런건 노트에 적어가면서 풀어보면 규칙이 보입니다.
계단이 하나일 경우 (1) 계단 만 오를 수 있으니 경우의 수는 1 입니다.
두개일 경우 (1, 1)로 오르거나 (2) 계단 오를 수 있어서 경우의 수가 2입니다.
계단이 세 개일 경우 (1, 1, 1)로 오르거나 (1, 2) 로 오르거나 (2, 1)로 오르거나 (3) 계단 전부 오를 수 있으므로 경우의 수는 4개 입니다.
계단이 네 개일 경우 (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2), (1, 3), (3, 1) 의 경우로 경우의 수는 7 입니다.
감이 좋으신 분들은 여기에서 눈치를 챘을 수 있습니다.
잘보면 보이는 규칙이 있습니다.
저는 계단 다섯 개 까지 경우의 수를 써보고 규칙을 찾아냈습니다.
1로 시작 할경우 바로 전 계단의 경우의 수와 동일한 경우나 나타납니다.
2로 시작 할 경우 바로 전전 계단의 수에서의 경우의 수가 나오고
3로 시작 할 경우 바로 전전전 계단의 수에서의 경우의 수가 나오는 것이 보입니다.
네 계단 에서의 (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2), (1, 3), (3, 1) 을 보기 좋게 나열해보면
(1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 3)
(2, 1, 1), (2, 2)
(3, 1)
이고 첫 숫자들만 지워보면
(1, 1, 1), (1, 2), (2, 1), (3)
(1, 1), (2)
(1)
이렇게 되고 이는 각각 세 계단일 경우, 두 계단일 경우, 하나의 계단일 경우 와 동일 합니다.
즉 앞의 숫자 3개를 더하면서 진행되는 피보나치 수열을 짜면 문제는 해결 되는 것입니다.
이해가 잘 안되시는 분들은 다섯, 여섯 계단 일 경우도 노트에 적어 보시면 이해가 되실 것 같습니다.
문제 출처 : 코딩도장(http://codingdojang.com/)
코딩 출처 : 내 머리, 내 손
'공부 > c++(c, STL)' 카테고리의 다른 글
| [코딩문제]n번째 피보나치 나머지 구하기 - 1 (0) | 2016.07.10 |
|---|---|
| Swap (베타적 OR - XOR 사용) (0) | 2016.06.24 |
| [코딩문제]피보나치 수열 (0) | 2016.06.20 |
| [코딩문제]셀프 넘버(self-number) 풀이 (0) | 2016.06.18 |
| [코딩문제]문자열 거꾸로 출력 (0) | 2016.06.16 |
Resources.Load<TextAsset> 가 null 일 때
위와 같은 사항을 발견하였다.
Resources.Load 가 null 이면 일단 Project 탭에서
어떻게 나오는지 확인해보도록 하자
'공부 > Unity' 카테고리의 다른 글
| There are 2 audio listeners in the scene 해결 방법 (0) | 2016.07.01 |
|---|---|
| MipMap(밉맵) - 이론 (0) | 2016.06.29 |
| NGUI 한글 입력 문제 - ime 버그 (0) | 2016.06.19 |
| 유니티에서의 싱글톤(Singleton) 적용 (2) (0) | 2016.06.17 |
| 유니티에서의 싱글톤(Singleton) 적용 (0) | 2016.06.17 |
