단백질폴딩은 원본 자료에 grader만 공개돼 있고 검증된 통과 코드가 없다. 따라서 이 페이지는 — 라인 단위 코드 해부 대신, rotate()의 회전 변환과 verify()의 인접 점수 합을 읽고 베스트 해법을 설계하며 정당성을 논증한다. 90도 회전 행렬이 왜 좌표를 정수로 유지하는지, fold_amino·fold_element의 접기 연산이 어떤 탐색 공간을 만드는지, 점수 H1·C2·O5·N10·S30의 비대칭이 왜 "S·N 밀집"을 강제하는지를 설계 의사코드와 C++ 스케치로 제시한다. 추측이 들어가는 곳은 설계 제안으로 표시한다.
단백질폴딩은 통과 코드가 없다. 그러나 채점기 verify()와 회전 엔진 rotate()·fold_*()가 완전히 공개돼 있고, 좋은 해법의 형태는 거기서 연역할 수 있다. 먼저 점수와 제약을 정확히 적는다.
점수 식을 읽는 것이 전부다. 채점기는 100³ 공간을 훑으며, 각 원소가 6방향(±x,±y,±z) 이웃과 만날 때 두 원소 가중치의 곱을 더한다. 인접한 두 원소가 점수에 2·w(e)·w(e')씩 기여한다(양쪽에서 한 번씩). 가중치가 곱해지므로 — 비싼 원소끼리 붙을 때 점수가 폭발한다.
가중치를 보라: S는 30, N은 10, O는 5인데 H는 1, C는 2다. S 두 개가 인접하면 2·30·30 = 1800점, H 두 개는 2·1·1 = 2점 — 900배 차이다. 게다가 아미노산 종류 20개를 보면 S는 거의 없고(HSCHH…·CHHHSCHH… 등 일부), N은 사슬마다 한둘씩 박혀 있다. 즉 희소하고 비싼 원소(S, N)를 서로 맞붙이는 것이 점수의 거의 전부다. H·C는 사실상 점수에 무의미하다.
그래서 베스트 해법은 두 단계로 설계된다.
fold_amino·fold_element가 사슬을 어떻게 변형하는지, 그 결과 도달 가능한 형태(conformation) 공간이 무엇인지 파악한다.핵심 통찰은 1단계가 "어떤 변형이 가능한가"(연산), 2단계가 "어떤 변형이 점수를 높이는가"(탐색)를 푼다는 점이며, 둘 다 점수의 곱-비대칭에 종속된다.
30·30 ≫ 30·1 ≫ 1·1. 그러므로 H·C 같은 싼 원소의 배치는 거의 무시하고, S·N 같은 희소·고가 원소가 서로 인접하도록 모든 접기 자원을 집중하라.
설계의 정당성을 논증하려면 먼저 접기 연산이 무엇을 보존하는지 알아야 한다. 점수보다 우선, verify()는 어떤 원소든 좌표가 [0,100)를 벗어나거나 두 원소가 같은 칸을 공유하면 false를 반환해 점수를 0으로 만든다.
채점기 rotate()는 90도 회전만 수행한다. X축 회전을 보면 y' = ±-(z−bz)+by, z' = ±(y−by)+bz — 모두 정수 덧셈·부호 반전뿐이다. 따라서 회전 전 좌표가 정수면 회전 후도 정수다. 격자 위 점은 회전해도 격자 위에 머문다.
또한 90도 회전은 거리를 보존하는 등거리변환(isometry)이다 — 회전축 위의 기준 원소(baseElem)와 다른 원소 사이 거리, 그리고 인접했던 두 원소(결합으로 이어진 사슬)는 회전 후에도 인접한 채 남는다. 사슬의 연결성은 어떤 접기를 해도 깨지지 않는다.
축 a ∈ {x,y,z}에 대한 90도 회전을 기준점 b 둘레로 적용하면, 회전축에 수직인 두 좌표가 (p, q) ↦ (b_p − dir·(q−b_q),\; b_q + dir·(p−b_p))로 바뀐다(dir = ±1은 시계/반시계). 이는 행렬 [[0,−1],[1,0]](또는 그 역)을 평행이동한 것으로, determinant 1의 직교변환이다.
2×2 회전행렬 R_{90°} = [[0,−1],[1,0]]의 모든 성분은 \{0, 1, −1\}이다. 정수 벡터에 이 행렬을 곱하면 결과의 각 성분은 입력 정수들의 부호 있는 합 — 다시 정수다. 채점기 rotate()의 식은 정확히 이 곱에 기준점 평행이동 −R b + b를 더한 형태이며, 평행이동 항도 정수다.
따라서 초기 배치(init()이 만든 정수 격자)에서 출발해 fold_*를 아무리 적용해도 모든 원소 좌표는 정수로 유지된다. verify()가 gSpace[z][y][x] 정수 배열로 충돌을 검사할 수 있는 것은 이 정수 무결성 덕분이다. 충돌과 점수는 모두 정수 격자 위에서 정의된다.
채점기는 두 종류의 접기를 제공한다. fold_amino(aminoNum, front, axis, anticlockwise)는 아미노산 단위로 접는다 — aminoNum번 아미노산의 connector 원소를 회전축으로, 그 앞쪽(front=true) 또는 뒤쪽 아미노산 전체를 통째로 90도 돌린다. fold_element(aminoNum, elementNum, …)는 원소 단위로, 한 아미노산 안에서 특정 원소를 축으로 그 일부를 돌린다.
아미노산 사슬은 일렬로 연결된 구조다. fold_amino는 사슬을 한 connector 지점에서 둘로 가르고 한쪽 절반을 회전한다 — 마치 경첩(hinge)처럼. fold_element도 같은 원리를 한 아미노산 내부에 적용하되, 회전 대상 구간에 다른 connector가 있으면 회전을 거부한다(코드의 if (connector == true) return;).
이 거부 규칙의 의미: connector는 아미노산을 잇는 관절이므로, 한 fold_element 회전이 두 개 이상의 관절을 가로지르면 사슬 구조가 모순된다. 그래서 접기는 항상 "하나의 관절을 중심으로 한쪽을 돌리기"라는 잘 정의된 연산만 허용한다. 탐색 공간은 이 관절들의 회전 각도 조합 — 유한하지만 거대한 이산 공간이다.
이 문제에는 호출 비용이 없다 — process()가 접기를 끝낸 뒤 verify()가 한 번에 채점한다. 따라서 "비용"은 점수 함수 그 자체이고, 설계의 모델은 다음과 같다.
점수 식을 펼치면 — 인접쌍 중 S와 N이 관여하는 쌍만이 의미 있는 점수를 낸다. H·C 인접은 전체 점수의 소수점 이하 노이즈다. 그러므로 설계의 핵심 결정은 "S·N 원소들을 어떻게 6방향 인접하도록 모을까"다.
전체 탐색은 불가능하다 — 관절이 수십 개고 각 관절이 3축×4각도면 조합이 천문학적이다. 두 가지 설계 전략을 제안한다. 설계 제안
아래는 그리디 접기의 설계 스케치다. 실제 통과 코드가 아니라 — verify의 점수 식에서 연역한 의사코드에 가까운 C++다.
// 현재 배치의 인접 점수를 계산한다 (verify의 점수 식과 동일).long long evalScore() { clearSpace(); if (!placeAll()) return -1; // 충돌·범위이탈이면 무효 long long s = 0; for (each 원소 e at (x,y,z)) for (each 6방향 이웃칸 (nx,ny,nz)) s += weight(e) * weight(space[nz][ny][nx]); // 곱 누적 return s;}// 점수를 가장 많이 올리는 fold를 반복 적용한다.void greedyFold() { while (1) { long long base = evalScore(), best = base; Fold bestFold = NONE; for (each 후보 fold f) { // 관절×축×각도×front apply(f); // fold_amino / fold_element long long s = evalScore(); apply(inverse(f)); // 되돌리기 (90도 3번 = 역회전) if (s > best) { best = s; bestFold = f; } } if (bestFold == NONE) break; // 개선 fold 없음 → 국소최적 apply(bestFold); // 최선 fold 확정 }}
greedyFold의 핵심은 "fold를 적용해 점수를 본 뒤 되돌린다"는 것이다. 90도 회전은 4번 적용하면 제자리로 돌아오므로, 한 fold의 역연산은 같은 축·같은 관절로 3번 더 회전(또는 반대 방향 1번)이다. Theorem 1의 정수 무결성 덕분에 되돌린 좌표는 원래 좌표와 정확히 일치한다 — 부동소수 오차가 없다. 모든 후보 fold를 이렇게 시험한 뒤 가장 좋은 것만 확정하면, 매 단계가 점수 단조 증가를 보장한다. 다만 그리디는 국소 최적에 갇히므로(예: S 두 개를 붙이려다 N 세 개가 흩어짐), 실전에서는 §4의 국소 탐색·교란을 덧붙여야 한다. 설계 제안
아미노산 수 A ≤ 20, 아미노산당 원소 수 ≤ 28이므로 총 원소 수 E ≤ 560이다. evalScore() 한 번은 모든 원소의 6방향 인접을 보므로 O(E)(공간 배열을 쓰면 상수배). 후보 fold 수는 O(관절 수 × 3축 × 4각도) ≈ O(A · 12). 그리디 한 단계는 모든 후보를 평가하므로 O(A · E), 그리디가 수렴할 때까지의 단계 수가 O(K)라면 전체 O(K · A · E). E·A가 작아(~10⁴) 한 단계는 매우 싸므로, 국소 탐색을 수천~수만 회 반복해도 10 TC가 시간 안에 든다. 병목은 알고리즘이 아니라 탐색이 좋은 형태를 찾느냐다. 설계 제안
사슬을 접어 비싼 원소를 모으려 할수록, 사슬의 두 부분이 같은 격자 칸으로 겹쳐 들어갈 위험이 커진다. verify()는 두 원소가 한 칸을 공유하면(gSpace[z][y][x]가 이미 차 있으면) 즉시 false — 전체 점수 0이다. 밀집과 충돌은 동전의 양면이다.
설계의 모든 단계에서 다음이 성립해야 한다: 서로 다른 두 원소는 결코 같은 (x,y,z)를 점유하지 않으며, 모든 좌표는 [0,100) 안에 있다.
그래서 greedyFold의 evalScore()는 점수를 매기기 전에 placeAll()로 모든 원소를 공간 배열에 놓아 본다 — 놓다가 이미 찬 칸을 만나거나 범위를 벗어나면 -1을 반환한다. 점수가 아무리 높아 보이는 fold라도 이 단사성을 깨면 채택해서는 안 된다. 충돌을 내는 fold는 후보에서 즉시 탈락시킨다.
충돌 회피는 탐색을 까다롭게 만든다 — 점수를 올리는 fold가 충돌을 일으키고, 충돌을 피하는 fold가 점수를 못 올리는 상황이 흔하다. 그래서 그리디만으로는 부족하고 국소 탐색이 필요하다.
그리디 greedyFold가 멈추는 지점은 "어떤 단일 fold도 점수를 못 올리는" 국소 최적이다. 그러나 두세 개의 fold를 동시에 하면 더 좋아질 수 있다 — 예: fold A 혼자서는 충돌, fold B 혼자서는 무점수지만, A 다음 B를 하면 충돌이 풀리며 S 두 개가 붙는다. 단일 fold 그리디는 이런 협력적 수를 못 본다.
탈출 전략을 제안한다. 설계 제안
30·30 한 쌍이 10·10 열여덟 쌍과 맞먹으므로, S끼리 붙이는 데 탐색을 집중한다.verify()가 한 TC라도 false면 gTotalScore = 0 후 break — 그때까지 쌓은 모든 TC 점수가 사라진다. 따라서 설계는 점수 욕심보다 충돌 없는 유효 배치를 먼저 보장해야 한다. 최악의 경우 "전혀 접지 않은 초기 배치"도 충돌 없는 유효 해다(init()이 아미노산을 z축으로 한 층씩 떨어뜨려 놓는다). 유효 해를 손에 쥔 채로만 더 나은 형태를 탐색하라 — 탐색 중 충돌 fold는 시험만 하고 절대 확정하지 않는다.
| 전략 | 유효성 | 점수 경향 | 시간 | 평가 |
|---|---|---|---|---|
| 접지 않음 (초기 배치 그대로) | 유효 | 낮음 | 빠름 | 아미노산이 층층이 떨어져 인접쌍이 거의 없음 |
| 무작위 접기 | 불안정 | 낮음 | 빠름 | 자기 충돌 빈발 — verify 실패로 0점 위험 |
| 전체 탐색 (모든 fold 조합) | 유효 | 최대 | 불가 | 관절 수십 개 × 3축 × 4각도 = 천문학적 조합 |
| 그리디 fold + 국소탐색 + S·N 우선 | 유효 | 설계 목표 | 중간 | 단조 증가 + 충돌 회피 + 고가 원소 집중 |
표의 구조는 §1의 분해를 비춘다. 유효성은 충돌 fold를 확정하지 않으면 얻는다(Invariant) — 최악이라도 초기 배치가 유효 해다. 진짜 경쟁은 점수에서 벌어진다. 접지 않으면 인접쌍이 없어 점수가 바닥이고, 무작위 접기는 충돌로 verify 실패 위험이 크다. 전체 탐색은 이론적 최대를 주지만 관절 조합이 천문학적이라 시간 안에 불가능하다. 따라서 "점수 단조 증가를 보장하는 그리디 + 국소 최적을 벗어나는 탐색 + 비싼 S·N에 집중"하는 설계가 — 통과 코드가 없는 상태에서도 점수 식으로부터 연역할 수 있는 현실적 최선이며, Theorem 1의 정수 무결성이 fold 되돌리기를 받친다.
rotate()의 세 축은 각각 다른 좌표쌍을 바꾼다 — X축은 (y,z), Y축은 (z,x), Z축은 (x,y). dir(시계/반시계) 부호를 한 글자라도 틀리면 의도와 다른 방향으로 접혀 점수가 떨어지고, fold 되돌리기도 어긋난다. 작은 예제로 90도×4 = 항등인지 손검증하라.
fold_element는 회전 대상 구간에 다른 connector가 있으면 회전을 거부한다(아무 일도 안 함). 거부된 fold를 "적용됐다"고 가정하면 탐색 상태가 어긋난다. fold 후 좌표가 실제로 바뀌었는지 확인하라.
verify()는 전체 TC를 0점으로 만든다. evalScore()가 충돌 시 -1을 반환하게 하고, 충돌 fold는 후보에서 즉시 탈락시켜라.
이 문제는 통과 코드가 없으므로 측정된 SCORE를 제시할 수 없다. 대신 채점기의 판정 구조를 명시한다. verify()는 모든 원소를 gSpace 배열에 놓으며 범위 이탈·충돌을 검사한다 — 하나라도 걸리면 gTotalScore = 0 후 break. 모두 통과하면 100³ 공간을 훑어 6방향 인접 가중치 곱을 누적하고, 10 TC 합이 최종 SCORE다 — 높을수록 좋다.
rotate()·fold_amino·fold_element·verify()로부터 연역한 설계다. greedyFold()·evalScore() 스케치는 컴파일·실측을 거치지 않았고, Theorem 2의 시간 복잡도는 그리디 수렴 단계 수에 대한 추정에 의존한다. "90도 회전의 정수 무결성"과 "S·N 인접이 점수를 지배함"은 채점기 코드에서 안전하게 연역되지만, 정확한 SCORE와 최적 접기 전략은 실제 구현·실행으로만 확정된다.