2008/11/20에 해당되는 글 2건
2008.11.20 :: XML? XAML? (part 2)
2008.11.20 :: 알고리즘 코딩기법 - 6. 상태를 나타내는 값싼 방법(bits) 2
2008. 11. 20. 23:25 :: .net Framework
저번 포스팅에 제목으로만 달아놓고 쓰지못했던 XAML이란 것에 대해 간략히 이야기 해보고자 합니다.
XAML이란?
XAML (Extensible Application Markup Language) = 확장 응용프로그램 마크업 언어
원래는 윈도우 프리젠테이션 파운데이션의 코드이름인 Avalon에서 따와서 Extension Avalon Markup Language의 약자였죠.
[zæ:mɛl]로 발음한다고 하네요.
.NET Framework를 공부하고 계시는 분이면 최근까지 런칭된 .NET Framework가 3.5까지 나와있다는 점과 WPF(윈도우 프리젠테이션 파운데이션), Silverlight등의 Framework와 관련된 여러 도구들이 나왔다는 것을 한번쯤 들어봤을것이라고 생각합니다. 이것들이야 말로 XAML(MS의 XML)기반의 서비스를 구축하기 위한 도구들입니다.
XAML 요소는 공통 언어 런타임 객체 인터페이스에 직접 매핑할 수 있지만 XAML은 공통 언어 런타임 속성과 이벤트를 해당 객체로 매핑하는데 사용합니다. 일반 XML문서와 마찬가지로 표준 문서 편집기, XAMLPad와 같은 코드 편집기, Vectropy와 같은 그래픽 편집기로 만들어 편집할 수도 있습니다. (물론 다들 Visual Studio를 열고 쓰시겠죠;) 급하게 수정해야할 부분이라면 간단히 notepad 같은 걸로 열고 수정하기엔 편하죠.
좀 더 쉽게 풀어쓰자면 XAML은 그래픽 요소, 사용자 인터페이스, 동작, 애니메이션 등을 정의하는 데 사용되는 XML 기반 언어이면서 Microsoft의 .NET Framework 3.0에 포함된 데스크톱 지향 기술인 윈도우 프리젠테이션 파운데이션용 태그 언어로서 처음 도입되었으며 응용 프로그램 생성 시 디자이너와 개발자 간 작업에 교량 역할을 하기 위해 고안되었습니다라고 할 수 있습니다.
지금까지는 응용 프로그램을 만들기 위해 디자이너가 사용하는 도구 및 리소스 모음이 개발자가 사용하는 것과 달랐으며 이러한 차이는 결과 응용 프로그램에도 부정적인 영향을 줄 여지가 있었습니다. Microsoft는 디자인 전문가들이 그래픽 항목과 사용자 인터페이스를 개별적으로 구성하여 최종 결과를 XAML로 표현하면 이를 통해 개발자가 응용 프로그램을 구축할 수 있도록 Microsoft Expression 및 Microsoft Expression Blend라는 새 Expression 도구 모음을 도입했습니다.
그리고 일반적으로 이런 내용에 대해서 한번쯤 들어보신분들도 가끔 모르는게 있는데 Silverlight의 최초 릴리스에 사용된 XAML은 데스크톱에 사용할 수 있는 완벽한 XAML의 웹 지향 하위 집합이므로 Windows Presentation Foundation에 사용된 XAML과는 차이가 있습니다. 따라서 WPF XAML에 익숙하다면 Silverlight XAML에 <Window> 태그, 페이지 리소스, 데이터 바인딩, 유용한 컨트롤 모델 등과 같은 기능이 없는 걸 금방 눈치채실 수 있을것이라 생각합니다.
XAML에서는 XML 태그를 사용하여 요소를 정의합니다. 각 Silverlight 문서의 루트 수준에는 UI 요소가 그려질 공간을 정의하는 Canvas 태그가 위치합니다. 이 Canvas에는 Silverlight에 필요한 XML 네임스페이스 선언이 들어 있습니다.
Canvas는 고유한 자식을 생성할 수 있는 자식 Canvas 등을 포함해 둘 이상의 자식을 가질 수 있습니다. 자식 Canvas의 위치는 부모 Canvas를 기준으로 상대적으로 지정되며 루트 Canvas만 예외입니다. 다음은 부모(Canvas)의 왼쪽 위 모서리에서 25픽셀 떨어진 곳에 위치한 사각형을 포함하는 Canvas의 예입니다.
우선 이번에는 간단한 내용만 이야기를 하고 맺도록 하겠습니다.
여담이지만 차세대 웹 표준으로 인해 최근 많은 논란이 있었죠. XForm, XAML, XUL 등등 각기 다른 회사에서 채택한 사용방식중 어떤 것을 사용할 것 인지에 대한 논란이죠. 상대적으로 현재는 XAML이 가장 우세하다고 하지만 우선은 좀 더 두고봐야 할테고..일단 공부는 그래도 계속해야죠 ㅋ
Reference by Wikipedia, jowon.springnote.com
좀 더 쉽게 풀어쓰자면 XAML은 그래픽 요소, 사용자 인터페이스, 동작, 애니메이션 등을 정의하는 데 사용되는 XML 기반 언어이면서 Microsoft의 .NET Framework 3.0에 포함된 데스크톱 지향 기술인 윈도우 프리젠테이션 파운데이션용 태그 언어로서 처음 도입되었으며 응용 프로그램 생성 시 디자이너와 개발자 간 작업에 교량 역할을 하기 위해 고안되었습니다라고 할 수 있습니다.
지금까지는 응용 프로그램을 만들기 위해 디자이너가 사용하는 도구 및 리소스 모음이 개발자가 사용하는 것과 달랐으며 이러한 차이는 결과 응용 프로그램에도 부정적인 영향을 줄 여지가 있었습니다. Microsoft는 디자인 전문가들이 그래픽 항목과 사용자 인터페이스를 개별적으로 구성하여 최종 결과를 XAML로 표현하면 이를 통해 개발자가 응용 프로그램을 구축할 수 있도록 Microsoft Expression 및 Microsoft Expression Blend라는 새 Expression 도구 모음을 도입했습니다.
그리고 일반적으로 이런 내용에 대해서 한번쯤 들어보신분들도 가끔 모르는게 있는데 Silverlight의 최초 릴리스에 사용된 XAML은 데스크톱에 사용할 수 있는 완벽한 XAML의 웹 지향 하위 집합이므로 Windows Presentation Foundation에 사용된 XAML과는 차이가 있습니다. 따라서 WPF XAML에 익숙하다면 Silverlight XAML에 <Window> 태그, 페이지 리소스, 데이터 바인딩, 유용한 컨트롤 모델 등과 같은 기능이 없는 걸 금방 눈치채실 수 있을것이라 생각합니다.
XAML에서는 XML 태그를 사용하여 요소를 정의합니다. 각 Silverlight 문서의 루트 수준에는 UI 요소가 그려질 공간을 정의하는 Canvas 태그가 위치합니다. 이 Canvas에는 Silverlight에 필요한 XML 네임스페이스 선언이 들어 있습니다.
<Canvas xmlns=”http://schemas.microsoft.com/winfx/2006/xaml/presentation” xmlns:x=”http://schemas.microsoft.com/winfx/2006/xaml”></Canvas>
Canvas는 고유한 자식을 생성할 수 있는 자식 Canvas 등을 포함해 둘 이상의 자식을 가질 수 있습니다. 자식 Canvas의 위치는 부모 Canvas를 기준으로 상대적으로 지정되며 루트 Canvas만 예외입니다. 다음은 부모(Canvas)의 왼쪽 위 모서리에서 25픽셀 떨어진 곳에 위치한 사각형을 포함하는 Canvas의 예입니다.
<Canvas Width=”250” Height=”200”> <Rectangle Canvas.Top=”25” Canvas.Left=”25” Width=”200” Height=”150” Fill=”Black” /></Canvas>
우선 이번에는 간단한 내용만 이야기를 하고 맺도록 하겠습니다.
여담이지만 차세대 웹 표준으로 인해 최근 많은 논란이 있었죠. XForm, XAML, XUL 등등 각기 다른 회사에서 채택한 사용방식중 어떤 것을 사용할 것 인지에 대한 논란이죠. 상대적으로 현재는 XAML이 가장 우세하다고 하지만 우선은 좀 더 두고봐야 할테고..일단 공부는 그래도 계속해야죠 ㅋ
Reference by Wikipedia, jowon.springnote.com
2008. 11. 20. 22:00 :: 알고리즘코딩기법
안녕하세요 17기 조일룡입니다.
참고
http://en.wikipedia.org/wiki/Bit_operation
사과, 배, 참외, 수박, 포도
이제 비트열을 이용하여 과일의 상태를 나타내보도록 하겠습니다. 그리고 배열을 사용한 방법과 비교를 해보도록 하겠습니다
비트에 의미부여
과일의 종류가 5가지 이므로 다섯비트가 필요합니다.
첫번째 비트부터 다섯번째 비트까지 각각 사과, 배, 참외, 수박, 포도가 있는지 없는지 여부를 나타내는 상태라고 생각합시다. 과일이 있으면 그 비트는 1이 되고 비트가 0이면 그 과일이 없다는 것을 의미합니다.
5개의 비트를 저장할 변수가 필요한데 현재 C++에서 int는 32bit 정수형이므로 5개의 과일의 상태를 저장하고도(5bit사용) 27bit나 남으므로 int형을 사용하겠습니다.
초기상태
처음에는 과일이 모두 있으므로 아래와 같이 초기 상태를 설정할 수 있습니다.
(1 << 5) - 1에 대해 간략히 살펴봅시다.
1을 이진수로 나타내면 00000001(2)입니다. << 5 연산은 이 바이너리를 왼쪽(더 큰 비트쪽)으로 5번 이동합니다. 그럼 00100000(2)가 됩니다. 여기에서 1을 빼면 00011111(2)가 됩니다. 어떤가요? 다섯개의 과일이 모두 있다는 상태가 되었네요
배열버전
누군가 과일을 먹는다
A가 지나가다 쟁반에 과일이 놓여져 있는 것을 보고 자기가 젤 좋아하는 수박을 먹었습니다. 이를 아래와 같이 코드로 옮길 수 있습니다.
bitwise NOT, bitwise AND 연산을 이용하여 수박에 해당하는 비트를 0으로 변환하였습니다.
연산 후 frutis은 10111(2)가 됩니다.
배열버전
이번엔 B가 지나가다 쟁반을 보았습니다. B는 욕심이 많아서 배, 수박, 포도를 먹으려 합니다. 아래 코드를 봅시다.
bitwise OR 연산을 이용하여 B가 먹고싶은 과일들의 비트를 만듭니다. 그 후 먹는 것은 A때와 같습니다.
여기에서 수박은 A가 이미 먹었기 때문에 B가 먹을 수는 없습니다. B가 먹을 수 있는 과일은 자기가 먹으려고 하면서 쟁반에 놓여져 있어야 합니다. eatByB는 B가 실제로 먹게되는 과일을 bitwise AND 연산으로 구합니다.
연산후 eatByB와 fruits는 다음과 같습니다.
eatByB = 10111(2) & 11010(2) = 10010(2) -> 배, 포도
fruits = 10111(2) & (~11010(2)) = 10111(2) & 00101(2) = 00101(2) -> 사과, 참외
배열버전
어떤 과일이 없어진거지??
A랑 B가 과일을 먹어서 몇개의 과일이 없어진 것을 나중에 알게된 쟁반의 주인은 어떤 과일이 없어졌는지 알고 싶습니다.
쟁반의 주인은 bitwise NOT연산으로 어떤 과일이 없어졌는지 금새 알아차립니다.
배열버전
사과 마니아 등장
사과를 엄청나게 좋아하는 A씨가 있습니다. A씨는 사과를 너무 좋아해서 쟁반에 사과가 있으면 그 사과를 먹을 것입니다. 반면 쟁반에 사과가 없으면 자기가 가지고 있던 사과를 쟁반에 올려놓는다고 합니다. A씨가 쟁반을 본다면 어떤일이 일어날까요?
배열버전
Bitwiase 표기 vs 배열표기
yes/no로 나타낼 수 있는 일련의 상태가 있을 때, 이 상태를 나타낼 수 있는 두 가지 방법(비트, 배열)에 대해서 간략히 살펴보았는데요.. 구현의 예에서 드러나듯이 bit를 사용하는 방법이 속도, 메모리, 구현 측면에서 모두 배열을 사용하는 방법보다 월등히 뛰어납니다. (물론 제 생각이긴 합니다) 한가지 단점이 있다면 나타내야할 상태의 공간이 크다면(예를 들어 50개 정도되는 상태는 int변수에 담을 수 없으니깐여;;) bit를 사용하기 힘들어 지는데 이때는 다른 방법을 강구해 봐야겠지요.. 배열을 쓰는것도 방법이 될 수 있습니다.
다행이도 long long(__int64) 이라는 타입은 64bit를 지원합니다. 이 타입을 이용하면 64개의 독립된 변수를 가진 상태까진 하나의 변수를 이용하여 나타낼 수 있습니다.
이번 포스팅에서 bit를 이용한 상태표현에 대해서 알아보았으니 다음 포스팅에서는 bit를 이용한 brute force방법에 대해 알아보겠습니다.
ps.
제가 포스팅하는 소스에는 무한버그가 있을 수도 있습니다. -ㅁ-;;
이번 포스팅에서는 2진수를 사용하여 상태를 나타내는 기법에 대해서 살펴보겠습니다.
많은 경우에 어떤 상태는 Yes나 No로 나타낼 수 있습니다.
예를 들면 쟁반위에 사과가 있냐/없냐 와 같은 상태가 있을 수 이겠네요. 초기에 쟁반위에 사과, 배, 참외, 수박, 포도가 있었는데 누군가 과일을 먹어서 어떤 것은 없어졌습니다. 이때 가능한 상태는 모두 32(=2^5)가지가 됩니다.
프로그램을 작성하면서 위와 같은 상태를 나타내야 하는 경우는 종종 발생합니다. 그리고 어떻게든 나타내게 되겠지요..
각각의 과일마다 boolean type의 변수를 하나식 만들 수도 있고 좀 더 똑똑한 누군가는 boolean type의 배열을 선언할 수도 있습니다.
오늘 포스팅에서는 bit를 이용하여 이런 상황을 표현하는 방법을 알아보겠습니다.
많은 경우에 어떤 상태는 Yes나 No로 나타낼 수 있습니다.
예를 들면 쟁반위에 사과가 있냐/없냐 와 같은 상태가 있을 수 이겠네요. 초기에 쟁반위에 사과, 배, 참외, 수박, 포도가 있었는데 누군가 과일을 먹어서 어떤 것은 없어졌습니다. 이때 가능한 상태는 모두 32(=2^5)가지가 됩니다.
프로그램을 작성하면서 위와 같은 상태를 나타내야 하는 경우는 종종 발생합니다. 그리고 어떻게든 나타내게 되겠지요..
각각의 과일마다 boolean type의 변수를 하나식 만들 수도 있고 좀 더 똑똑한 누군가는 boolean type의 배열을 선언할 수도 있습니다.
오늘 포스팅에서는 bit를 이용하여 이런 상황을 표현하는 방법을 알아보겠습니다.
Bitwise operation
자주 사용하는 bitwise operation은 bitwise and, bitwise or, bitwise complement, bitwise xor 정도가 있습니다.
하나씩 알아보도록 하겠습니당
bitwise AND
bitwise AND는 두 바이너리 표현에 대해서 각 비트의 쌍마다 AND 연산을 합니다.
C++ 에서 bitwise AND 연산자는 &입니다. 반면 logical AND 연산자는 &&입니다. 사용할 때 주의를 해야겠지요.
bitwise AND 연산은 주로 bitmask를 취할때 사용합니다. 가령 어떤 바이너리에 대해서 첫번째 비트와 세번째 비트를 취하고 싶다면 bitwise AND 0101(2) 를 취하면 됩니다.
bitwise OR
bitwise OR은 두 바이너리 표현에 대해서 각 비트의 쌍마다 OR 연산을 합니다.
C++에서 bitwise OR 연산자는 |입니다. 마찬가지로 logical OR연산자인 ||와 혼돈할 가능성이 크니 주의해야겠습니다.
bitwise OR 연산은 바이너리 표현에 플레그(flag)를 추가할때 사용합니다. 각 비트마다 어떤 의미를 부여한 사항에서 첫번째 비트와 세번째 비트에 해당하는 의미가 추가되었다면 원래 상태에다가 새로 추가된 상태를 더해야 합니다. 이때 bitwise OR을 사용합니다.
bitwise XOR
bitwise XOR은 두 바이너리 표현에 대해서 각 비트의 쌍마다 XOR 연산을 합니다.
C++에서 bitwise XOR 연산자는 ^입니다. AND나 OR과 다르게 logical XOR 연산자는 c++에 없습니다.
위의 예에서와 같이 bitwise XOR 연산은 바이너리 표현에에서 특정 비트를 토글(toggle)할때 사용합니다. 비트열 중 어떤 상태를 나타내는 비트를 반전시켜줘야 할때 반전 시켜야할 비트만 1로 세팅해놓고 bitwise XOR를 취하면 됩니다.
bitwise NOT(complement)
bitwise XOR은 두 바이너리 표현에 대해서 각 비트의 쌍마다 NOT 연산을 합니다.
C++에서 bitwise NOT 연산자는 ~입니다. logical NOT 연산자는 !이니 햇갈릴일은 거의 없겠네요
bitwise NOT은 모든 비트를 반전합니다.
bitwise AND는 두 바이너리 표현에 대해서 각 비트의 쌍마다 AND 연산을 합니다.
0101
AND 0011
= 0001
AND 0011
= 0001
C++ 에서 bitwise AND 연산자는 &입니다. 반면 logical AND 연산자는 &&입니다. 사용할 때 주의를 해야겠지요.
bitwise AND 연산은 주로 bitmask를 취할때 사용합니다. 가령 어떤 바이너리에 대해서 첫번째 비트와 세번째 비트를 취하고 싶다면 bitwise AND 0101(2) 를 취하면 됩니다.
bitwise OR
bitwise OR은 두 바이너리 표현에 대해서 각 비트의 쌍마다 OR 연산을 합니다.
0101
OR 0011
= 0111
OR 0011
= 0111
C++에서 bitwise OR 연산자는 |입니다. 마찬가지로 logical OR연산자인 ||와 혼돈할 가능성이 크니 주의해야겠습니다.
bitwise OR 연산은 바이너리 표현에 플레그(flag)를 추가할때 사용합니다. 각 비트마다 어떤 의미를 부여한 사항에서 첫번째 비트와 세번째 비트에 해당하는 의미가 추가되었다면 원래 상태에다가 새로 추가된 상태를 더해야 합니다. 이때 bitwise OR을 사용합니다.
bitwise XOR
bitwise XOR은 두 바이너리 표현에 대해서 각 비트의 쌍마다 XOR 연산을 합니다.
0101
XOR 0011
= 0110
XOR 0011
= 0110
C++에서 bitwise XOR 연산자는 ^입니다. AND나 OR과 다르게 logical XOR 연산자는 c++에 없습니다.
위의 예에서와 같이 bitwise XOR 연산은 바이너리 표현에에서 특정 비트를 토글(toggle)할때 사용합니다. 비트열 중 어떤 상태를 나타내는 비트를 반전시켜줘야 할때 반전 시켜야할 비트만 1로 세팅해놓고 bitwise XOR를 취하면 됩니다.
bitwise NOT(complement)
bitwise XOR은 두 바이너리 표현에 대해서 각 비트의 쌍마다 NOT 연산을 합니다.
NOT 0101
= 1010
= 1010
C++에서 bitwise NOT 연산자는 ~입니다. logical NOT 연산자는 !이니 햇갈릴일은 거의 없겠네요
bitwise NOT은 모든 비트를 반전합니다.
참고
http://en.wikipedia.org/wiki/Bit_operation
사과, 배, 참외, 수박, 포도
이제 비트열을 이용하여 과일의 상태를 나타내보도록 하겠습니다. 그리고 배열을 사용한 방법과 비교를 해보도록 하겠습니다
비트에 의미부여
과일의 종류가 5가지 이므로 다섯비트가 필요합니다.
첫번째 비트부터 다섯번째 비트까지 각각 사과, 배, 참외, 수박, 포도가 있는지 없는지 여부를 나타내는 상태라고 생각합시다. 과일이 있으면 그 비트는 1이 되고 비트가 0이면 그 과일이 없다는 것을 의미합니다.
5개의 비트를 저장할 변수가 필요한데 현재 C++에서 int는 32bit 정수형이므로 5개의 과일의 상태를 저장하고도(5bit사용) 27bit나 남으므로 int형을 사용하겠습니다.
초기상태
처음에는 과일이 모두 있으므로 아래와 같이 초기 상태를 설정할 수 있습니다.
int numFruits = 5; // 과일의 수
int bitFruits[] = {(1<<0), (1<<1), (1<<2), (1<<3), (1<<4)}; // 사과, 배, 참외, 수박, 포도를 나타내는 비트
int fruits = (1<<numFruits) - 1; // 모든 과일이 있다
int bitFruits[] = {(1<<0), (1<<1), (1<<2), (1<<3), (1<<4)}; // 사과, 배, 참외, 수박, 포도를 나타내는 비트
int fruits = (1<<numFruits) - 1; // 모든 과일이 있다
(1 << 5) - 1에 대해 간략히 살펴봅시다.
1을 이진수로 나타내면 00000001(2)입니다. << 5 연산은 이 바이너리를 왼쪽(더 큰 비트쪽)으로 5번 이동합니다. 그럼 00100000(2)가 됩니다. 여기에서 1을 빼면 00011111(2)가 됩니다. 어떤가요? 다섯개의 과일이 모두 있다는 상태가 되었네요
배열버전
const int numFruits = 5; // 과일의 수
bool fruits[numFruits] = {true, true, true, true, true}; // 모든 과일이 있다.
bool fruits[numFruits] = {true, true, true, true, true}; // 모든 과일이 있다.
누군가 과일을 먹는다
A가 지나가다 쟁반에 과일이 놓여져 있는 것을 보고 자기가 젤 좋아하는 수박을 먹었습니다. 이를 아래와 같이 코드로 옮길 수 있습니다.
int eatA = bitFruits[3]; // 먹을 과일 -> 수박
fruits &= ~eatA; // A가 과일을 먹음 - 수박을 먹어서 없어짐
fruits &= ~eatA; // A가 과일을 먹음 - 수박을 먹어서 없어짐
bitwise NOT, bitwise AND 연산을 이용하여 수박에 해당하는 비트를 0으로 변환하였습니다.
연산 후 frutis은 10111(2)가 됩니다.
배열버전
int eatA[numFruits] = {false, false, false, true, false}; // 먹을 과일 -> 수박
// B가 과일을 먹음
for (int i = 0; i < numFruits; i++)
if (eatA[i] == true)
fruits[i] = false;
// B가 과일을 먹음
for (int i = 0; i < numFruits; i++)
if (eatA[i] == true)
fruits[i] = false;
이번엔 B가 지나가다 쟁반을 보았습니다. B는 욕심이 많아서 배, 수박, 포도를 먹으려 합니다. 아래 코드를 봅시다.
int eatB = bitFruits[1] | bitFruits[4] | bitFruits[5]; // B가 먹으려는 과일 - 배, 수박, 포도에 해당하는 비트
int eatByB = fruits & eatB; // B가 실제로 먹는 과일
fruits &= ~eatB; // B가 과일을 먹음
int eatByB = fruits & eatB; // B가 실제로 먹는 과일
fruits &= ~eatB; // B가 과일을 먹음
bitwise OR 연산을 이용하여 B가 먹고싶은 과일들의 비트를 만듭니다. 그 후 먹는 것은 A때와 같습니다.
여기에서 수박은 A가 이미 먹었기 때문에 B가 먹을 수는 없습니다. B가 먹을 수 있는 과일은 자기가 먹으려고 하면서 쟁반에 놓여져 있어야 합니다. eatByB는 B가 실제로 먹게되는 과일을 bitwise AND 연산으로 구합니다.
연산후 eatByB와 fruits는 다음과 같습니다.
eatByB = 10111(2) & 11010(2) = 10010(2) -> 배, 포도
fruits = 10111(2) & (~11010(2)) = 10111(2) & 00101(2) = 00101(2) -> 사과, 참외
배열버전
int eatB[numFruits] = {false, true, false, true, true};
int eatByB[numFruits] = {false};
for (int i = 0; i < numFruits; i++)
{
// B가 실제로 먹는 과일
if (fruits[i] && eat[i])
eatByB[i] = true;
// B가 과일을 먹음
if (eat[i] == true)
fruits[i] = false;
}
int eatByB[numFruits] = {false};
for (int i = 0; i < numFruits; i++)
{
// B가 실제로 먹는 과일
if (fruits[i] && eat[i])
eatByB[i] = true;
// B가 과일을 먹음
if (eat[i] == true)
fruits[i] = false;
}
어떤 과일이 없어진거지??
A랑 B가 과일을 먹어서 몇개의 과일이 없어진 것을 나중에 알게된 쟁반의 주인은 어떤 과일이 없어졌는지 알고 싶습니다.
쟁반의 주인은 bitwise NOT연산으로 어떤 과일이 없어졌는지 금새 알아차립니다.
int disappeared = ~fruits; // 없어진 과일 -> 배, 수박, 포도
배열버전
int disappeared[numFruits] = {false};
for (int i = 0; i < numFruits; i++)
if (fruits[i] == false)
disappeared[i] = true;
for (int i = 0; i < numFruits; i++)
if (fruits[i] == false)
disappeared[i] = true;
사과 마니아 등장
사과를 엄청나게 좋아하는 A씨가 있습니다. A씨는 사과를 너무 좋아해서 쟁반에 사과가 있으면 그 사과를 먹을 것입니다. 반면 쟁반에 사과가 없으면 자기가 가지고 있던 사과를 쟁반에 올려놓는다고 합니다. A씨가 쟁반을 본다면 어떤일이 일어날까요?
if (fruits & bitFruits[0]) // 사과가 있으면
fruits &= ~bitFruits[0]; // 사과를 먹는다
else // 사과가 없으면
fruits |= bitFruits[0]; // 사과를 쟁반에 놓는다
fruits &= ~bitFruits[0]; // 사과를 먹는다
else // 사과가 없으면
fruits |= bitFruits[0]; // 사과를 쟁반에 놓는다
배열버전
if (fuits[0] == true) // 사과가 있으면
fruits[0] = false; // 사과를 먹는다
else // 사과가 없으면
fruits[0] = true; // 사과를 쟁반에 놓는다.
fruits[0] = false; // 사과를 먹는다
else // 사과가 없으면
fruits[0] = true; // 사과를 쟁반에 놓는다.
Bitwiase 표기 vs 배열표기
yes/no로 나타낼 수 있는 일련의 상태가 있을 때, 이 상태를 나타낼 수 있는 두 가지 방법(비트, 배열)에 대해서 간략히 살펴보았는데요.. 구현의 예에서 드러나듯이 bit를 사용하는 방법이 속도, 메모리, 구현 측면에서 모두 배열을 사용하는 방법보다 월등히 뛰어납니다. (물론 제 생각이긴 합니다) 한가지 단점이 있다면 나타내야할 상태의 공간이 크다면(예를 들어 50개 정도되는 상태는 int변수에 담을 수 없으니깐여;;) bit를 사용하기 힘들어 지는데 이때는 다른 방법을 강구해 봐야겠지요.. 배열을 쓰는것도 방법이 될 수 있습니다.
다행이도 long long(__int64) 이라는 타입은 64bit를 지원합니다. 이 타입을 이용하면 64개의 독립된 변수를 가진 상태까진 하나의 변수를 이용하여 나타낼 수 있습니다.
이번 포스팅에서 bit를 이용한 상태표현에 대해서 알아보았으니 다음 포스팅에서는 bit를 이용한 brute force방법에 대해 알아보겠습니다.
ps.
제가 포스팅하는 소스에는 무한버그가 있을 수도 있습니다. -ㅁ-;;
