백준 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 로 반복되게 된다.

프로그래머스에서 이번 데브매칭에서 PCCP 기회를 주어서 응시하게 되었다.

일반적인 데브매칭에서는 모바일로 문제 푸는 모습만 나오게 촬영하면 되었지만

이번 시험에서는 규정이 상당히 까다로웠다.

큰 차이점은 주변환경을 촬영해야하는 것과 웹캠을 사용해야하는 것

또한 신분증도 촬영해야 하는데 사전테스트에서 미리 등록해 뒀었는데 다시 촬영할 필요가 없었다.

웹캠을 사용해야 하기때문에 부득이하게 노트북으로 테스트를 응시하였다.

(작은 모니터로 푸는게 쉽지 않았다.)

시험 1시간 전 입장가능하며 20분 전에는 입장이 불가능하다.

시험입장 후 대기하는 동안 중간중간 공지사항이 올라오며 따라서 이행하면 된다.

시험 후기

문제 난이도는 아무래도 인터넷 검색이나 IDE가 사용이 금지되어있기 때문에

고난도의 문제는 내지 않는 것으로 보였다.

기본적인 유형과 애드혹스러운 문제에 충실해서 내는 것 같았다.

기본 채점셋은 공개해 주지만 히든 테스트 셋은 공개해주지 않아 정답이 맞는지 긴가 민가 하였다.

시험 팁

시험시간은 2시간이지만 시험문제는 4개 이므로 시간 배분을 적절하게 해서 처리해야 한다.

모르는 문제에 계속 시간을 투자하지 말고 다음 문제로 넘어가서 풀다가 돌아오는 게 더 좋을 수도 있다.

실행 결과 테스트가 모두 맞았다고 해서 정답은 아니다 예외처리하지 못했거나

문제에서 요구하는 시간복잡도 내에 풀었는지 다시 한번 확인하는 게 좋다. (지문을 꼼꼼히 읽자)

IDE가 사용불가능하므로 자동완성이 되지 않기 때문에 응시언어의 자료구조의 함수들은 어느 정도 외워가는 게 좋다.

ex) insert, push, push_back, 인지 헷갈려 컴파일 에러가 나는 경우가 있다.

정 모를 경우 위에 레퍼런스를 눌러보면 해당자료구조의 기능들이 자세하게 나타나있다.

시험 결과

그래도 부분점수를 통해 LV.4를 턱걸이로 넘을 수 있었던 것 같다.

부족한 부분을 다시금 깨달을 수 있었던 좋은 시험이었다.