백준 13325번 - 이진 트리 🌲

🔗 문제 링크: https://www.acmicpc.net/problem/13325

📝 문제 요약

• 높이 N의 완전 이진 트리에서 루트부터 리프까지의 경로의 가중치 합이 모두 같도록 만드려고 합니다.
• 각 간선의 초기 가중치가 주어지며, 일부 간선의 가중치를 증가시킬 수 있습니다.
• 모든 리프 노드까지의 경로 가중치 합이 동일해지도록 하기 위한 최소의 증가 비용을 출력합니다.
  

  ---

🧷 문제 분류

• 트리
• 누적합
  

  ---

📦 제출 정보

🔗 소스코드: GitHub - cbkpar/BOJ/boj_13325.cpp

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int iN;
	cin >> iN;
	int iTotal = 0;
	for (int i = 1; i <= iN; ++i)
	{
		iTotal += 1 << i;
	}
	iTotal += 2;

	long long lAns = 0;

	vector<long long> vecNum(iTotal, 0);
	for (int i = 2; i < iTotal; ++i)
	{
		cin >> vecNum[i];
		lAns += vecNum[i];
	}

	long long lMax = 0;
	for (int i = 2; i < iTotal; ++i)
	{
		int iNext = i * 2;
		if (iNext >= iTotal)
		{
			lMax = max(lMax, vecNum[i]);
			continue;
		}

		vecNum[iNext] += vecNum[i];
		vecNum[iNext + 1] += vecNum[i];
	}

	for (int i = iTotal - 1; i >= 2; --i)
	{
		if (i * 2 >= iTotal)
		{
			vecNum[i] = lMax - vecNum[i];
			continue;
		}

		vecNum[i] = min(vecNum[i * 2], vecNum[i * 2 + 1]);
		vecNum[i * 2] -= vecNum[i];
		vecNum[i * 2 + 1] -= vecNum[i];
	}

	for (int i = 2; i < iTotal; ++i)
	{
		lAns += vecNum[i];
	}

	cout << lAns << "\n";
	return 0;
}

💡 풀이 방법

🔍 문제 접근

• 루트 노드부터 각 리프 노드까지의 경로의 가중치 최대값 계산 후 다른 경로의 부족한 부분만큼 보정.
• 각 노드에서 자식 노드로 누적합을 전파하고, 자식에서 부모방향으로 차이를 보정해주며 최소 증가량을 계산.

🧠 핵심 아이디어

• 전방 탐색을 통해 자식에게 누적합을 전파한 후, 경로에 부족한 값을 역으로 채워주는 방식.
• 모든 경로 중 가장 큰 누적합을 기준으로 남은 간선 가중치를 계산하고 누적합니다.

⚙️ 구현 방식

1. 트리의 간선 수는 2N+1 - 2개이므로 이만큼 입력을 받아 vector에 저장합니다.
2. 자식 노드로 누적합을 더해주며 최대 경로 길이를 계산합니다.
3. 계산 된 밑에서 위로 올라가면서 필요한 가중치의 값을 구한다.

✅ 시간 복잡도

• 트리 탐색은 O(N)이며, 완전 이진 트리의 노드 수는 2N+1 - 1이므로 충분히 빠르게 수행됩니다.

🧪 예제 입력 / 출력

📘 예제 1

2
2 2 2 1 1 3

15

📙 예제 2

1
1 1000

2000

📘 예제 3

3
1 2 1 3 2 4 1 1 1 1 1 1 1 1

27

📙 예제 4

2
1 1000 1 1 1000 1000

5001

백준 13018번 - 특이한 수열

🔗 문제 링크: https://www.acmicpc.net/problem/13018

📝 문제 요약

• 수열 A의 길이는 n
• 1 이상 n이하의 정수가 빠짐없이 모두 등장해야 하며, 각 수는 한 번만 등장해야 함
• 1 ≤ i ≤ n 인 i에 대해 gcd(i, A[i]) > 1을 만족하는 i가 정확히 k개여야 함
  

  ---

  
  

🧷 문제 분류

