본문 바로가기

알고리즘26

비트마스크(BitMask) - 비트 연산 컴퓨터는 2진법을 사용해서 연산을 하는데, 비트 마스크는 이를 활용하는 기법이다. 정수를 이진수로 표현하는 방식을 활용해서 보다 빠르고, 간결하게 작성할 수 있다는 게 비트 마스크 기법의 장점이다. 이에 더해 비트마스크 기법은 비트 N개를 활용해 2^N가지의 경우를 표현이 가능하기 때문에 메모리 사용량이 더 적다. 이러한 장점들 때문에 비트 마스크를 유용하게 사용할 수 있는 상황이 더러 생긴다. 비트 마스크를 사용하기 위해서는 우선 비트 연산자를 잘 알아야 한다. 다음은 비트 연산자의 종류를 표를 통해 작성한 것이다. 다만 여기서 주의할 점은 와 같은 시프트 연산자의 경우 만약 할당된 값이 1100일 경우 2023. 3. 22.
분할 정복 분할 정복은 해결할 문제를 여러 개의 작은 부분으로 나눈 뒤, 나뉜 작은 문제들을 각각 해결한다. 그 이후 해결된 해답을 모은다(필요하다면). 분할 정복은 일반적으로 top-down 접근 방식을 사용한다. 일반적으로 top-down방식은 재귀 호출을 통해 분할해서 문제를 해결한다. 큰 문제가 작은 문제로 나눌 수 있다면 재귀를 계속해서 호출해서 더 이상 나눌 수 없는 작은 문제가 되었을 때, 문제를 해결하고 필요에 따라 해결한 작은 문제들을 다시 합치게 된다. 여기서 중요한 것은 나누어진 문제들이 서로 상관관계가 없어야 한다는 것이다. 즉, 나뉜 문제들이 서로의 풀이 과정에서 서로에 영향을 미치지 않아야 한다. 만약 나뉜 문제들이 서로에 영향을 끼친다면 각각의 해답이나 풀이 과정이 달라질 수 있기 때문이.. 2023. 3. 22.
1의 보수(One's Complement) 우선 보수에 대해 알아보기 전에 간단히 알아볼 개념들이 있다. 일단 진법의 밑수. 밑수는 각 진법에서 기호에 사용되는 숫자의 수를 밑수라고 한다. 10진법에서의 밑수는 10, 2진법에서의 밑수는 2, 8진법에서의 밑수는 8이다. 또한 모든 진법에서 밑수는 0부터 시작한다. 2진법에서의 밑수는 0과 1, 10진법에서의 밑수는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9와 같이 10개이다. 이제 여기서 보수를 설명할 수 있다. 보수란, 두 수의 합이 진법의 밑수가 되게 하는 수라고 할 수 있다. 10진법에서 4의 10의 보수는 6이고, 2의 10의 보수는 8이다. 그렇다면 100에 대한 10의 보수는? 900이다, 10을 맞추는 게 아닌, 10진법에서 자릿수를 올라가게 하는 수라고 생각하면 된다. 이.. 2023. 3. 22.
2진수, 8진수, 10진수, 16진수 많이들 들어보았을 것이다. 인간은 10진법, 컴퓨터는 2진법. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. 인간이 10진법을 쓰는 방법으로 숫자를 표기해 사용한다. 그렇다면 컴퓨터는 어떻게 2진법을 사용하는 것일까. 컴퓨터의 내부에는 수많은 트랜지스터가 존재하는데, 이 트랜지스터를 전기 신호를 통해 켰다 껐다 할 수 있다. 여기 트랜지스터가 켜지면 on(true), 꺼지면 off(false) 상태라고 볼 수 있다. 컴퓨터는 이 상태를 각각 1, 0으로 인식하고 이를 통해 2진법을 사용할 수 있는 것이다. 뭐 이런 건 차치하고, 왜 10진수가 아닌 다른 것들도 배워야 할까? 그 이유는 나중에 배울 비트 연산을 위해서이다. 비트 연산자를 통해 추후 비트 마스킹과 같은 기법들을 활용할 때가 오는데, .. 2023. 3. 21.

티스토리툴바