구현이란?
| 헷필드는 ENTP, 언쟁을 좋아하는 달변가이다. 하지만 이런 헷필드에게는 아주 큰 약점이 있었으니... 바로 당황하면 머릿속이 하얘진다는 것! 어느날, 헷필드는 학교를 대표하여 토론대회에 나가게 되었다. 상대는 영혼의 라이벌 머스테인! 헷필드는 늘 머스테인을 상대로 이겼었던지라 대본 따위는 전혀 준비하지 않았고, 마침내 토론대회 날이 밝았다. 언제나 그랬듯 머스테인을 조목조목 두드려 패며 승기가 헷필드 쪽으로 기운 상황. 갑자기 머스테인이 헷필드가 예상했던 범위 바깥의 반박을 시전하였다!! 당황한 헷필드... 물론 똑똑한 헷필드는 바로 논점을 간파하고 반박의 반박을 준비하는데.. 이미 한번 하얘진 머릿속은 제대로 돌아가지 않았다. 무슨 말을 해야 할지는 알겠는데, 어떻게 말해야 할지 전혀 정리가 안되는 상황! 결국 횡설수설만 하던 헷필드는 첫 패배의 굴욕을 맛보고 만다. 불쌍한 헷필드! |
헷필드는 갑자기 들어온 상대의 질문에 순간 당황하여 머릿속의 말들을 제대로 정리하지 못했다.
아무리 좋은 반박거리가 있더라도 그것을 말로 표현하지 못하면 무용지물인 것이다.
구현이란, 위 문장에서 반박거리를 아이디어로, 말을 코드로 바꾼 것과 같다.
아무리 좋은 아이디어가 있더라도 그것을 코드로 구현하지 못하면 무용지물인 것이다.
코드를 구현하는데 가장 중요한 것은 뭘까? 시간 복잡도? 코드의 길이? 아니면 사용 언어??
정답은 바로 "정확성"이다. 1+1을 단 0.00001초만에 계산해주는 코드가 있다고 해도, 답이 3이 나와버리면 아무짝에 쓸모 없는 코드다. 시간 복잡도나 코드의 길이는 모두 정확히 코드를 구현 하고 나서 고려할 문제이다.
//a = 1, b = 1일 때, a+b의 값을 구하시오
function A(a, b){
return a * b
}
//실행 속도는 빠르지만 정확하지 않은 코드
function B(a, b) {
for (let i = 0; i < 100000; i++) {
for (let j = 0; j < 100000; j++) {
a = a * a / a
b = b * b / b
}
}
return a + b
}
//실행속도는 느리지만 정확한 코드A 코드보다는 B 코드가 압도적으로 시간이 많이 걸리지만, 결국 정확한 코드는 B이다.
이처럼 구현은 "아이디어를 얼마나 정확하게 코드로 만들어 내느냐"의 싸움이다.
구현시 고려할 사항
1. 문법과 라이브러리
코딩을 처음 시작할 때 부터, 코딩테스트를 준비하고 있는 지금까지도 나를 가장 괴롭게 하는 것은 바로 "오류"이다.
이 오류는 정말 여러가지 이유로 날 수 있는데, 가장 많이 내는 오류는 바로 문법 오류가 아닐까 싶다.
여러 언어를 배워보고 자바스크립트를 배우면서 느꼈던 장점들 중 하나는 바로 자바스크립트의 쉬운 문법과 편하게 쓸 수 있는 라이브러리들이었다.
변수형을 지정할 필요도 없고 추천되진 않지만 명령어도 생략 가능하다. ;을 반드시 써야 할 필요도 없는데, 그렇다고 다른 언어들과 완벽히 다른 문법을 가진것도 아니다. 또한 복잡하게 코드로 구현해야 하는 기능들이 단 하나의 함수로 모두 해결되기도 한다.
하지만 가장 큰 적은 바로 방심. 생각보다 이런 자잘한 문법에서 실수가 많이 나오곤 한다.
예를 들어 while문의 종료 조건을 지정하지 않아 무한루프에 빠진다거나, 맞지 않는 라이브러리를 호출했다거나, 매개변수를 잘못 지정했다거나 하는 것들 말이다.
위에 설명했듯 가장 중요한 것은 정확한 코드 구현이다. 하지만 이는 당연히 문법 오류가 없다는 것을 전제하에 하는 말일 것이다!!
2. 메모리 제약
프로그래밍에는 시간 복잡도와 공간 복잡도가 존재한다. 시간 복잡도는 프로그램을 수행하는데 얼마나 많은 시간이 걸리는지, 그리고 공간 복잡도는 얼마나 많은 메모리를 사용하는지를 나타내는 수치이다.
다행히 자바스크립트는 자료형 선언이 필요 없는 언어이고, 큰 수의 연산도 자동 실행이 된다. 만약 C를 사용했다면 수의 크기에 따라 int, float, double, long 등의 자료형을 선언해 주었어야 했겠지만!
단, 정수가 아닌 실수형 변수는 유효숫자에 따라 범위 초과시 오류가 날 수 있다고 한다!
숫자가 크면 연산 속도가 오래 걸리고, 이는 시간 복잡도가 올라가는 원인이 된다. 시간 복잡도에 제한이 있는 문제라면 이를 고려하여 수를 조절하거나, 반복되는 연산을 줄여 시간 복잡도를 낮추어야 한다.
공간 복잡도는 메모리에 얼마나 많은 데이터가 저장되어 있느냐에 따라 판가름난다. 1개의 변수를 선언한 코드와 1000개의 변수를 선언한 코드의 메모리 사용량은 차이가 날 것이다.
메모리를 잡아먹는 가장 큰 원인 중 하나는 바로 배열인데, 두 배열의 길이가 똑같이 100이라 해도, 0만 100개가 들어있는 배열과 길이가 50인 배열이 100개 들어있는 배열은 메모리 차이가 어마어마하게 난다.
정말 다행히도, 메모리가 부족할 정도로 많은 데이터를 처리하는 문제는 잘 나오지 않는다고 한다. 입출력에 문제가 있을 뿐더러, 채점 환경에서도 문제가 생길 수 있기 때문!
하지만 어쨌거나 같은 기능을 가졌다면 메모리를 조금이라도 덜 사용하는 코드가 좋은 코드일 것이다.
구현의 종류
- 완전 탐색 : 모든 경우의 수를 전부 고려
- 시뮬레이션 : 제시한 알고리즘을 한단계씩 차례대로 수행
정리
구현
- 머릿속의 아이디어를 코드로 만들어 내는 과정
- 정확성이 가장 중요
고려사항
- 문법 오류와 정확한 라이브러리 사용
- 시간, 메모리 사용량 고려
종류
- 완전탐색
- 시뮬레이션
예제
- 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다
- 00시 00분 00초
- 00시 13분 30초
- 반면 다음은 3이 하나도 포함되어 있지 않으므로 세면 안되는 시각이다
- 00시 02분 55초
- 01시 27분 45초
00시 00분 00초부터 N시 59분 59초까지의 모든 시간을 초 단위로 세서 풀 수 있는 완전 탐색 문제이다.
중요한 것은 시, 분, 초에 3이 하나라도 존재하면 된다는 것.
그렇다면, 시, 분, 초를 문자로 만든 뒤 match()를 이용해 3을 찾아내면 된다.
그럼 시, 분, 초는 어떻게 세느냐?
우리에게 필요한 정보는 숫자 뿐이며, 60초는 1분이고, 60분은 1시간이다.
즉, 초를 1씩 증가시킨 뒤 60이 되면 분을 1 증가시키고, 분이 60이 되면 시간을 1 증가시키면 된다.
따라서, 이 문제는 다음과 같은 메커니즘을 따랐다.
- while문 사용. 시간이 N+1 이 되기 전 까지 반복
- hour, min, sec 변수 선언 뒤 모두 0으로 초기화.
- 반복 할 때 마다 sec은 1씩 증가.
- hour, min, sec을 문자로 바꾼 뒤 합침
- match()를 통해 3을 찾아냄
- 3이 있다면 answer에 1을 추가, 아니라면 반복 진행
- sec이 60이 된다면, min에 1을 추가하고 sec은 다시 0으로 초기화
- min이 60이 된다면, hour에 1을 추가하고 min은 다시 0으로 초기화
코드
let N = 5
let answer = 0
let sec = 0
let min = 0
let hour = 0
while(hour < N+1){
if((hour.toString() + min.toString() + sec.toString()).match("3")){
console.log("3이 있는 시간 : " + hour + "시 " + min +"분 " + sec +"초")
answer++
}
sec++
if(sec == 60){
min++
sec = 0
}
if(min == 60){
hour++
min = 0
}
}
console.log("3의 개수 : " + answer)
실행 결과
문제를 풀고 나서 보니 책에 나온 답안은 나의 답안과 좀 달랐다.
책에서는 3중 for문을 이용해 문제를 풀었는데, 어차피 답도 같으니 어떤 코드가 시간 복잡도가 더 낮을지 궁금하여 측정해 보았다.
let answer = 0
for (let i = 0; i < n + 1; i++) {
for (let j = 0; j < 60; j++) {
for (let k = 0; k < 60; k++) {
let string = i.toString() + j.toString() + k.toString()
if (string.match("3")) {
answer++
}
}
}
}
N이 아주 작을 때를 제외하고는 내 코드의 시간 복잡도가 더 높았다. 이런 경우에는 내 코드보다는 예제 답안과 같은 코드를 작성한 사람이 나보다 좋은 점수를 받을 것이다. 으악!!!!
내 코드는 변수가 훨씬 많고, 무엇보다 반복마다 3개의 if문을 거쳐야 하므로 실행 시간이 좀 더 걸리는 것 같다. ..
앞으로는 최대한 간단한 방법으로 문제를 풀 수 있게 노력해 봐야겠다.