• 애드혹
• 정수론
  

  ---

  
  

📦 제출 정보

🔗 소스코드: GitHub - cbkpar/BOJ/boj_13018.cpp

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int iN, iK;
	cin >> iN >> iK;

	if (iK == iN)
	{
		cout << "Impossible" << "\n";
		return 0;
	}

	vector<int> vecNum(iN + 1, 0);
	for (int i = 1; i <= iN; ++i)
	{
		vecNum[i] = i;
	}

	int iRest = iN - 1 - iK;

	for (int i = 2; i <= iN; i += 2)
	{
		if (iRest < 2)
		{
			break;
		}
		iRest -= 2;
		swap(vecNum[i], vecNum[i + 1]);
	}

	if (iRest == 1)
	{
		swap(vecNum[1], vecNum[iN]);
	}

	for (int i = 1; i <= iN; ++i)
	{
		cout << vecNum[i] << (i == iN ? "\n" : " ");
	}
	return 0;
}

💡 풀이 방법

🔍 문제 접근

• 인접한 수를 적절히 교환하여 문제를 해결.
• 가능하지 않은 경우 Impossible을 출력해야 하며, 가능한 경우 그 수열을 출력.

🧠 핵심 아이디어

• 1은 항상 gcd값이 1이 나온다.
• k 값이 n과 같은 경우는 Impossible 처리.
• gcd(n, n+1) = 1이라는 원리를 이용 

⚙️ 구현 방식

1. 1부터 N까지의 수를 초기 배열에 채운다. -> gcd(i,arr[i]) 만족하는 개수는 N-1개
2. N-1개에서 K개를 만족하도록 바꾸기 위한 개수를 계산한다 (N-1-K) = R개
3. 배열의 2번째부터 2칸씩 뛰며 순회하며 R이 2 이상 일경우 배열의 다음 값과 자리를 바꾸고 R을 2 빼준다.
4. 최종적으로 R값이 1 남은 경우, 처음과 마지막을 swap.
5. 최종 배열을 출력.

✅ 시간 복잡도

• O(N): 한 번의 루프만으로 swap 진행
• 입력 크기가 작아 실질적으로 상수 시간 수준

백준 32292번 - ABB to BA (Easy) 🔤

🔗 문제 링크: https://www.acmicpc.net/problem/32292

📝 문제 요약

• 문자열 S가 주어집니다.
• 문자열 S는 'A'와 'B'로만 구성되어 있습니다.
• 문자열중 ABB는 BA로 치환된다. (연쇄 가능)

  ---

  
  

🧷 문제 분류

• 문자열
• 브루트포스

📦 제출 정보

🔗 소스코드: GitHub - cbkpar/BOJ/boj_32292.cpp

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int iT;
	cin >> iT;
	for (int t = 1; t <= iT; ++t)
	{
		int iN;
		cin >> iN;

		string strWord;
		cin >> strWord;

		while (true)
		{
			if (strWord.find("ABB") == string::npos)
			{
				break;
			}
			strWord.replace(strWord.find("ABB"), 3, "BA");

		}
		cout << strWord << "\n";
	}
	return 0;
}

💡 풀이 방법

🔍 문제 접근

• "ABB"를 "BA"로 바꾸는 작업을 반복하여 더 이상 "ABB"가 없을 때 문자열을 출력하는 문제.
• 한 번의 치환이 또 다른 "ABB" 패턴을 생성할 수 있으므로 반복적인 탐색과 치환이 필요합니다.

🧠 핵심 아이디어

• find() 함수를 사용하여 문자열에서 "ABB"를 찾고, replace()로 "BA"로 치환합니다.
• 이 과정을 "ABB"가 더 이상 발견되지 않을 때까지 반복합니다.
• 모든 테스트 케이스에 대해 위의 작업을 수행한 후 최종 문자열을 출력합니다.

⚙️ 구현 방식

