면접 필기 예상문제

문자열 뒤집기

예) "abcdef abc" -> "abc abcdef" 로 출력

void ReverseString(char* str)

{

int iLength = strlen(str);

char* tempStr = new char[iLength + 1];

int iReadStart = 0;

int iReadEnd = 0;

int iWriteIndex = 0;

int iCurIndex = 0;

iCurIndex = iLength - 1;

iReadStart = iCurIndex;

iReadEnd = iCurIndex;

while (iCurIndex >= 0)

{

while (str[iCurIndex] != ' '

&& iCurIndex >= 0)

--iCurIndex;

iReadStart = iCurIndex + 1;

while (iReadStart <= iReadEnd)

{

tempStr[iWriteIndex] = str[iReadStart];

++iReadStart;

++iWriteIndex;

}

if (iCurIndex < 0)

{

tempStr[iWriteIndex] = '\0';

break;

}

tempStr[iWriteIndex] = str[iCurIndex];

--iCurIndex;

++iWriteIndex;

iReadEnd = iCurIndex;

}

  strcpy_s(str, iLength + 1, tempStr);

delete[] tempStr;

}

문자열 숫자를 숫자로 바꾸기

예) char* str = "123" -> int a = 123으로 바꾸기

int strToInt(char* str)

{

int i = 0;

int num = 0;

bool isMinus = false;

if (str[0] == '-')

{

isMinus = true;

i = 1;

}

int index = strlen(str) - 1;

int itemp = 0;

int iValue = 1;

itemp = str[index] - '0';

num = itemp;

--index;

while (i <= index)

{

itemp = str[index] - '0';

iValue *= 10;

itemp *= iValue;

num += itemp;

--index;

}

return num;

}

//짧은버전

int strToInt(char* str)

{

int i = 0;

int num = 0;

bool isNeg = false;

int len = strlen(str);

while (i < len)

{

num *= 10;

num += str[i] - '0';

++i;

}

return num;

}

숫자에서 문자열로 변경하기

int a = 123; -> char* str = "123"

char* IntToStr(int num)

{

int iValue = num;

int index = 0;

char* str = new char[10];

while (iValue)

{

int temp = iValue % 10;

str[index] = temp + '0';

++index;

iValue /= 10;

}

str[index] = '\0';

//아래부터는 문자열을 뒤집기

int iLength = strlen(str) - 1;

index = 0;

while (index <= iLength)

{

char temp = str[index];

str[index] = str[iLength];

str[iLength] = temp;

++index;

--iLength;

}

return str;

}

이진검색

정렬된 int arr[10] = 0 ~ 9

int Search(int* arr, int FindValue, int upper, int lower)

{

int center;

int range;

range = upper - lower;

if (range >= 0)

{

center = (range / 2) + lower;

if (arr[center] == FindValue)

return center;

else if (arr[center] < FindValue)

return Search(arr, FindValue, upper, center + 1);

else if (arr[center] > FindValue)

return Search(arr, FindValue, center - 1, lower);

}

}

int BinarySearch(int* arr, int iFindValue)

{

return Search(arr, iFindValue, 9, 0);

}

//반복문으로 만든것.

int BinaryFor(int* arr, int FindValue, int upper, int lower)

{

int center;

int range;

int iUpper = upper;

int iLower = lower;

while (true)

{

range = iUpper - iLower;

center = (range / 2) + iLower;

if (range == 0)

return center;

if (arr[center] == FindValue)

return center;

else if (arr[center] < FindValue)

{

iLower = center + 1;

}

else if (arr[center] > FindValue)

{

iUpper = center - 1;

}

}

return -1;

}

---

알고리즘을 선택할 때 고려해야할 점

1. 정렬할 데이터의 양

2. 데이터와 메모리

  - 대부분 정렬 알고리즘은 처리할 데이터가 메모리에 들어있을 때만 효율적으로 돌아간다. 데이터가 너무 많아서 메모리에 다 올릴 수 없으면

조금씩 잘라서 정렬을 하고 잘라진 각 조각을 합쳐서 전체 정렬된 데이터 모음을 만들어야 할 수 있다.

3. 데이터가 정렬된 정도

4. 필요한 추가 메모리의 양

5. 상대 위치 보존 여부

