기술 면접 책관련(배열, 문자열 / 재귀호출)

문자열은 문자의 배열일 뿐이다(보통은 읽기 전용)

배열 : 메모리 블록에 연속적으로 나열된 같은 유형의 변수 모음..

인덱스 접근으로 검색이 O(1)이긴하지만..최악의 배열이면 배열도 검색이 O(n)이 된다.

특히 문자 배열이 있을떄 W를 찾아내라 ? 이런건 O(n)임

배열 중간의 데이터 삭제나 추가는 느려진다는 단점이 있다. 이건 o(n) 이다

대부분의 동적배열은 내부적으로 정적 배열을 사용하는데..

동적 배열의 크기를 바꿀때는 보통 적당한 크기의 새로운 배열을 만들고 모든 원소를 복사하고 기존 배열의 메모리 할당을 해제해야하는 식이다.

꽤 느린 연산이다.

포인터 상수 : char* const charPtr 이런식이다. 메모리상의 다른 위치를 가리키도록 변경시킬 수 없음..값을 변경가능..

상수 포인터 : const char* charPtr 이런식이다. 메모리상 다른 위치를 가리키도록 가능하지만, 메모리 위치에 있는 값을 바꿀 수 없다.

* 해석할때 상수의 위치를 자세히 볼것. 포인터 뒤에 상수냐, 포인터보다 앞에 상수 단어가 나오느냐..이거에 따라 의미가 틀려짐..

char* const 오호..

문자열...

char는 무조건 한바이트..

UTF - 8 : 네트워크를 통해서 전송되는 텍스트나 파일에 저장된 테스트 용도로 많이 쓰인다는데.. 최대 네 개까지의 8비트짜리 char를 써서

모든 유니코드 코드 포인트를 인코딩.. Ascii코드는 모두 한 바이트로 표현된다는 장점..

문자열의 마지막은 '\0'으로 표현되는 널 문자로 표시된다.

배열과 문자열 문제중에는 더 효율적인 풀이를 위해 임시 자료구조를 만들어야 할때가 많다.

1. 반복되지 않은 첫번째 문자열 찾기

이건 해쉬를 이용해서 하네..배열을 이용한다면..음...문자열을 정수값으로 변경해서 그걸..키 값으로..변형해서..인덱스에..

저장한다라..0번이 A가 들어갈 수 있게..A - z 뭐 이런식으로 배열을 만들고...문자에 A - 문자값..뭐 이런식..??

char* str = "ACDbc";

char a = str[0];

a -= 'z';

if (a < 0)

a *= -1;

//이게 사이즈가 될테고..

cout << int(a) << endl;

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

{

char temp = str[i];

temp = temp - 'A';

cout << int(temp) << endl;

}

문자열을 단어단위로 뒤집어서 출력하는것..중요한건

어딘가에 반드시 저장을 하면서 가야하는것이고..빈칸이라는것..그리고 어쩔수 없이 while안에 while이 들어가는 것들..

위치를 특별히 보관해야하는 변수들이 필요하다..마지막에 다 끝나고 널문자 넣는것도 잊으면 안되고

이렇게 하면 일반적으로 푸는것이고..우아하게는..

혹시나 임시버퍼를 없앤다면..우선은 그냥 순서들을 뒤에서 넣어버리고..        

어쨌든 단어들이 뒤집어져 있으나 문자열은 완벽히 뒤집어져있다..

문자열을 숫자로 바꾸거나 숫자를 문자열로 바꾸는 방법.. '0' 이 아스키 코드를 이용하는것에 대해서 잊지말아야함

이떄 음수에 대한처리가..문자열 -> 숫자냐 / 숫자 -> 문자열이냐에 따라 다르게 된다.

문자열 -> 숫자인 경우..음수라는 - 표시가 있다면 bool 형으로 잠시 담아두고 처리

숫자 -> 문자열인 경우에는 음수일 경우에는 양수로 만들어놓고 음수라는 표시해두고 나중에 -1 곱해주는게 낫다.

숫자를 문자열로 바꾸려면..해당 숫자의 자릿수별로 값을 뽑아야 하는데.. 예를들어 732라면..

왼쪽부터 오른쪽 순으로 간다고하면..이건 첫번째 자리에 대해서 찾고 확인을 해야하는데..이게 여간 어려운게 아니다..복잡하고..

