최근 저는 절실한 마음으로 본격적인 취업 준비에 돌입했습니다.
그중에서도 삼성전자 SW역량테스트를 준비하며, SW Expert Academy에 있는 문제들을 집중적으로 풀고 있습니다. 목표는 하루에 D4 이상 난이도의 문제를 1~2개씩 풀어가는 것. 하지만, 시작부터 만만치 않은 벽을 만났습니다. 바로, 시간 복잡도와 연산량이 어마어마한 문제였죠.
전략1
그동안 문제를 풀 때는 다음과 같은 흐름으로 접근해왔습니다:
- 문제를 제대로 읽기
- 정답을 맞추기
- 시간 최적화하기
하지만 이 문제를 만나고 나서, 전략을 근본적으로 바꾸기로 결심했습니다.
전략2
이 문제를 통해 얻은 가장 큰 교훈은 "정답을 맞추는 것과 시간 최적화를 동시에 고려해야 한다"는 점입니다.
단순히 브루트포스로 정답을 먼저 맞추고 최적화를 고민하는 순서로는 절대 시간 제한을 만족할 수 없습니다.
문제의 조건과 난관
- 컴퓨팅 타임: 10초
- 보통
O(10^8)정도의 연산이 1초를 넘지 않는다고 가정했을 때, 총 연산량은 약10^9이하로 제한됨 - 테스트 케이스 수: 20개
- 각 테스트케이스에서 후보 시작점을 탐색하는 데만
O(N × 4M)시간 소모
→ 이 부분만 해도 약8 × 10^7소모
따라서 암호 블록 탐색 및 디코딩을 위한 시간 여유는 단 10~20 정도 뿐이었죠.
4가지 핵심 pruning 전략
시간 최적화를 위해 아래와 같은 pruning을 반드시 적용했습니다:
1. 암호 후보는 반드시 0으로 시작해서 1로 끝난다
→ 이 특성을 이용해 후보 블록 시작점 탐색을 대폭 줄일 수 있음
2. 암호의 합은 두께(thickness)의 3배 혹은 5배
→ 해당 조건을 만족하지 않으면 블록 자체를 무시
3. 한 번 암호 블록을 발견하면, 그 이후는 전체 thickness 만큼 건너뛴다
→ 중복 계산 제거 (탐색 pruning)
4. 암호 비교는 반드시 부분합(partial sum) 으로 처리
→ 일일이 비교하지 않고 누적합/정규화로 비교 연산 간소화
어제 저녁에 시작해 오늘 저녁에 AC
문제에 할당된 시간을 쪼개 쓰고, 탐색 공간을 최대한 줄이면서 결국 정답에 도달할 수 있었습니다. 이번 경험을 통해 단순히 풀기만 해서는 안 되고, 알고리즘 설계 자체부터 제한 조건을 고려해야 한다는 것을 다시금 느꼈습니다.
처음엔 하루 1~2문제 정도면 괜찮겠지, 했지만 현실은 냉정했습니다.
이 문제를 통해 겸손함을 배웠고, 앞으로는 무조건 정답보다 "조건 내에서의 정답"을 추구하는 실력을 키워야겠다고 다짐했습니다.
앞으로 더 열심히 달려보겠습니다.🔥 🔥 🔥 🔥 🔥
코드
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <unordered_map>
#include <cstring>
using namespace std;
int T, N, M;
vector<string> A;
map<char, string> hex2bin;
vector<string> str_blocks[10] = {
{"000", "11", "0", "1"}, // 0
{"00", "11", "00", "1"}, // 1
{"00", "1", "00", "11"}, // 2
{"0", "1111", "0", "1"}, // 3
{"0", "1", "000", "11"}, // 4
{"0", "11", "000", "1"}, // 5
{"0", "1", "0", "1111"}, // 6
{"0", "111", "0", "11"}, // 7
{"0", "11", "0", "111"}, // 8
{"000", "1", "0", "11"} // 9
};
vector<int> partial_sum;
vector<unordered_map<int, int>> ps_encoded_digits;
vector<int> get_parsed(string& str, int column, int thickness){
// precheck
for(int i = 0; i < 8; i++){
int offset = column + i * 7 * thickness; // start, 포함
int offset_end = column + (i + 1) * 7 * thickness; // end, 미포함
int ps = partial_sum[offset_end] - partial_sum[offset];
if((ps != 3 * thickness) && (ps != 5 * thickness))
return {};
}
vector<int> vt;
for(int i = 0; i < 8; i++){
int offset = column + i * 7 * thickness; // start, 포함
bool pushed = false;
for(int j = 0; j < 10; j++){
bool is_same = true;
for(auto [k, v]: ps_encoded_digits[j]){
if((partial_sum[offset + k * thickness] - partial_sum[offset]) != v * thickness){
is_same = false;
break;
}
}
if(is_same){
vt.push_back(j);
pushed = true;
break;
// cout << encoded_digit << " " << j << endl;
}
}
if(!pushed)
return {};
}
return vt;
}
bool get_check(vector<int>& vt){
int evens = vt[1] + vt[3] + vt[5] + vt[7];
int odds = vt[0] + vt[2] + vt[4]+ vt[6];
return (evens + odds * 3) % 10 == 0;
}
int get_val(vector<int>& vt){
int ret = 0;
for(int i = 0; i < vt.size(); i++){
ret += vt[i];
}
return ret;
}
void print_vt(vector<int>& vt){
for(int i = 0; i < vt.size(); i++)
cout << vt[i] << " ";
cout << endl;
return;
}
void init_hex2bin(){
hex2bin['0'] = "0000";
hex2bin['1'] = "0001";
hex2bin['2'] = "0010";
hex2bin['3'] = "0011";
hex2bin['4'] = "0100";
hex2bin['5'] = "0101";
hex2bin['6'] = "0110";
hex2bin['7'] = "0111";
hex2bin['8'] = "1000";
hex2bin['9'] = "1001";
hex2bin['A'] = "1010";
hex2bin['B'] = "1011";
hex2bin['C'] = "1100";
hex2bin['D'] = "1101";
hex2bin['E'] = "1110";
hex2bin['F'] = "1111";
return;
}
string to_binary(string str){
string ret = "";
for(int i = 0; i < str.size(); i++){
ret += hex2bin[str[i]];
}
return ret;
}
void init_partial_sum(string& str){
partial_sum.resize(str.size() + 1);
int sum = 0;
for(int i = 0; i < str.size(); i++){
if(str[i] == '1'){
sum++;
}
partial_sum[i + 1] = sum;
}
return;
}
void init_ps_encoded_digits(){
ps_encoded_digits.resize(10);
for(int i = 0; i < 10; i++){
int idx = 0;
int sum = 0;
for(int j = 0; j < 4; j++){
idx += str_blocks[i][j].size();
if(str_blocks[i][j][0] == '1')
sum += str_blocks[i][j].size();
ps_encoded_digits[i][idx] = sum;
}
}
return;
}
int main() {
init_hex2bin();
init_ps_encoded_digits();
cin >> T;
for(int t = 1; t <= T; t++){
cin >> N >> M;
A.clear();
A.resize(N);
for(int i = 0; i < N; i++){
string str;
cin >> str;
A[i] = to_binary(str);
}
M = 4 * M;
set<vector<int>> answers;
for(int i = 0; i < N; i++){
partial_sum.clear();
init_partial_sum(A[i]);
for(int j = 0; j < M; j++){
bool check = false;
if(A[i][j] == '1')
continue;
for(int thickness = 1; thickness <= 35; thickness++){
int offset_end = j + 56 * thickness; // 미포함
if (offset_end >= M)
break;
if(A[i][offset_end - 1] == '0')
continue;
vector<int> parsed_str = get_parsed(A[i], j, thickness);
if(parsed_str.size() == 0)
continue;
// print_vt(parsed_str);
check = get_check(parsed_str);
if(check)
answers.insert(parsed_str);
j += 56 * thickness - 1;
break;
}
}
}
int sum = 0;
for(vector<int> ele: answers){
sum += get_val(ele);
}
cout << "#" << t << " " << sum << endl;
}
return 0;
}