비트연산으로 조합 풀기
기본 비트연산자 이해하기
비트연산은 숫자를 2진수 형태로 다루는 연산입니다. 먼저 기본적인 비트연산자들을 알아보겠습니다.
연산자 | 기능 | 설명 |
& | AND 연산 | 비트단위로 AND 연산을 합니다 |
\| | OR 연산 | 비트단위로 OR 연산을 합니다 |
\^ | XOR 연산 | 비트단위로 XOR 연산을 합니다 |
\~ | NOT 연산 | 단항 연산자로서 피연산자의 모든 비트를 반전시킵니다 |
\<\< | 왼쪽 시프트 | 피연산자의 비트 열을 왼쪽으로 이동시킵니다 |
\>\> | 오른쪽 시프트 | 피연산자의 비트 열을 오른쪽으로 이동시킵니다 |
특정 비트 위치의 값 확인하기
비트연산을 활용하면 특정 위치의 비트가 0인지 1인지 확인할 수 있습니다.
0번 비트 확인하기
0번 비트(가장 오른쪽 비트)가 0인지 1인지 확인하는 방법은 다음과 같습니다.
int main()
{
int d = 0x6; // 6 = 0110(2)
int result = 0;
result = d & 0x1; // 0번 비트만 추출
if (result > 0)
{
// 0번 비트가 1인 경우
}
return 0;
}
C++
복사
1번 비트 확인하기
1번 비트를 확인하려면 먼저 해당 비트를 0번 위치로 이동시킨 후 확인합니다.
int d = 0x6; // 6 = 0110(2)
int result = 0;
result = (d >> 1) & 0x1; // 1번 비트를 0번 위치로 이동 후 추출
if (result > 0)
{
int a = 0; // 1번 비트가 1인 경우
}
C++
복사
N번 비트 확인하기 (일반화)
위의 원리를 일반화하면 N번째 비트를 확인하는 공식을 만들 수 있습니다.
int d = 0x6;
int result = 0;
result = (d >> n) & 0x1; // n번 비트를 0번 위치로 이동 후 추출
if (result > 0)
{
int a = 0; // n번 비트가 1인 경우
}
C++
복사
핵심 원리: (숫자 >> n) & 0x1
•
>> n: n번 비트를 0번 위치로 이동시킵니다
•
& 0x1: 0번 비트만 추출하고 나머지는 0으로 만듭니다 (마스킹)
실습: 2진수에서 1의 개수 세기
이제 배운 내용을 활용하여 실전 문제를 풀어보겠습니다.
문제: 0부터 15 사이의 숫자를 입력받아 2진수로 변환했을 때 1이 몇 개인지 세어보세요.
#include <iostream>
int main()
{
int d;
int result;
int count;
std::cin >> d; // 0~15 입력
count = 0;
// 8비트를 모두 확인 (15 = 0000 1111)
for (size_t i = 0; i < 8; i++)
{
result = (d >> i) & 0x1; // i번 비트 확인
if (result > 0)
{
count++; // 1인 비트 개수 증가
}
}
std::cout << count << std::endl;
return 0;
}
C++
복사
실행 예시:
•
입력: 15 (2진수로 0000 1111)
•
출력: 4 (1이 4개 있습니다)
비트연산 사용 시 주의사항
연산자 우선순위 확인하기
비트연산자는 다른 연산자들과 우선순위가 다를 수 있으므로, 항상 괄호를 사용하는 습관을 들이시는 것이 좋습니다.
권장하는 방식:
result = (d >> i) & 0x1; // 명확한 괄호 사용
C++
복사
피해야 할 방식:
result = d >> i & 0x1; // 우선순위가 헷갈릴 수 있습니다
C++
복사
비트연산 핵심 개념 정리
비트연산을 제대로 이해하기 위해 꼭 알아야 할 개념들을 정리하겠습니다.
1.
진수 표현의 통일: 10진수, 16진수, 2진수는 모두 컴퓨터 내부에서 같은 숫자로 인식됩니다. 따라서 별도로 진수 변환을 할 필요가 없습니다.
2.
비트 마스킹: & 0x1을 사용하면 특정 비트만 추출할 수 있습니다.
3.
비트 시프트: >> n을 사용하면 원하는 비트를 0번 위치로 이동시킬 수 있습니다.
4.
괄호의 중요성: 연산 순서를 명확히 하기 위해 항상 괄호를 사용하는 것이 좋습니다.
연습 문제
배운 내용을 바탕으로 다음 문제들을 풀어보세요.
1.
주어진 숫자의 3번 비트가 1인지 확인하는 코드를 작성해보세요.
2.
8비트 숫자에서 연속된 1의 최대 길이를 구해보세요.
BFS 경로 추적하기
DFS와 BFS의 차이점 이해하기
그래프나 트리를 탐색하는 두 가지 대표적인 방법인 DFS와 BFS에 대해 알아보겠습니다.
DFS (Depth First Search - 깊이 우선 탐색)
DFS는 한 방향으로 끝까지 탐색한 후 다음 경로를 탐색하는 방식입니다. 가장 밑바닥까지 내려가면서 하나씩 탐색합니다.
BFS (Breadth First Search - 너비 우선 탐색)
BFS는 레벨별로 탐색하는 방식입니다. 현재 레벨의 모든 노드를 먼저 탐색한 후 다음 레벨로 이동합니다.
BFS를 사용해야 하는 경우
핵심 원칙
모든 DFS 문제는 BFS로도 풀 수 있습니다. 중요한 것은 BFS를 사용했을 때 답을 더 빨리 찾을 수 있는 문제를 구분하는 것입니다.
BFS가 적합한 문제 유형
다음과 같은 문제들은 BFS를 사용하는 것이 효율적입니다.
•
최단 경로를 구하는 문제
•
레벨별 탐색이 필요한 문제
•
모든 경우를 탐색하지 않고 특정 조건을 만족하는 결과를 찾을 수 있는 문제
BFS 구현 방법
Queue 자료구조 사용하기
BFS를 구현하기 위해서는 Queue(큐) 자료구조를 사용합니다.
•
Queue는 FIFO (First In First Out) 방식으로 동작합니다
•
현재 레벨의 노드들을 Queue에 저장합니다
•
Head에서 노드를 꺼내고 Tail에서 새로운 노드를 삽입합니다
배열을 이용한 Queue 구현
다음은 배열을 사용하여 Queue를 구현한 예시입니다.
#include <iostream>
#include <queue>
#include <print>
int queue[30] = { 1, 2 }; // 노드 값을 저장하는 배열
int level[30] = { 1, 1 }; // 각 노드의 레벨 정보
int parent[30] = { -1, -1 }; // 부모 노드의 인덱스 정보
int head = 0; // Queue의 앞쪽 포인터
int tail = 2; // Queue의 뒤쪽 포인터
C++
복사
BFS 탐색 과정 이해하기
레벨별 탐색 진행 방식
BFS는 다음과 같이 레벨별로 탐색을 진행합니다.
•
Level 1: 시작 노드
•
Level 2: 시작 노드의 자식들
•
Level 3: Level 2 노드들의 자식들
•
이런 식으로 계속 진행됩니다
Queue 상태 변화
1.
초기 상태: Queue에 시작 노드들을 삽입합니다
2.
반복 과정:
•
Head에서 노드를 꺼냅니다
•
해당 노드의 자식들을 Tail에 삽입합니다
•
Level 정보와 Parent 정보를 업데이트합니다
경로 추적 (Parent Tracking) 구현하기
BFS의 중요한 특징 중 하나는 경로를 추적할 수 있다는 것입니다. 결과를 출력할 때는 자식 노드에서 부모 노드를 거슬러 올라가며 시작 지점까지 추적합니다.
실습 예제: 권투 펀치 조합 문제
다음 문제를 통해 BFS를 활용한 경로 추적을 실습해보겠습니다.
문제:
권투선수가 원(1) 또는 투(2) 펀치를 사용하여 공격합니다. 이 선수가 세 번의 펀치를 날릴 때 모든 경우의 수를 BFS를 이용해서 출력해보세요.
1단계: 초기 상태 설정하기
먼저 Level 1에 있는 시작 노드들의 정보를 작성합니다.
2단계: 자식 노드 정보 채우기
Queue의 Front 노드에 접근하여 자식 노드들의 정보를 채워줍니다. 모두 채웠으면 Front를 Pop하고 다음 노드에 대해 같은 작업을 반복합니다.
3단계: Queue 완성하기
이 과정을 반복하면 다음과 같이 Queue가 채워집니다. 세 번의 펀치를 날리는 문제이므로 Level 3까지만 반복하면 됩니다.
각 노드별로 저장된 Queue가 완성됩니다. 총 14개의 노드가 있으므로 14칸의 Queue가 완성됩니다.
예를 들어 10번 인덱스의 Queue 정보는 트리에서 다음 위치를 의미합니다.
BFS Queue 채우기 코드
#include <iostream>
#include <queue>
int queue[30] = { 1, 2 };
int level[30] = { 1, 1 };
int parent[30] = { -1, -1 };
int head = 0;
int tail = 2;
int main()
{
while (true)
{
if (level[head] == 3)
break;
for (size_t i = 0; i < 2; i++)
{
queue[tail] = i + 1; // 원 투
level[tail] = level[head] + 1;
parent[tail] = head;
tail++;
}
head++;
}
return 0;
}
JavaScript
복사
경로 추적하여 결과 출력하기
결과를 출력하려면 자식 노드에서 부모 노드를 거슬러 올라가며 시작 지점까지 추적해야 합니다.
BFS는 자식 노드부터 거꾸로 부모 노드로 추적해 나갑니다. Parent 배열을 보면 현재 노드의 부모 노드 위치를 알 수 있습니다. (Queue에서 부모 위치의 인덱스 값)
따라서 반복문을 돌면서 경로를 추적하며 출력하면 됩니다.
전체 코드
#include <iostream>
#include <queue>
#include <print>
int queue[30] = { 1, 2 };
int level[30] = { 1, 1 };
int parent[30] = { -1, -1 };
int head = 0;
int tail = 2;
void print(int idx)
{
while (true)
{
if (idx == -1)
break;
std::println("{} 출력", queue[idx]);
idx = parent[idx];
}
}
int main()
{
while (true)
{
for (size_t i = 0; i < 2; i++)
{
queue[tail] = i + 1; // 원 투
level[tail] = level[head] + 1;
parent[tail] = head;
tail++;
}
head++;
if (level[head] == 3)
break;
}
for (size_t i = head; i < tail; i++)
{
print(i);
std::println("-----");
}
return 0;
}
C++
복사
“강의는 많은데, 왜 나는 아직도 코드를 못 짤까?”
혼자 공부하다 보면 누구나 이런 고민을 하게 됩니다.
•
강의는 다 들었지만 막상 손이 안 움직이고
•
복습을 하려 해도 무엇을 다시 봐야 할지 모르겠고
•
질문할 곳도 없고
•
유튜브는 결국 정답을 따라 치는 것밖에 안 되는 것 같고
문제는 ‘연습’이 빠졌기 때문입니다.
단순히 강의를 듣는 것만으로는 실력이 늘지 않습니다. 실제 문제를 풀고, 고민하고, 직접 구현해보는 시간이 반드시 필요합니다.
그래서, 얌얌코딩 코칭은 다릅니다
그냥 가르치지 않습니다. 스스로 설계하고, 코딩할 수 있게 만듭니다.
얌얌코딩 코칭에서는 단순한 예제가 아닌, 스스로 문제를 분석하고 구현해야 하는 연습문제를 제공합니다.
이 연습문제들은 다음과 같은 역량을 키우기 위해 설계되어 있습니다.
•
문제를 스스로 쪼개고 설계하는 힘
•
다양한 조건을 만족시키는 실제 구현 능력
•
기능 단위가 아닌, 프로그램 단위로 사고하는 습관
•
마침내 자신의 힘으로 코드를 끝까지 작성하는 경험
지금 필요한 건 더 많은 강의가 아닙니다
코드를 스스로 완성해 나가는 훈련, 그것이 지금 실력을 끌어올릴 가장 현실적인 방법입니다.
자세한 안내 보기: 프리미엄 코칭 안내 바로가기
또는 카카오톡 상담방: 얌얌코딩 상담방