1. 테스트 케이스 개수 T를 입력받습니다.
2. 각 테스트 케이스마다 문자열을 입력받습니다.
3. while 반복문을 사용해 문자열에 "ABB"가 존재하는지 확인하고, 있다면 replace를 수행합니다.
4. 최종 변환된 문자열을 출력합니다.

✅ 시간 복잡도

• 각 find(), replace() 연산은 O(N)
• 반복 횟수를 K라고 하면 전체 시간 복잡도는 O(K × N)
• 실제 데이터에선 K가 작기 때문에 충분히 빠르게 동작합니다

  ---

🧪 예제 입력 / 출력

📘 예제 1

3
3
ABB
9
ABABABBBB
12
AAAAAABBBBBB

BA
BAABA
AAAABABA

백준 9335번 - 소셜 광고 📢

🔗 문제 링크: https://www.acmicpc.net/problem/9335

📝 문제 요약

• 모든 사용자가 광고를 볼 수 있도록 게시할 최소의 광고의 수 계산
• 친구의 광고는 시청 할 수 있다
• A와 B가 친구 이면 B도 A와 친구이다
• A와 B, B와 C가 친구 여도 A와 C는 친구가 아닐 수 있다

🧷 문제 분류

• 브루트포스
• 비트마스킹

  ---

  
  

📦 제출 정보

🔗 소스코드: GitHub - cbkpar/BOJ/boj_9335.cpp

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int iT;
	cin >> iT;
	for (int t = 1; t <= iT; ++t)
	{
		int iN;
		cin >> iN;

		vector<int> vecNum(iN, 0);
		for (int i = 0; i < iN; ++i)
		{
			int iFriend;
			cin >> iFriend;
			vecNum[i] = 1 << i;
			for (int j = 0; j < iFriend; ++j)
			{
				int iFriendNum;
				cin >> iFriendNum;
				vecNum[i] |= (1 << (iFriendNum - 1));
			}
		}

		int iAns = iN;
		for (int i = 0; i < (1 << iN); ++i)
		{
			int iTemp = i;
			int iCount = 0;
			int iConnected = 0;
			for (int j = 0; j < iN; ++j)
			{
				if (iTemp % 2 == 1)
				{
					++iCount;
					iConnected |= vecNum[j];
				}
				iTemp /= 2;
			}

			if (iConnected == (1 << iN) - 1)
			{
				iAns = min(iAns, iCount);
			}
		}

		cout << iAns << "\n";
	}
	return 0;
}

💡 풀이 방법

🔍 문제 접근

• 각 사람의 광고 도달 범위를 비트마스크로 표현합니다.
• 전체 사람을 0부터 N-1까지 인덱스로 보고, 각 인덱스마다 자신과 친구들이 도달 가능한 사람을 비트로 나타냅니다.

🧠 핵심 아이디어

• vecNum[i]는 i번째 사람이 광고를 본다면, 영향을 받는 사람들의 집합을 비트마스크로 표현한 것입니다.
• 이후 가능한 모든 사람 선택의 조합 (2^N개)을 순회하며, 해당 조합으로 광고를 보낼 경우 전체 사람에게 도달 가능한지 확인합니다.
• 전체 사람에게 도달할 수 있는 최소 사람 수를 구하는 것이 목표입니다.

⚙️ 구현 방식

1. 각 사람에 대해 자신을 포함한 친구 목록을 비트마스크로 구성
2. 비트마스크 조합 (0부터 2^N-1까지) 을 순회하면서 해당 조합으로 도달 가능한 사람들을 계산
3. 모든 사람에게 도달할 수 있다면 (즉, 비트 OR 결과가 (1 << N) - 1), 최소 인원 수를 갱신

✅ 시간 복잡도

• 총 조합 수는 2^N이며, 각 조합에 대해 N번 반복 → O(N × 2^N)
• N ≤ 20 이하이므로 브루트포스로 충분히 해결 가능

🧪 예제 입력 / 출력

📘 예제 1

2
5
4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4
5
2 4 5
2 3 5
1 2
2 1 5
3 1 2 4

1
2

백준 33702번 - 비밀번호 🔐

🔗 문제 링크: https://www.acmicpc.net/problem/33702