알고리즘 중에서 최악 조건의 실행 시간이 nlogn보다 빠른것은 없다.

선택정렬 : 최선 평균 최악 모두 O(n^2) 이다 

장점이라고 해봐야..원소를 맞바꾸는 횟수가 최대 n - 1번이라는 점. 데이터 원소를 움직이는 게 비교 작업에 비해 비싼 경우에는 선택 정렬이

다른 알고리즘 보다 빠를 수 있다.  불안정함.

삽입정렬 : 이미 리스트가 정렬 되어 있다면 O(n)이다. 즉, 이미 정렬된 리스트에 새 원소를 추가할 때는 삽입 정렬이 매우 효율적이다.

그러나 평균 및 최악은 O(n^2)이기 떄문에 무작위로 정렬된 많은 데이터를 처리하기에는 좋은 알고리즘이라고 할 수 없다.

안정적이며, 소량의 데이터 집합을 처리할때 강점을 발휘한다.

퀵 정렬 : 어떤 피벗값을 선택하느냐에 따라 성능이 결정된다. 가장 이상적인 것은 절반씩 쪼개는 값이다. 

최선의 경우는 재귀호출이 이뤄질 때마다 부분 리스트의 크기가 절반씩 줄어들고 부분 리스트의 크기가 1이 되면 재귀호출이 끝난다.

즉, 각  원소에 대해 상수 시간 연산을 하는 횟수는 n 을 1이 나올때까지 반복해서 2로 나누는 횟수. 즉, log(n)이다 n개의 원소에 대해

log(n)번씩 연산을 수행하므로 최선의 경우도 nlog(n)이다.

하지만 최악이라면 O(n^2)이다. 

그리고 불안정한 정렬이다.

합치기 정렬 : 데이터 집합을 둘 이상의 부분집합으로 가르고, 각 부분집합을 정렬한 다음에 다시 정렬된 형태로 합치는 정렬 방식이다.

데이터 집합이 메모리에 한번에 올리기에 너무 너무 클 떄 쓰기 좋은 방법이다. 보통은 큰 파일에 있는 내용을 여러 개의 더 작은 파일로 나눈다.

각각의 작은 파일을 메모리로 읽어들여서 적당한 알고리즘으로 정렬한 다음 다시 파일로 저장한다. 그리고 정렬된 파일을 입력 받아서 바로 최종

출력파일에 결과를 기록하는 식으로 합치기 작업을 처리한다.

최고, 평균, 최악 실행시간은 모두 nlogn이다. 정렬시간의 상한을 철저하게 지켜야할 때 매우 좋다. 하지만 추가로 O(n)의 메모리가 필요하다.

안정적임..

const int ITEMSIZE = 6;

int result[ITEMSIZE];

void Sort(int* arr, int left, int mid, int right)

{

int i, j, k, m;

int arrayTest[ITEMSIZE];

i = left;

j = mid + 1;

k = left;

while (i <= mid && j <= right)

{

if (arr[i] < arr[j])

{

arrayTest[k] = arr[i];

++i;

}

else if (arr[i] > arr[j])

{

arrayTest[k] = arr[j];

++j;

}

++k;

}

if (i > mid)

{

for (m = j; m <= right; ++m)

{

arrayTest[k] = arr[m];

++k;

}

}

else

{

for (m = i; m <= mid; ++m)

{

arrayTest[k] = arr[m];

++k;

}

}

for (int i = left; i <= right; ++i)

{

arr[i] = arrayTest[i];

}

}

질문 : 정렬할 때 가장 적합한 알고리즘은 무엇인가요?

무조건 퀵 정렬이 아니다.

1. 어떤 데이터인가요? 데이터가 이미 정렬이 된건가? 보통 어느 정도의 크기인가? 

2. 정렬 조건이 어떻게 되는가요? 최선, 최악, 평균 중 어느 상황에 맞춰서 최적화해야 하는가

3. 어떤 시스템인가요 ? 정렬해야 하는 데이터의 최대치가 사용 가능한 메모리 크기랑 비교해서 더 큰가 아니면 더 작은가?

질문 : 마스터 디렉터리 서버에서는 여러 부서별 디렉터리 서버로부터 사용자 ID를 기준으로 정렬된 계정 목록을 수신한다.

