비트연산으로 조합풀기, BFS 경로 추적하기

비트연산 (Bit Operation)

기본 비트연산자

연산자	기능	설명
&	AND 연산	비트단위로 AND 연산을 한다
\|	OR 연산	비트단위로 OR 연산을 한다
^	XOR 연산	비트단위로 XOR 연산을 한다
~	NOT 연산	단항 연산자로서 피연산자의 모든 비트를 반전시킨다
<<	왼쪽 시프트	피연산자의 비트 열을 왼쪽으로 이동시킨다
>>	오른쪽 시프트	피연산자의 비트 열을 오른쪽으로 이동시킨다

특정 비트 위치 확인하기

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번 비트가 0인지 1인지 확인

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번 비트가 0인지 1인지 확인 (일반화)

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으로 마스킹)

실습: 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 (0000 1111)

•

출력: 4 (1이 4개)

비트연산 사용 시 주의사항

1. 연산자 우선순위 확인

•

항상 괄호를 사용하자!

•

비트연산자는 다른 연산자들과 우선순위가 다를 수 있음

좋은 예:

result = (d >> i) & 0x1;    // 명확한 괄호 사용
C++
복사

나쁜 예:

result = d >> i & 0x1;      // 우선순위 헷갈림 위험
C++
복사

중요 개념 정리

진수 변환 불필요: 10진수, 16진수, 2진수 모두 컴퓨터에서는 같은 숫자로 인식

비트 마스킹: & 0x1을 사용해 특정 비트만 추출

비트 시프트: >> n으로 원하는 비트를 0번 위치로 이동

괄호 사용: 연산 순서를 명확히 하기 위해 항상 괄호 사용

연습 문제

주어진 숫자의 3번 비트가 1인지 확인하는 코드를 작성해보세요

8비트 숫자에서 연속된 1의 최대 길이를 구해보세요

DFS vs BFS (깊이 우선 탐색 vs 너비 우선 탐색)

DFS vs BFS 기본 개념

DFS (Depth First Search - 깊이 우선 탐색)

•

우선탐색으로 깊이 우선으로 가장 밑에까지 내려가면서 하나 씩 탐색하는 방법

•

한 방향으로 끝까지 탐색한 후 다음 경로 탐색

BFS (Breadth First Search - 너비 우선 탐색)

•

너비 우선 탐색으로 level별로 오른쪽으로 가면서 탐색하는 방법

•

현재 level의 모든 노드를 탐색한 후 다음 level로 이동

BFS를 사용해야 하는 경우

핵심 원칙:

•

모든 DFS 문제는 BFS로 풀 수 있다

•

BFS를 풀어야 답이 빨리 나오는 문제를 찾는 것이 중요

BFS 적합한 문제:

•

최단 경로 문제

•

레벨별 탐색이 필요한 문제

•

4장 전부를 뽑지 않고 해당 결과를 만들 수 있는 문제

BFS 구현 방법

1. Queue 자료구조 사용

•

FIFO (First In First Out) 방식

•

현재 level의 노드들을 queue에 저장

•

Head에서 꺼내고 Tail에서 삽입

2. 배열을 이용한 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 탐색 과정

Level별 탐색 진행

Level 1: 시작 노드 Level 2: 시작 노드의 자식들 Level 3: Level 2 노드들의 자식들 ...

Queue 상태 변화

초기 상태: queue에 시작 노드들 삽입

반복 과정:

•

head에서 노드 꺼내기

•

해당 노드의 자식들을 tail에 삽입

•

level 정보와 parent 정보 업데이트

경로 추적 (Parent Tracking)

결과 출력 방법

결과를 출력하면 자식노드에서 부모노드를 시작지점까지 출력해나가면 된다

경우의수를 BFS를 이용해서 풀어보자

권투선수가 원(1) 또는 투(2) 펀치를 이용해서 공격을 한다.

이권투선수가 세번의 펀치를 날릴때 모든 경우의수를 BFS 를 이용해서 출력해보자.

먼저 level 1에 있는 내용을 써두고 시작한다.

이제 자식노드들에 대한 정보를 queue 프론트 노드에 접근해서 채워준다.

다채웠으면 queue에서 프론트를 뺴주고 pop 하면 그다음 프론트 (2번쨰 노드) 같은 작업을 반복한다.

이렇게 반복 하다 보면 아래와 같이 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;
}
JavaScript
복사

“강의는 많은데, 왜 나는 아직도 코드를 못 짤까?”

혼자 공부하다 보면 누구나 이런 고민을 하게 됩니다.

•

강의는 다 들었지만 막상 손이 안 움직이고,

•

복습을 하려 해도 무엇을 다시 봐야 할지 모르겠고,

•

질문할 곳도 없고,

•

유튜브는 결국 정답을 따라 치는 것밖에 안 되는 것 같고.

문제는 ‘연습’이 빠졌기 때문입니다.

단순히 강의를 듣는 것만으로는 실력이 늘지 않습니다.

실제 문제를 풀고, 고민하고, 직접 구현해보는 시간이 반드시 필요합니다.

그래서, 얌얌코딩 코칭은 다릅니다.

그냥 가르치지 않습니다.

스스로 설계하고, 코딩할 수 있게 만듭니다.

얌얌코딩 코칭에서는 단순한 예제가 아닌,

스스로 문제를 분석하고 구현해야 하는 연습문제를 제공합니다.

이 연습문제들은 다음과 같은 역량을 키우기 위해 설계되어 있습니다:

•

문제를 스스로 쪼개고 설계하는 힘

•

다양한 조건을 만족시키는 실제 구현 능력

•

기능 단위가 아닌, 프로그램 단위로 사고하는 습관

•

마침내 자신의 힘으로 코드를 끝까지 작성하는 경험

지금 필요한 건 더 많은 강의가 아닙니다.

코드를 스스로 완성해 나가는 훈련,

그것이 지금 실력을 끌어올릴 가장 현실적인 방법입니다.

자세한 안내 보기: 프리미엄 코칭 안내 바로가기

또는 카카오톡 상담방: 얌얌코딩 상담방