📝 문제 요약

3×3 키패드가 주어지고, 첫 입력값으로 시작할 숫자 K가 주어진다.
비밀번호를 입력할 때는 바로 직전에 누른 버튼과 상하좌우로 인접한 버튼만 누를 수 있다.
이 규칙을 지키며 생성할 수 있는 가능한 비밀번호 개수를 구하는 문제이다.

🧷 문제 분류

수학

📦 제출 정보

🔗 소스코드: GitHub - cbkpar/BOJ/boj_33702.cpp

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int iK;
    cin >> iK;

    if (iK % 2 == 0)
    {
        cout << "0" << "\n";
    }
    else
    {
        cout << "8" << "\n";
    }

    return 0;
}

💡 풀이 방법

• 중복 없이 모든 가능한 경로 탐색
• 방문 체크를 통해 한 경로 내에서 같은 숫자를 반복 사용하지 않도록 처리
• DFS를 사용한 정석적인 방법도 있지만, 위치별 특성을 고려해 단순하게 계산할 수도 있다

🔢 숫자별 시작 위치에 따른 경로 수 분석

1로 시작했을 때

• 2로 가는 경우 총 4가지
  • 경로 예시: 1→2→3→6→5→4→7→8→9
  • 예시 경로들: 123654789, 123698745, 123698547, 125478963
• 4로 가는 경우도 동일하게 4가지
• 총 8가지 경로 가능
• ※ 3, 7, 9도 1처럼 구석(코너)이기 때문에 동일하게 8가지 가능

2로 시작했을 때

• 1 또는 3으로 가는 경우, 나머지를 모두 채우면 다시 돌아올 수 없음
• 5로 가는 경우도 1 또는 3을 다시 방문해야 하므로 실패
• 총 0가지

5로 시작했을 때

• 상하좌우(2, 4, 6, 8)로 이동 가능
• 시계방향 또는 반시계방향으로 한 바퀴 도는 경로가 존재
• 총 8가지

🧪 예제 입력 / 출력

📘 예제 1

3

8

📙 예제 2

8

0

문제 : https://www.acmicpc.net/problem/32515

문제요약

정훈이와 이안이 각각 보낸 문자열을 통한 새로운키를 통해 태균이가 도청하고 있는지 확인

문제 분류

구현

C++

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_32515.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int iLen;
	cin >> iLen;

	string strJQbit, strJKey, strEQbit, strEKey;
	cin >> strJQbit >> strJKey >> strEQbit >> strEKey;

	for (int i = 0; i < iLen; ++i)
	{
		if (strJQbit[i] == strEQbit[i])
		{
			if (strJKey[i] != strEKey[i])
			{
				cout << "htg!" << "\n";
				return 0;
			}
		}
	}

	for (int i = 0; i < iLen; ++i)
	{
		if (strJQbit[i] == strEQbit[i])
		{
			cout << strJKey[i];
		}
	}
	cout << "\n";

	return 0;
}

문제 풀이

정훈이와 이안이의 기저선택을 순서대로 비교하며 같을 경우 생성되는 키가 동일한지 확인

기저선택을 순서대로 비교하며 같은 큐비트의 경우 키가 다를 경우 도청

예제 1)

8
HHVHVVHV
00100110
HVHHHVVV
01100100

0010

새로생성 되는 키 0010 일치 -> 키 출력

예제 2)

4
HHVH
0101
VHVV
1001

htg!

새로운 키의 불일치 -> 태균이의 도청 -> htg! 출력

문제 : https://www.acmicpc.net/problem/27468

문제 요약

1~N 까지 정확히 한번 사용

인접한 세수 A, B, C가 |A-B| = |B-C| * 2 혹은 |A-B| = |B-C| * 0.5를 만족

문제 분류 : 애드혹