이 서버에서 모든 계정을 사용자 ID를 기준으로 정렬된 상태로 합쳐두는 마스터 목록을 만들 떄 가장 좋은 접근법은?

가장 단순한 방법은 모든 하위 목록을 쭉 이어 붙이고 퀵 정렬 같은 일반적인 정렬 알고리즘으로 정렬하는 방법이다.

실행시간은 nlogn이 되겠지.

더 효율적인 방법은 없나?

우선 각각의 하위 목록이 정렬이 되어 있다는것을 알 수 있다. 이걸 어떻게 써먹을까..합치기 정렬되나?

지금 이 문제의 상황은 재귀 호출을 통해 각각의 하위 목록이 정렬되어 있는 합치기 정렬의 마지막 단계와 비슷하네..

그래서 합치기 정렬이 더 좋을 수도..근데 추가적 공간이 없으면 어쨌든 퀵정렬이..그냥 낫다..n보다 nlogn이 엄청 느린건 아닐테니..

질문 : 어떤 제조공장을 모니터하는 시스템에서 품질 관리를 할때 불량이 난 모든 항목의 일련번호를 목록으로 저장해 둔다고 하자.

근무 시간 동안 공장이 가동되는 중에는 새 일련번호를 목록 맨 뒤에 덧 붙인다. 그리고 매일밤 배치 작업을 돌려서 목록을 다시 정렬한다.

이떄 쓸 수 있는 가장 좋은 정렬알고리즘은?

전날 정돈한 일련번호까지는 이미 정렬이 되어 있다. 그날 새로 추가된 일련번호만 정렬이 안되어있다. 

정리해보자면 이 문제는 소수의 정렬되지 않은 항목들을 커다란 정렬된 목록에 추가하는 문제라고 할 수 있다.

이런 문제에는 삽입 정렬이 제격이다. 

삽입 정렬이 최선의 속도인 O(n)이 나오는 상황과 비슷해 보인다. 최악이 O(n^2)이긴 한데 일련번호 양이 적으면 가능하다.

하지만 갑자기 어느날 엄청나게 일련번호가 쌓이면? 속도가 최악에 가깝게 될텐데..가끔 정렬하는데 시간이 오래 걸려도 상관없다면

선택정렬이 최선이다.

만약 최악 성능은 안된다고 해보자..

그럼 합치기 정렬이 나을듯..어차피 두 목록을 합쳐야 한다면..

질문 : 여러 종류의 데이터를 정렬해야 하는데 그 데이터에 대해 아는게 거의 없다. 데이터 집합이 크진 않아서 메모리에 전부 들어갈 수 있지만

각각의 크기는 많이 다를 수 있다. 어떤 정렬 알고리즘을 써야 할까?

정렬할 데이터에 대해서 아는게 거의 없는 상황은 매우 흔하게 생기는데..

이런 경우에는 일반적인 속도만 생각해서 정렬할 순 없다. 

결국 아까 언급한

1. 어떤 데이터인가요? 데이터가 이미 정렬이 된건가? 보통 어느 정도의 크기인가? 

2. 정렬 조건이 어떻게 되는가요? 최선, 최악, 평균 중 어느 상황에 맞춰서 최적화해야 하는가

3. 어떤 시스템인가요 ? 정렬해야 하는 데이터의 최대치가 사용 가능한 메모리 크기랑 비교해서 더 큰가 아니면 더 작은가?

을 비교해서 선택해야한다.

선택 정렬이 불안정한 이유?

5(1), 3 5(2), 2 를 정렬하게 된다면 2, 3 5(2), 5(1) 로 만들어 진다.

두 개의 같은 키를 가지는 값의 순서가 뒤집혔다. 아무래도 키를 서로 맞바꾸기 때문에 불안정해지는 것으로 보인다. 

정렬되지 않은 키가 정렬되고 있는 키가 있던 자리로 맞바뀌어 들어가면서 그 정렬되지 않은 키의 다른 정렬되지 않은 키들에 대한 상대적인

위치 정보를 잃어버리고 말기 때문이다. 이런 맞바꾸기 작업이 반복되기 때문에 정렬이 진행되면서 정렬되지 않은 키의 순서가 계속 뒤바뀐다.

결국 맞바꾸는 과정을 없애면 된다.  삽입 삭제과정을 하면된다. 먼저 있던 자료를 임시보관하고 그 자료를 삭제하고 삽입하면된다.

