[262가지 문제로 정복하는 코딩 인터뷰 간단요약] 4장 기본 자료형

참고로, 이 책은 자바 알고리즘 도서가 파이썬에 비해 많지가 않아서 추천 도서 중에 고른 책인데

내용은 매우 유용하지만 다소 난이도가 있어 입문용으로는 추전하지 않는다.

(책의 서문에서도 학부수준의 자료구조나 알고리즘이 익숙한 사람을 대상독자로 한다.)

 

나도 한번 읽으면 절반은 이해 못하지만, 여러번 읽다 보면 이해되지 않을까 싶어서 간단요약을 하려고 한다.

---

기본 자료형, 비트를 잘 사용하면 프로그램의 성능 향상 시킬 수 있다.

 

4.1 패리티 계산하기

 패리티 : 보통 정보 전달 과정에서 오류 생겼는지 검사하기 위한 값(전체 비트의 개수를 2로 나눈 나머지 값과 같다.)

1이 홀수개면 1, 짝수개면 0이 된다.

 

64비트로 이루어진 숫자 굉장히 많을때 -> 룩업테이블 활용

 - 무식하게 모든 비트 갯수 세기 -> 1이 짝수개 인지 홀수개인지? 2로 나눈 나머지값만 기억

 - 하위 비트 지우기 : x & ( x -1) // &는 두 비트가 모두 1인경우만 1

 - 룩업테이블에 캐시로 저장하기

 

4.2 비트 스왑

64비트가 주어졌을 때 i번째와 j번째 스왑하라

- 무식하게 지역변수에 저장하고 j번째를 i번째에 쓰고, i번째를 j번째에 쓴다 -> 1또는 0밖에 없으므로 두값이 다르면 뒤집는다 아님 말고. 

 

4.3 비트 뒤집기

64비트가 주어졌을 때 역순으로 재구성하라

- 무식하게 최하위 32개와 최상위 32개를 비트 스왑(4.2응용)

- 16비트에 대한 룩업테이블 만들기(4.1응용)

 

4.4 같은 무게를 가진 가장 가까운 정수 찾기

음이 아닌 정수 x의 무게를 2진수로 표현했을때 1로 세팅된 비트의 개수(92의 2진수는 (1011100)이므로 4)

x와 무게는 같지만 x와의 차이 |y-x|가 최소가 되는 y를 반환하라(단, x의 모든 비트가 0 혹은 1인 경우는 고려하지 않아도 된다.)

 - 최하위 비트부터 시작

 

 

4.5 곱셈과 덧셈 없이 x * y 계산하기

- 덧셈은 비트연산 이용 / 곱셈은 시프트와 덧셈 이용

- 무식하게 덧셈 반복(x를 y번 더하기)

- 결과값을 0으로 초기화 한 후 x비트 순회하며, x의 k번째 비트가 1로 세팅되어 있다면 2^k*y를 더한다.

(2^k*y는 y를 왼쪽으로 k번 시프트함으로써 구할 수 있다.)

 

4.6 x / y 계산하기

- 덧셈, 뺄셈, 시프트 연산만으로 양의 정수 x와 y를 나눈 몫을 구하라

- 무식하게 x를 y보다 작아질 때까지 빼기

- 2^k*y <= x를 만족하는 가장 큰 k를 찾은 뒤 x에서 2^k*y를 빼고, 2^k를 몫에 더한다.(반복할 때마다 최소 절반씩 줄어듦)

 

4.7 x^y 계산하기

실수형 x와 정수형 y가 주어졌을 때 x^y를 계산하라(오버플로와 언더플로는 무시)

지수의 성질에 대하여~

- 간단하게는 x를 y-1번 곱하는 것

- 복잡하게는 지수의 성질 아는 것

 

4.8 숫자 뒤집기

정수값 주어졌을 때, 숫자를 뒤집어서 출력하라(42 -> 24, -314 -> -413)

- 무식하게 문자열로 바꿔서 반대로 읽으면서 숫자로 변환

- 10으로 나눈 나머지를 붙인다(절대값으로 계산 후 부호를 붙인다)

 

4.9 회문 확인하기

회문 : 앞으로 읽어도 뒤로 읽어도 동일한 문자열

 - 주어진 10진수 숫자가 회문인지 판단하라

 - 최하위, 최상위 숫자 비교해서 같으면 양 옆을 떼면서 줄여 나간다

 

4.10 임의의 숫자를 균등한 확률로 생성하기

6명이 앞면 뒷면 나올 확률 같은 동전을 통해 운전자 뽑으려 함

 - 같은 확률 생성해내는 임의의 숫자 생성기 주어졌을 때 a와 b 사이의 임의의 자연수 i 생성하려면?

 

4.11 사각형이 겹치는지 확인하기

두개의 직사각형 주어졌을 때 겹치는지 확인하고 겹치면 겹치는 직사각형 정보 반환 (x, y 축에 평행한 직사각형만 고려)

 - 겹치지 않는 직사각형 조건 생각해보기