C++

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_27468.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int iN;
	cin >> iN;

	cout << "YES" << "\n";
	if (iN % 4 == 2)
	{
		for (int i = 1; i <= iN; ++i)
		{
			if (i % 4 == 1) cout << (i + 1);
			if (i % 4 == 2) cout << (i - 1);
			if (i % 4 == 3) cout << i;
			if (i % 4 == 0) cout << i;
			cout << (i == iN ? "\n" : " ");
		}
	}
	else
	{
		for (int i = 1; i <= iN; ++i)
		{
			if (i % 4 == 1) cout << i;
			if (i % 4 == 2) cout << (i + 1);
			if (i % 4 == 3) cout << (i - 1);
			if (i % 4 == 0) cout << i;
			cout << (i == iN ? "\n" : " ");
		}
	}

	return 0;
}

문제 풀이

주어진 N을 4 단위로 생각한다.

주어진 N을 4로 나머지연산했을 때 2인 경우

2+4x, 1+4x, 3+4x, 4+4x (x = 0,1,2,3,...)를 반복해서 출력한다.

-> [2 1 3 4] [6 5 7 8] [10 9] 

-> 간격 : 1 2 1 2 1 2 1 2 1 로 반복되게 된다.

주어진 N을 4로 나머지연산했을 때 2가 아닌경우

1+4x, 3+4x, 2+4x, 4+4x (x = 0,1,2,3,...)를 반복해서 출력한다.

-> [1 3 2 4] [5 7 6 8] [9 11 10 12] 

-> 간격 : 2 1 2 1 2 1 2 1 2 1 2 로 반복되게 된다.

문제 : https://www.acmicpc.net/problem/6568

문제 요약 : 프로그램 종료 후 가산기의 값 출력

C++

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_6568.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Fetch(string str)
{
	int iSum = 0;
	for (char ch : str)
	{
		iSum <<= 1;
		iSum += ch - '0';
	}
	return iSum;
}

void Decode(const int command, int& _operator, int& _operand)
{
	_operator = command >> 5;
	_operand = command % 32;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vecMemory(32, 0);
	int iIndex = 0;

	string strCommand;
	while (cin >> strCommand)
	{
		vecMemory[iIndex] = Fetch(strCommand);
		iIndex = (iIndex + 1) % 32;

		if (iIndex == 0)
		{
			int iPC = 0;
			int iSum = 0;

			while (iPC >= 0)
			{
				int iTempPC = iPC;
				int iOperator, iOperand;
				Decode(vecMemory[iPC], iOperator, iOperand);
				iPC = (iPC + 1) % 32;
				switch (iOperator)
				{
				case 0: vecMemory[iOperand] = iSum; break;
				case 1: iSum = vecMemory[iOperand]; break;
				case 2: iPC = (iSum == 0 ? iOperand : iPC); break;
				case 3: break;
				case 4: if (--iSum < 0) iSum += 256; break;
				case 5: iSum = (++iSum) % 256; break;
				case 6: iPC = iOperand; break;
				case 7: iPC = -1; break;
				}
			}

			for (int i = 7; i >= 0; --i)
			{
				cout << ((iSum & (1 << i)) == (1 << i) ? "1" : "0");
			}
			cout << "\n";
		}
	}
	return 0;
}

시스템 프로그래밍 공부에 좋은 문제인 것 같아서 풀어 보았다.

우선 받은 명령어를 RAM 에 적재하듯이 올려준다. (Load)

RAM과 CPU에서는 크게 Fetch - Decode - Execute 가 일어나게 된다.

이를 기반으로 알고리즘을 작성하면 된다.

1. 해당 PC가 가리키는 명령어를 operator와 operand로 분리한다.

2. 명령어 해석후에 PC레지스터 의 값을 1 증가시키며 이때 32보다 커지면 0으로 만들어 준다.

3. operator에 따른 명령을 수행한다.

이 문제에서 눈여겨 볼 점은 명령을 통해 직접 계산을 하였을 경우

총 5비트밖에 사용하지 못하기 때문에 32가 넘어가는 숫자에 대한 연산을 할 수 없지만

값의 주소를 이용해 연산 횟수는 늘지만 8비트 모두 연산에 사용할 수 있다.

이 방법은 Indirect 모드라고 볼 수 있다.