물론 배열이 다 움직인다. 이동연산만 n^2이 된다 어차피 결국은 n^2인데 더 느려진건 사실..그래서 연결리스트로하면 이동연산이 n으로 되서

그나마 조금 나은 n^2이 된다.

---

멀티프로세싱, 멀티프로그래밍, 멀티태스킹, 멀티 스레드 용어 구분

더보기

쓰레드는 애플리케이션의 실행에 있어서 가장 기본적인 단위이다. 실행중인 애플리케이션은 최소 하나의 쓰레드로 구성된다.

각 스레드마다 별도의 스택이 있다. 그라나 파일 핸들이나 메모리 같은 자원을 공유한다.(코드, 힙, 데이터 메모리) 그래서

공유 자원에 대한 접근을 제대로 제어하지 못하면 문제가 생긴다.

선점형 멀티 스레드에 대해 아는대로 설명해 보시요! 

Windows의 스레드 스케줄 방식으로 선점형 스레드 스케줄러를 가지고 있다.
즉, 더 높은 우선순위(IRQL)의 스레드가 나타나면 CPU 사용권을 빼끼는 것이다.

그렇다. 선점형이란 단어때문에 핵갈렸던 것이다. 스레드가 CPU를 선점했던것이 아니라

다른 스레드에 의해 선점 당할수 있다는 의미에서 선점형 스레드 스케줄링인것 같다.

: 현재 CPU를 사용하고 있는 스레드의 실행으 ㄹ언제라도 멈추게 하고 다른 스레드에게 CPU의 사용권을 넘길 수 있음을 이야기한다.

데드락

참조사이트1

참조사이트2

  - 두 스레드가 서로 상대방이 쥐고 있는 자물쇠(진입 키 같은것)가 풀리기만을 기다리면서 서로 가로막고 있는 상황이 벌어질 수 있다.

이걸 데드락이라고 하는데..

  - 두 개의 서로 다른 스레드에서 서로 상대방이 필요로 하는 자원에 대한 락을 가지고 있는 경우에 일어난다. 이런 경우에서는 두 스레드 모두 더 이상 실행이 될 수 없기 때문에 꼼짝할 수 없는 상태가 되기 때문에 데드락이라는 이름을 붙였다.

바쁜대기??

질문 : 바쁜대기란 용어는 뭐지? 바쁜대기를 피할 수 있는 방법

작업을 완료하기 위해 다른 스레드를 파생시켜야만 하는 스레드가 있다고 해보자. 첫 번째 스레드에서는 두 번째 스레드가 작업을 마칠 때까지 기다려야 하고

두번째 스레드는 자기가 할일을 마치고 나면 바로 종료가 된다고 하자. 가장 간단한 접근법은 첫번째 스레드에서 두번째 스레드가 종료될떄까지

기다리도록 하는것인데..이렇게 대기중인 스레드가 여전히 활성 상태긴 하지만 실제로 아무일도 안하는것을 바쁜대기라고 한다.

첫번째 스레드에서 두번째 스레드가 끝날 때까지 대기하는 것 외에는 아무 일도 하지 않음에도 불구하고 프로세서에서는 여전히 이 스레드를 실행시키기 떄문에 바쁜대기라고 부르는것이다.

바쁜대기를 사용하게 되면 두 번째 스레드 및 시스템에서 돌아가는 다른활성 스레드에서 진짜로 일을 처리하는 데 쓸 수 있을 소중한 프로세서 사이클을 뺏어가게 된다.

---

질문 : 클래스와 객체의 의미

클래스는 속성(상태)과 행동을 가진 무언가를 추상적으로 정의한것

객체는 다른 객체 인스턴스와는 별도의 상태를 가지고 있는 어떤 클래스의 특정 인스턴스를 뜻함.

질문 : 객체지향 프로그래밍에서 인터페이스와 추상 클래스 사이의 차이점을 설명하라

- 인터페이스에서는 클래스와 별도로 일련의 연관된 메소드를 선언한다.

클래스 계층 구조와는 독립적으로 애플리케이션 프로그래밍 인터페이스를 정의하는 같은 역활을 한다.

