프로그래밍 일기 — 알고리즘 기초 쌓기
#Java, #알고리즘, #코딩테스트
알고리즘 문제로 다시 이렇게 빨리 돌아올지 몰랐다. 사전 과정을 밟는 동안 알고리즘 문제를 푸는 연습을 했는데, 다시 2주만에 알고리즘 문제를 푸는 연습으로 돌아온 것이다.
그만큼 이 과정은 개발자가 되는데 있어서 매우 중요한 것처럼 느껴진다. 그도 그럴것이, 모든 개발자는 거의 대부분 코딩테스트를 거치게 되어있으니까. 그래서 오늘부터 다시 알고리즘 문제를 푸는 연습을 시작했다. 다시 일주일 동안 또 달려보자!
수수께끼 1 — 제곱근 문제(2)
문제 설명
임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다.
n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요.
제한 사항
- n은 1이상, 50000000000000 이하인 양의 정수입니다.
입출력 예
- a = 3, b = 5 => return 12
- a = 3, b = 3 => return 3
- a = 5, b = 3 => return 12
문제 해설:
이 문제는 주어진 값(x)이 완전한 제곱근 (n = x²가 완전한 정수가 되는지)를 확인하는 프로그램을 짜야하는 문제다. 그만큼 간단한 문제이며, 이 이상의 복잡한 요구사항은 없다.
일단 내가 문제를 읽고 파악한 요구사항은 다음과 같다.
- 수 n이 주어진다, 이 수가 x² 로 완전한 제곱근이 되는지 파악한다.
- 제곱근이면 (x+1)²를 리턴하고, 아니면 -1을 리턴한다.
그렇다면 제곱근을 확인하는 방법을 프로그램으로 어떻게 구현할 수 있을까? 나는 아래와 같은 코드를 썼다.
아마도 가장 쉬운 방법은 Math.sqrt() 메서드를 활용하는 것이다. Java에서 기본적으로 지원하는 메서드이기 때문에 별도의 import 가 필요없다. 주의할 것은 이 메서드는 기본적으로 double 타입의 값을 리턴한다는 것이다. 따라서 long정수 타입으로 casting을 통한 강제 타입변환 (long)이 필요하며, 스스로를 곱해 제곱을 만들어 주어야한다. 이후에 우리가 처음 받은 값 n 과 같은지를 확인하는 것이다.
또한 결과값에 0.5 를 더해서 double 을 다룰시에 생기는 정밀도 문제(precision error)를 없앨 필요가있다. 때로 int 값이 double 에 지정되었을 때, 소수점 자리로 표현될 수 있기 때문이다. 예를 들어, double 변수에 3을 지정하면 그 값은 3.000001/2.9999999 가 될 수 있다. 따라서 이런 표현을 피하기위해서는, 0.5를 double 타입 수에 더하여 long 으로 casting하기전 정밀도 에러를 막을 수 있어야한다.
추가적으로, sqrt 함수를 하나의 값으로 테스트하면 실행 시간은 훨씬 빠르다. 한편으로는 sqrt 함수를 너무 많이 호출하게되면 안 좋을 수 있다. sqrt 함수에 의해 수행되는 작업의 수를 줄이고자할 때에는, 이렇게 sqrt 를 하나의 값으로 테스트하는 것이 확실히 실행시간을 단축시키는데 도움이 된다.
// 정답 코드
class Solution {
public long solution(long n) { // long 타입의 값을 리턴해야한다.
long x = (long) Math.sqrt(n); // 주어진 수 n의 x^(1/2)를 찾는다.
long test = (long)(x + 0.5); // 주어진 수에 double 정밀도 문제를 막기 위해 0.5를 더하고 long으로 casting한다.
if(test*test == n){ // 만약 test 값의 제곱이 n과 같으면 (x+1)^2를 리턴한다.
return (long)(Math.pow(x+1, 2));
}
return -1; // n과 다르면 -1을 리턴한다.
}
}요약:
Math.sqrt(n)는 이미 Java에 있는 유용한 메서드이다. 결과값은double이기에 원하는 유형으로 casting이 필요하다.double값에는 0.5를 더해주어 정밀도 에러(Precision error)를 피하는 것이 좋다.test의 제곱을 구해 이 값이n과 같으면(x+1)의 제곱을 리턴한다.
보너스: 클래스 복습
오늘은 클래스의 개념에 대해 복습했다. 아래 요구사항에 대해 생각해보자.
1. 인스턴스변수
index, title, contents
각각 알맞는 참조형 변수로 생성
2. 클래스변수
pages
3. title, contents만 초기화하는 생성자
4. contents를 수정하는 메서드
5. contents를 확인하는 메서드
*인스턴스 변수의 접근제어자는 Book 클래스에서만 접근 가능하게
위 요구사항에 맞는 코드를 작성하려면 어때야할까? 아래와 같은 코드의 구성을 가질 것이다. 인스턴스 변수를 클래스를 통해서만 접근해야한다면 접근제어자는 private 일 것이다. 또한 이들이 참조형 변수려면 String 은 이미 참조형이지만, int 는 기본형이므로, 참조형으로 만드려면 Integer 를 타입으로 지정해야한다. 또한 클래스 변수는 static 키워드를 갖는다.
생성자가 특정 인스턴스 변수를 초기화한다면, 일단 이를 생성자의 매개변수로 받아와야하며, this 키워드를 통해 인스턴스 변수를 참조한다는 것을 명기하고 이를 매개변수에 지정해주어야한다. 특정 인스턴스 변수를 수정하는 메서드는 수정하려는 인스턴스 변수의 매개변수를 받아, setter 메서드를 통해 this 키워드를 활용하여 인스턴스 변수를 참조하고 매개변수에 지정해준다. 마지막으로 인스턴스 변수를 확인하기 위해 getter 메서드를 만들어 확인하고자하는 변수를 리턴한다. 특정 변수를 확인하기위해 호출하는 만큼, 반드시 매개변수를 넣어줄 필요는 없다.
public class Book {
// 인스턴스 변수
private Integer index;
private String title;
private String contents;
// 클래스 변수 (static 이어야한다)
private static Integer pages;
// 책 생성자 (매개변수로 생성자를 통해 초기화할 인스턴스 변수를 가져와야한다.)
public Book(String title, String contents){
// 생성자 초기화
this.title = title;
this.contents = contents;
}
// contents 수정 매서드 (setter)
public String setContents(String contents){
this.contents = contents;
}
// contents 확인 메서드 (getter)
public String getContents(){
return contents;
}
}오늘의 다짐/느낌/생각
사실 오늘 기술매니저님과의 면담을 했는데, 갑자기 클래스를 알고 있는지에 대해 테스트를 받게 되었다. 그런데 내가 자신있게 쓴 코드가 틀렸다는 말을 들었고, 그렇다는 것은 내가 클래스를 제대로 이해하지 못하고 있다는 의미여서 그것이 큰 충격으로 다가왔다. 어제까지 클래스를 이해하려고 몇 시간을 보냈는데, 그게 허무한 시간이 되었다는 판결같아서 매우 아쉽고 쓰렸다. 매니저님이 보시기에는 내가 클래스조차 잘 이해하지 못하는 상태였고, 따라서 그가 해줄 수 있는 말은 Java 기초를 다시 복습하라는 것이었다. 다른 조원들은 문제 없이 통과했고, 오히려 더 깊게 컴퓨터 공학적인 개념을 아는지를 물어보아서, 나는 왠지 뒤쳐진 것처럼 느껴졌다.
또한 부트캠프에서 전해주는 것 이상으로 공부를 해야한다는 말에 조금 혼돈이 오기도했다. 부트캠프에서 전달해주는 내용을 주어진 시간내 소화하는 것도 쉽지 않게 느껴지는데 그 이상을 하라니 정말 감이 안 잡혔다. 나의 페이스가 너무 느린 것인가? 그렇다고해서 내가 지금보다 훨씬 빨리 달린다고해서 배워야할 내용들을 충분히 잘 이해하면서 넘어갈 수 있을까? 나는 자신이 들지않았다. 나는 주어진 시간내 100% 효율을 못내면 조금 쉬었다가거나 조금 더 느리게 가더라도 시간을 좀 더 투자해서 그것을 만회하려는 성격이다. 얼마나 더 빨리 달려야할지 모르겠다. 나름 프로그래밍을 공부했다고 생각하고 들어왔는데, 이런 기초조차 제대로 설명하지 못하는 나를 보면서 많이 부족하다는 느낌은들지만, 그렇다고해서 지금보다 더 빨리 달리는 나를 지금 당장은 상상하기 어렵다.
물론 나의 학습 방법이 완벽하지 않을 수 있기 때문에, 물론 개선해나가야할 점은 있을 것이고, 나도 그것을 위해 계속 매니저님들과 피드백을 주고 받겠지만, 그렇다고해도 너무 급하게 달리고 싶지는 않다. 내가 소화할 내용을 충분히 소화하지 못한채 달리게되면 체해서 제대로 중간 장애물을 넘지 못할 수도 있기 때문이다.
물론, 최선을 다할 것이다. 내가 이 선택을 한 이상 내가 할 수 있는 최선은 이것 뿐이다. 그리고 아직 끝은 아니라고 생각한다. 어쩌면 이 보다 더한 피드백을 앞으로 받을 수도 있다. 하지만, 그래도 내게 많은 것을 주어진 시간내 충분히 배울 수 있는 잠재력은 있다고 생각한다. 그래서 아직은 포기하지 않을 생각이다. 나만의 답을 찾아가기위해 엄청 빨리 스프린트하지는 못해도 중간에 멈추지는 않을 것이다.
나와 같은 걱정을 하는 사람들도 스스로를 좀 더 믿고 달려보기를 바란다. 아직 시작도 못해봤다. Spring을 만나지도 못했다. 나는 오늘 좋은 피드백을 받지는 못했지만 조금 더 노력해서 Spring을 만날 것이다. 그리고 그렇게 계속 노력하다보면 Spring을 만나서도 쉽게 쓰러지지 않을 것이다. 넘어져도 다시 일어날 생각으로 임하다보면 어느새 한 발자국이 두 발 자국, 더 나아가서 열 발자국 이상 온 나를 발견할 것이라 믿으며 한번 더 힘을 내 본다.
참조:
(1) https://pixabay.com/vectors/maze-puzzle-riddle-quiz-labyrinth-2094070/
(2) https://school.programmers.co.kr/learn/courses/30/lessons/12934
