Seon's IT Story

코딩테스트에서 문제를 풀다 보면 논리적 오류나 사소한 실수로 인해 정답을 맞히지 못하는 경우가 많다.

이 때 대부분은 System.out.println() 같은 로그를 찍어 확인하려 하지만, 실전에서는 디버깅(Debugging) 기능을 사용하는 것이 시간 단축과 정확도 측면에서 훨씬 유리하다.

1. 디버깅(Debugging)이 필요한 이유

많은 사람들이 코드를 수정할 때 로그를 찍어서 확인한다. 하지만 로그 방식은 다음과 같은 단점이 있다.

 - 시간 소요 : 로그를 찍고, 실행하고, 다시 지우고, 재실행하는 과정이 반복되어 시간이 오래 걸린다.

 - 시야 협소 : 로그를 찍은 특정 부분만 보게 되어, 코드의 전체적인 흐름을 놓치고 지엽적인 부분에만 매몰되기 쉽다.

디버깅 기능을 사용하면 변수의 상태 변화를 실시간으로 추적할 수 있어 논리 오류를 빠르게 찾아낼 수 있다.

2. IDE 디버깅 기능 활용

Eclipse, Intellij 등 대부분의 IDE는 강력한 디버깅 기능을 제공한다.

 - 중단점(Breakpoint) : 코드의 특정 라인에서 실행을 멈춘다.

 - 변수(Variables) : 현재 시점의 변수 값을 실시간으로 확인한다.

 - 수식(Expression) : 단순 변수 값 뿐만 아니라 arr[i] + arr[i] 와 같이 특정 수식의 결과를 즉시 확인해 볼 수 있다.

3. 코딩테스트에서 자주하는 실수 유형

 변수 초기화 오류

현상 : 여러 테스트 케이스를 처리하는 문제에서 이전 케이스의 계산 값이 다음 케이스에 영향을 미쳐 오답 발생

해결 : for문 내에서 반복될 때 누적 변수(sum 등)나 배열이 적절한 시점에 초기화(0 또는 null) 되는 지 확인한다.

 반복문 인덱스 범위 오류

현상 : N번 반복해야 하는데 N+1번 반복하거나, 배열의 범위를 벗어나는 경우

체크 : 반복문 조건이 i < N 인지, i <= N 인지 의도한 로직과 정확히 일치하는지 디버깅을 통해 확인한다.

 출력 형식 오류

현상 : 문제에서는 숫자만 출력하라고 했는데, 디버깅이나 확인을 위해 넣은 텍스트를 그대로 포함하여 제출하는 경우

주의 : 불필요한 테스트 출력문이 포함되지 않았는지 마지막까지 확인해야 한다.

 자료형 범위 오류(Overflow)

현상 : 로직은 완벽한데 답이 틀리거나, 뜬금없이 음수가 출력되는 경우

원인 : int 자료형의 범위(약 21억)를 초과하여 오버플로우가 발생했기 때문이다.

해결 :

 - 답이 음수가 나올 수 없는 로직인데 음수가 나온다면 100% 오버플로우다.

 - 팩토리얼, 순열, 경우의 수 등 값이 급격히 커지는 문제를 처음부터 long 자료형을 사용하는 습관을 들이는 것이 좋다.

4 정리

코딩테스트는 시간 싸움이다. 한 번에 완벽하게 코드를 짜면 좋겠지만, 실수가 발생했을 때 얼마나 빨리 수정하느냐가 합격을 좌우한다. 로그를 찍으며 해매기보다는, 디버깅 툴을 익숙하게 다루는 연습을 통해 디버깅 시간을 단축해야 한다.

알고리즘 문제를 풀거나 효율적인 로직을 짤 때 가장 중요한 개념중 하나인 시간 복잡도에 대해 정리한다.

시간 복잡도

시간복잡도(Time Complexity)는 주어진 문제를 해결하기 위해 필요한 연산 횟수를 의미한다. 실제 걸리는

시간(초)를 측정하는 것이 아니라, 입력 데이터의 크기에 따라 연산량이 어떻게 증가하는지를 나타내는 지표다.

일반적으로 Problem Solving 환경에서는 1억번의 연산 = 1초 로 예측한다.

시간 복잡도 표기법

 - 빅-오메가 (Big-Ω) : 최선(Best Case)의 경우
 - 빅-세타 (Big-θ) : 보통(Average Case)의 경우
 - 빅-오 (Big-O) : 최악(Worst Case)의 경우

알고리즘 성능 평가시에는 데이터가 최악으로 주어졌을때도 처리가 가능한지를 판단해야 하므로 빅-오 (Big-O) 표기법이 가장 중요

