자료구조 과제 비트맵

안녕하세요. wholeworldisblue입니다.

역대급으로 짧은 코드가 나왔지만 역대급으로 삽질했어요.

옆에서 친구가 '너 무슨 소리 하는거야?' 라고 하지 않았다면 계속 삽질했겠죠ㅋㅋ

 

'비트맵' 이라는 과제입니다. 제목을 보자마자 비트셋에 관한 문제라는 걸 눈치챘어야하는데 말이죠. 

과제는 다음과 같았습니다. 

 

1. Long Long 자료형인 수를 받아서 matrix 초기화

2. 전치(Transpose) 

3. 각 행의 수를 출력

 

 

전치를 모르시는 분은 아래 링크를 보고 와주세요! 뒤집는다고 보시면 간단합니다.

 

ko.wikipedia.org/wiki/%EC%A0%84%EC%B9%98%ED%96%89%EB%A0%AC

전치행렬 - 위키백과, 우리 모두의 백과사전

 

이해가 잘 안 되시는 분이 있으실 수도 계시니 간단히 예를 들어보겠습니다. 

 

0 1

1 1 

 

이렇게 보면 첫 행은 1 (0 1), 두 번째 행은 3(1 1)인 걸 알 수 있죠.

이를 전치 시켜 보겠습니다. 

 

1 1 

1 0 

 

그러면 첫 행은 3(1 1), 두 번째 행은 3(1 0) 인 걸 알 수 있습니다. 

 

 

과제는 이런 느낌입니다!

왼쪽이 입력 오른쪽이 출력 테스트 파일입니다. 

 

 

 

 

내가 한 삽질

: 저는 당연히 이렇게 생각했습니다. 

'그럼 숫자를 하나하나 입력 받고 이를 2진수로 만들어야겠다. 

하지만 음수도 들어오니깐 양수랑 음수를 구분해서 받은 다음에 음수는 마이너스를 떼고 2의 보수를 한 후 +1을 해주면 되겠네. 근데 matrix 안에 넣어둘건데 Carry 를 어떻게 하지? '

 

그래서 찾아보니 비트셋(bitset)이라는 라이브러리가 있더군요. 이진수로 바꾸어주고 string,longlong, unsigned long long 까지 변환도 시킬 수 있는 편리한 라이브러리 였습니다 .

 

 그래서 숫자를 받으면 이진수로 변환시켜주고 이 값을 string로 형변환 해서 makeMAT 라고 정의한 함수를 통해 matrix 에 넣어주었습니다. 그러고 전치를 하고 나니 문제점이 있었습니다.

 

bitset 을 찾아봤는데 십진수를 이진수로 변환하는 건 가능하지만 이진수를 십진수로 변화시키는 게 안되는 겁니다. 

그래서 2진수를 10진수로 변환하는 함수 makeLL를 짜다가 제대로 동작하지 않아서 친구한테 짜증을 내고 있는 찰나였습니다. 

 

 

 

 

 

 

 

그렇습니다. 

 

비트연산자를 쓰면 간단히 해결이 되는 거 였어요.

어차피 컴퓨터는 이진수로 숫자를 저장하니깐요.

 

그럼 다시 풀어봅시다. 

 

 

---

i 번째의 bit 를 가져오기 위해 getBit() 함수를 만듭니다.

여기서 1<<i 를 int 형이 아닌 long long int 형으로 형변화를 해주어야하는데 이렇게 하지 않으면 32비트가 연속적으로 나오기 때문에 0번째 비트와 32번째 비트에 1이 들어가게 됩니다. 이는 원하는 결과가 아니기 때문에 형변환을 해줍니다. 

 

그리고 자리수에 맞제 전치를 시키고 난 후에는 각 행을 읽으면서 long long 변수에 비트를 설정해주어야하기 때문에 setBit() 함수를 만들어줍니다. 

 

잊지 않고 long long int  로 1를 형변환 해줍니다.

 

 

 

이런 식으로 하면 문제가 아주 짧게 풀립니다! 

 

왠지 친구가 30분 만에 문제를 다 풀더라구요. 

저는 세시간이 걸렸는데 말이죠. 

앞으로 친구한테 과제를 미리미리 해라고 해야겠어요..ㅋㅋㅋ

수고하셨습니다. 

 

자료는 저의 Github 에 가면 확인하실 수 있습니다. 

 

github.com/Chung-god/DataStructureHW/tree/master/HW3_bitmap

Chung-god/DataStructureHW