숫자가 엄청 크다면? 시작하기도전에 이 자릿수 찾는것 부터 해야겠지..뭐 찾는거야.. 해당 자리수로 나눠보고 0이 나오면 그 자릿수는 없는거겠지..

뭐 찾는거야 어렵진 않으나 계산을 한번더 해야하는것이 문제지..그 뒤에 찾았다고 치면..그 값이 무엇인지 확인하려면..

일단 자릿수로 나누고..그 값을 보존해두고 그 자릿수랑 나온수랑 곱해서 나온수를 기존의 732랑 빼주면.. 732 - 700 = 32 그럼 32가 나오겠지요..

7은 보존되어 있고..이런식으로 나눌수 있긴 한데..해당 자릿수랑 같이 수를 저장해야하는 불편함이 있긴하네..

어쨌든 반대로 오른쪽에서 왼쪽으로 확인해보자..

아하 그러니까..이렇게 하면된다..

732 숫자를 예로 2를 구하려면..그냥 일단 % 연산을 한다 왜냐면 처음이니까..

그 다음에 / 10을 해주고 그 값에 % 연산하고...

/ 10해주고 나온값을 다시 / 10 해주고 % 연산을 하고..

이걸 / 10 == 0 값이 나올떄까지 하면..되는데 가장 큰 단점은 ! 숫자가 역으로 나온다는것이다!!

그탓에 모든 자리 숫자를 다 알아내기 전까지 문자열로 넣을 수가 없다.

숫자 자체를 거꾸로 저장하고 나중에 뒤집에

---

재귀호출이란 유사한 하위 작업 형태로 정의할 수 있는 작업을 처리하는데 유용하다.

(유사한 하위작업!!)

기본케이스 : 재귀호출을 하다보면 자신을 호출하지 않고도 처리할 수 있는 하위 작업이 나옴..이렇게 루틴에서 재귀 호출을 하지 않아도 되는 케이스

* 그냥 종료조건이라고 해야할가..? 그게 더 맞을듯..

* 언젠가는 스택 오버 플로우를 만나게 될테니까..

재귀 케이스 : 루틴에서 자신을 호출하여 하위 작업을 수행하는 케이스

팩토리얼 한번볼까

n!  = n * (n - 1)! 형식으로 되어있다.

int factorial(int n)

{

if( n > 1)

{

return n * factorial(n - 1);    //재귀 케이스

}

else

return 1;   //기본케이스

}

}

반복문으로 바꾸면

int factorial(int n)

{

int i, val  = 1;

for(i = n; i > 1; --i)

val *= i;

return val;

}

여기서 중요한건 다른게 아니라..val이전값의 곱셈을 보존하는곳이 필요하거다.

이건 내가 구현한 반복문

int factorial2(int n)

{

int val = 1;

for (int i = 1; i <= n; ++i)

{

val = val * i;

}

return val;

}

여기서 꼬리 재귀 호출이라는게 나오는데..이건 반복문으로 만들 수 있당께.

* 재귀호출에서 반환한 값 자체가 바로 반환되면 그 함수가 꼬리 재귀 호출 함수라 한다.

복잡한 재귀 호출 루틴의 경우에는 초기화를 위한 래퍼함수를 별도로 만드는 것이 좋다.

재귀호출이 매우 강력한 테크닉이긴 하지만, 언제나 가장 좋은 접근법이라고는 할 수 없다.

가장 효율적인 접근법인 경우는 거의 없다. 

실제 계산보다 함수 호출에 따른 오버헤드가 더 큰 경우가 있음..그래서 반복문을 사용하는게 더 나을 수도 있음..

위의 팩토리얼 반복문 변경처럼 재귀호출은 일반적으로 지역변수의 현재 값을 보존했다가 재귀 호출에 의해 수행되는

하위 작업이 완료되었을때 다시 가져와서 쓰기 위해 쓰인다.

스택과 또 밀접한 관계도 있다고 하던데..근데 훨씬 복잡하다 ..그리고 스택을 쓰는 오버헤드가 함수 오버헤드보다 훨씬 적은게 아닌이상..

이진검색 : 재귀적인 구현에 적합하다.

검색시간은 logn인데..이건 정렬이 된 상태에서..만약에 정렬이 안되었다면 n logn 이 되버린다..먼저 정렬을 해야하니까..

문자열 순열이라...