- 추상클래스는 메소드를 선언하기는 하지만 모든 메소드를 정의하지는 않는 불완전하게 정의된 클래스이다.

인터페이스와는 달리 추상클래스는 그 자체가 클래스다. 데이터 멤버도 들어갈 수 있고 다른 클래스의 서브클래스로 만들 수도 있다.

사실 인터페이스는 데이터 멤버 및 메소드 정의가 들어있지 않은 추상 클래스하고 거의 똑같다. 

* 결론 : 추상클래스는 그것을 베이스 클래스로 상속해서 더 구체적인 클래스를 만들어 쓰는 경우에 쓰기 좋다. 특히 서브 클래스에서 써먹을 수 있는 공통적인 기능을 추상 베이스클래스에 집어넣을 필요가 있을때 좋다. 

인터페이스는 서로 관련이 없는 클래스에서 개념적으로 연관된 기능을 작동시킬 수 있는 공통된 방식이 필요하지만 그 기능을 구현하는 방법은 제각기 다른 경우에 인터페이스가 좋다.

질문 : 가상메소드가 무엇인지 기술하고 어떻게 활용할 수 있는지 설명하라

가상메소드는 그 메소드를 실제로 호출하는 객체가 어떤 클래스인지에 따라 구현이 결정되는 메소드를 뜻한다.

가상메소드는 다형성을 활용할 때 유용하다. 

질문 : C#에서 다중 상속을 허용하지 않는 이유는?

한 클래스에서 직,간접적으로 하나 이상의 클래스를 상속할 수 있으며 이를 다중 상속이라고 부른다.

하지만 c#에서는 허용안함..

모호성 때문에...

어쩄든 단일 상속에 제약이 많기 때문에(공통 조상이 있는 클래스끼리만 행동을 공유할 수 있다는 점..) 대신 인터페이스를 통해

코드를 공유하는 식으로 구현되지는 않지만 서로 다른 계층 구조에 속한 클래스들끼리 같은 인터페이스를 외부에 노출시킬 수 있게 하여 부족한 부분을 어느정도 보완한다.

---

빅엔디안 리틀엔디안 확인방법

bool IsLittleEndian()

{

union {

int a;

char b;

}endianTest;

endianTest.a = 1;

return endianTest.b;

}

왜이렇게 했냐면..봐바 유니온은 메모리 시작주소의 위치를 공유하잖아..

그러면 위의 공용체는 즉 int형 4바이트와 char 1바이트의 시작주소가 같다는거지..그런 상황에서

int형에 정수 1을 넣었다. 그리고 1바이트 char의 값을 확인했어 그럼..

빅엔디안의 경우 0이 나와야 한다..왜냐면 낮은 메모리 주소에 큰 값이 들어가는데 현재 정수가 1이니까 큰값은 0이다..

리틀엔디안의 경우 1이 나와야 한다 왜냐면 낮은 메모리 주소에 작은 값이 들어가니까..1이 들어가있는것이다!

비트 연산 관련

int numOfbit(int num)

{

int count = 0;

int Bit = 1;

while (num != 0)

{

if ((Bit & num) == 1)

{

count++;

}

num = num >> 1;

}

return count;

}

---

매크로와 인라인 함수의 차이점

매크로는 전처리에 의한 단순 텍스트 치환방식이다. 굳이 함수 호출에 필요한 오버헤드를 부담하기에는 너무 단순한 코드가 있을때 쓴다.

인라인 함수는 일반 함수와 비슷하게 선언되지만, 매크로와 달리 컴파일러가 직접 처리한다.

공통점은 함수호출에 필요한 오버헤드를 줄이는 대신 프로그램이 커지는것을 감수해야한다.

가비지 컬렉션이란?

가비지 컬렉션이란 프로그램에서 더이상 쓰지 않는 메모리를 자동으로 찾아서 가져가는 것을 뜻한다.

장점

메모리 누수에 대한 버그를 없앨 수 있다. 메모리를 확실히 제대로 비워지도록 하기 위해 전통적으로 쓰였던 복잡한 메커니즘이 더 이상 없어도 되기 때문이다. 

단점은? 가비지 컬렉션을 사용하는 프로그램에서는 시스템에서 더이상 필요하지 않은 메모리를 언제 되찾아올기 결정하기 위한 오버헤드 때문에 대체로 더 느리다.