데니의 Techlog

이번 포스트에서는 비트연산에 대해 살펴보도록 하겠습니다. 프로그램에서 사용하는 n비트 정수는 내부적으로 n개의 비트로 구성된 이진수 형태로 저장이 됩니다. 예를 들어 32Bit int 자료형에서 42는 아래와 같습니다. 00000000000000000000000000101010 이진수를 10진수로 변경하는 방법은 각 자리 수에 2의 n-1제곱을 곱해주면 구할 수 있습니다. (중학교 때 배운 것으로 간주하고 넘어가겠습니다.) 부호가 있는 n비트 정수 변수에는 -2^(n-1) 부터 2^(n-1)-1까지의 정수를 저장할 수 있습니다. 부호가 있는 정수 표현에서 가장 왼쪽 비트는 부호를 나타내며 0은 양수를 나타내고 1은 음수를 나타냅니다. 나머지 n-1개의 비트는 정수의 크기를 표현하게 됩니다. 부호가 없는 ..

이번 포스트에서는 문제 풀이를 위한 프로그래밍 기법 두번째 재귀적 알고리즘에 대해서 알아보도록 하겠습니다. 재귀를 사용하면 알고리즘을 잘 구현할 수 있게 되는 경우가 많이 있습니다.(안좋은 경우도 있지만) 문제 풀이를 하면서 답이 될 수 있을 만한 재귀적 풀이 후보들을 소개해보고자 합니다. 1. 부분집합 생성하기 재귀를 사용하는 예 중 부분집합 생성하기에 대해 살펴보도록 하겠습니다. 원소가 n개인 집합의 모든 부분집합을 생성하는 알고리즘을 구현해야하는 상황에 있다고 생각해봅시다. {1, 2, 3}의 부분집합은 (공집합), {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} 이렇게 있습니다. 우선 부분집합을 구하는 search라는 함수는 다음과 같은 벡터를 사용합니다. 1 vec..

알고리즘 문제 풀이를 위한 프로그래밍 기법에 대해 간단히 정리해보고자 한다. 단순 입/출력에서도 어떤 함수를 써야 실행 시간이 조금이라도 짧아질 수 있는지 알아보자. #include using namespace std; int main() { // 이 부분에 원하는 코드 } #include 는 표준 라이브러리 전체를 포함시키는 g++ 컴파일러의 기능이다. iosttream, vector, algorithm 등의 라이브러리를 개별적으로 포함시키지 않아도 자동으로 사용할 수 있게 된다. 작성된 소스 코드의 컴파일은 터미널에서 아래와 같은 명령어로 컴파일한다. g++ -std=c++11 -02 -Wall test.cpp -o test 컴파일러는 c++11 표준을 따르고(-std=c++11) 코드를 최적화 하며..