시간 복잡도 도출 기준

1. 상수는 시간 복잡도에서 제외

연산횟수가 N이든 3N이든, N이 무한대로 커지면 상수의 영향력은 미미하므로 똑같이 O(N)으로 취급한다.

2. 가장 많이 중첩된 반복문의 횟수가 기준

반복문이 2중으로 중첩되어 있다면 O(N^2), 3중이라면 O(N^3)이 된다. 따라서 가장 깊은 반복문을 찾으면 된다.

데이터 크기와 연산 횟수 확인

시간 복잡도를 따질 때는 가장 먼저 데이터의 개수(Input Size)를 확인해야 한다. 전체 연산 횟수는 다음과 같이 계산한다.

 연산 횟수 = 알고리즘 시간 복잡도 x 데이터의 크기

알고리즘 별 시간 복잡도 예시

 - 버블 정렬(Bubble Sort) : O(N^2)

데이터가 많아질수록 기하급수적으로 속도 저하

 - 병합 정렬(Merge Sort) : O(N log N)

N^2 대비 훨씬 효율적

효율적인 알고리즘 적용

1. 문제의 제한 시간 내에 통과할 수 있는 알맞는 알고리즘을 선택하기 위함

2. 코드 내에서 비효율적인 로직을 찾아 계산하기 위함

정리

무조건 복잡한 알고리즘을 쓰는 것이 아니라, 데이터의 크기에 맞춰 적절한 시간 복잡도를 가진 알고리즘을 선택하는 것이 핵심

전자서명은 근본적으로 부인방지 기능으로 개인키의 소유자가 서명했다는 것을 증명한다.

따라서 서명 시각에 대한 증명은 신뢰성을 갖지 않는다.

물론 서명 시각을 넣을 수는 있지만, 클라이언트의 시간을 조작하는 방법 등으로 서명 시간 조작이 가능하다.

또한 아래와 같은 경우에

1. 전자 서명 생성

2. 인증서 폐지 발생

전자서명이 인증서 폐지보다 먼저 발생하였느냐의 검증에 문제가 발생할 수 있다.

TSA 의 역할

 - 이 서명 값이

 - 해당 시작에 존재

-> 전자 서명이 언제 생성되었는지 제 3자가 증명해준다.

그러나 타임스탬프가 있다고 무조건 신뢰할 수 있는 것은 아니다.

 - 신뢰 불가한 TSA

 - TSA 인증서/키 문제 발생

 - 검증 정책(LTV 정책)이 없는 경우

-> 타임 스탬프는 조건을 만들어 주는 도구일뿐 만능 해결책은 아니다.

정리

전자서명에서 TSA는 시간 기록 용도가 아니라

전자서명 인증서의 만료/폐지 이후에도 과거 서명을 검증하기 위한 기반을 만들어준다.

타임스탬프 토큰을 발급 받았다고 끝이 아니다. 운영에서는 검증 역시 중요하다.

 - TSQ <-> TSR 매칭 여부(요청한 응답이 맞는지)

 - 토큰에 대한 서명/인증서 검증(TSA를 신뢰할 수 있는지)

1. TSR status 

TSR(TimeStampResp)에는 status(PKIStatusInfo)가 존재한다.

 - granted / grantedWithMods 등 성공 여부 확인

2. timeStampToken

status가 성공이면 timeStampToken이 존재

3. messageImprint

 - 원문을 다시 해시

 - TSTInfo의 messageImprint(알고리즘+해시값)와 비교

4. nonce

TSQ에 nonce를 포함하였다면, TSR에도 같은 nonce가 있어야 한다.

 - TSQ nonce == TSR nonce

 - 리플레이 공격 방지용

5. policy

TSTInfo 에는 policy OID가 포함

 - 허용 정책이 정해져 있다면 필터링

 - TSQ에서 reqPolicy를 요청했다면 응답 policy가 동일한지 확인 

6. TimeStampToken 서명 검증

 - 토큰(CMS SignedData) 서명 검증 

 - signerInfo가 가리키는 TSA 인증서로 검증

7. TSA 인증서 체인 검증

토큰에 인증서가 포함되어 있어도 신뢰 여부는 별도로 판단해야 함

 - 루트/중간CA 체인이 신뢰 저장소에 연결되는지 확인

정리

TimeStampToken 검증은 단순한 시간 검증이 아니다.

 - status 확인

 - token 존재 확인

 - messageImprint 일치 여부

 - nonce 매칭

 - policy 확인

 - 서명 검증