맥북이 도착하고 난 뒤부터 코딩테스트를 시작하려 했지만, 맥북이 생각보다 늦게와서 (아니 한국에 들어왔는데 왜 배송이 안되냐고..ㅠㅠ) 데스크탑으로 공부를 시작했다!
앞에 문제들은 이미 풀어져 있길래,, 2588번부터 하나하나 단계별 풀어보기를 진행할 예정이다.
오늘은! 그 대망의 첫 번째 문제인 백준 2588 A*B를 풀 것이다.
오늘의 문제
2588번 A*B를 순차적으로 출력하라!
2588번의 문제는 두 정수 A*B를 계산할 때, 계산 과정을 모두 출력하는 것이다.
이 문제를 딱 봤을 때, 정해야 할것 하나와 알아야 할 것이 두 가지가 있는 것을 알 수 있다.
정해야 할것 1. 두 정수 중 어떤 것을 베이스로 할것인가?
알야아 할것 1. 곱해지는 수는 몇자리 수 인가? (365=3자리 수) 2. 곱해지는 수의 각 자리의 값은 무엇인가? (일의 자리, 십의 자리, 백의 자리 ...)
정해야 할 것은 그냥 첫 번째 수를 베이스로 했고, 따라서 두번 째 수는 자연스럽게 곱해지는 수로 정했다.
해당 문제는 수학적 지식만 조금 있다면 바로 구할 수 있다. 나 같은 경우에는 위의 방법이 바로 떠올랐고, 이미 알고있는 방법이기 때문에 바로 문제를 풀 수 있었다. (세 번 실패한건 비밀... 첫 번째는 오타로인한 컴파일 에러.. 두 번째는 클래스 명이 Main이어야 한다는 것을 까먹고 있었고,, 따라서 틀렸다...)
1. 곱해지는 수는 몇자리 수 인가?
우선 곱해지는 수가 몇자리 수인지 알아야 한다. 우리에게 주어지는 곱의 값은 매번 달라질 것이고, 따라서 하드코딩을 통해 값을 매번 지정할 수 없기 때문이다.
예를 들어, 곱해지는 수가 한자리 수일때의 경우, 두자리 수일 때의 경우, 세자리 수일 때의 경우, ... 엄청 큰 자리수일 때의 경우 를 모두 코딩할수는 없잖아!
해당 질문은 log를 통해 쉽게 구할 수 있다. 먼저 자리수에 대해 우리가 표현할 때, 1의 자리는 다음과 같이 표현할 수 있다.
$$ n * 10^0 $$
마찬가지로 10의 자리는 다음과 같이 표현할 수 있다.
$$ n * 10^1 $$
이쯤 되면 내가 무엇을 하고자 하는지 이해 할 수 있다! 즉, 우리는 정수의 자리수를 표현하기 위해 다음과 같이 일반화 할 수 있다.
$$ n * 10^m ( m >= 0, integer ) $$
이 때,n은 우리가 표현하고자 하는 수이고,m은 해당 숫자의 자릿수이다.
우리는지수를 로그로 표현할 수 있는 것을 고등학교 수학에서 배웠다.
로그와 지수의 관계
즉, 자리수를 로그를 통해 표현할 수 있는 것인데, 위의 일반화를 로그로 표현해 보면 다음과 같이 될 수 있다.
$$ m = log_10 n $$
이 때, m은 자리수가 되고, n은 표헌하고자 하는 수 이다! 그런데, log에서는 한가지 주의할 점이 있는데, log 0이 정의되지 않는 점이다.
$$ 10^m = 0 $$ log 0을 지수로 나타내었을 때 위와 같은 식이되고, 해당 식을 만족하는m의 값은 없기 때문이다.
따라서, 우리가 구하고자 하는 자릿수는 최종적으로 다음과 같은 식이 된다.
$$ m = {log_{10} n} + 1$$
2. 곱해지는 수의 각 자리의 값은 무엇인가? (일,십,백, ...의 자리)
이제 해당하는 m 자리의 값이 무엇인지 구하면 된다.
해당 질문은 놀랍게도 몫을 구하는 식으로 쉽게 풀 수 있다. 위에서 우리는 모든 수를 다음과 같이 표현할 수 있다는 걸 이미 인지했다.
$$ n = 10^m $$
우리는 궁극적으로 n이 무엇인지 구해야 한다. 수는 0~9까지 중 하나로 표현할 수 있고, 거기에 자릿수를 곱해주게 되면, n이 무엇인지 알 수 있다.
"그래서 도대체 0~9 중 무엇인지 어떻게 아는데?!"
우리가 어떤 수를 나눌 때, 해당 식은 다음과 같이 표현된다.
$$ N = Qx + R $$
아직도 감이 안오는가?!?!
우리가 구하고자 하는 수 N에 대하여 Q=10(몫의 밑)이고, x(몫의 배수)가 얼마든 간에 R의 범위는 0~9로 한정된다.
이 때 우리는 몫의 배수를 자리수로 해 줄 것이다. 무슨 말이냐면, 다음과 같이 나타낼 수 있다.
$$ 10^m ％ 10 $$
여기서 문제점은, 우리가 아무리 10 % 10, 100 % 10, 10....0, % 10을 해도 0이 나온다는 점이다. 그 이유는, 우리 본래 수를 아직 구하지 않았기 때문인데, 본래 우리가 찾고자 하는 수는 다음과 같이 구할 수 있다. 예를 들어, 385에 대하여 8을 구하고자 할 때는 다음과 같다.
$$ {385 / 10^1} ％ 10 = 8.5 $$
이 때, 우리가 사용하는 수는 정수이기 때문에, 8로 구해지는 것을 알 수 있다.
이제 위 두 수식을 근거로 코드를 작성해보자!
문제의 풀이 과정을 출력하기 위한 함수 하나, 그리고 메인함수 하나 하여 총 두 개의 함수를 만들 것이다.
메인 함수는 두 수를 입력받고, 풀이 과정을 출력하는 함수를 호출하며 최종적으로 두 식의 연산 결과를 출력할 것이다.
BufferedReader와 InputStreamReader를 이용하여 입력받을 수 있지만, 간단한 문제이고 메모리, 속도제한 등 아무 것도 없기 때문에 java.util.Scanner를 이용하여 두 수를 입력받을 것이다.
따라서 최종 코드는 다음과 같다.
public class Number2588{
public static void main(String args[]){
try(Scanner scan = new Scanner(System.in)){
int a = scan.nextInt();
int b = scan.nextInt();
printNth(a, b);
System.out.println(a*b);
}
}
public static void printNth(int a, int b){
int length = (int)(Math.log10(b)+1);
for(int i = 0; i < length; i++){
int tempB = b / (int)Math.pow(10, i) % 10; // tempB 없이 바로 출력해도 된다.
System.out.println(a * tempB);
}
}
}
받자마자 제일 처음에만 한번 보고, 이후에 블루투스 키보드만 사용해서 키판에 찍힘이 존재하는지 몰랐다..
그런데 한번 누워서 맥북 써봐야지 하고, 누워서 맥북을 여는데!!! 그 순간 넘버 4 위에 찍힘이 :O 하는 표정으로 날 바라보고 있는게 아닌가 ㅠㅠㅠㅠㅠ
그래서 쓸까 말까 고민하다가, 주변에서 새 기기이고 애플 정책상 14일 안에 묻지마 환불이 가능하다 하니 얼른 새걸로 교환해라!! 라고 조언해주는 바람에 교환신청 했다.
환불 후 재구매를 하지 않은 이유는, 첫번째로 교육할인 스토어는 환불 진행이 완료되더라도, 교육할인스토어 정책상 학년별 대수 구매 수량 제한이 있기 때문에, 제한이 풀릴때 까지 결제가 불가능하다는 안내를 받았고, 체크카드로 결제했기 때문에 환불 후 카드사에서 실제 환불이 되기까지의 딜레이를 감안했을 때 교환 진행했을 때와 별 차이가 없다는 결론이 나왔기 때문이다.
그래서, 6월 27일 애플 교육할인 스토어에 전화해서 교환절차를 신청했고, 7월 마지막주에 신제품을 받을 수 있을거라는 안내를 받았다.
그런데 내가 제품을 수령하는 날짜는 12일~14일로 찍혀있었다!
그런데 실제 애플 홈페이지에서는 내가 제품을 수령하는 날짜가 12일~14일로 찍혀있었다!
애플에서 나로부터 제품을 수거해가는 날짜가 7월 1일이었고, 애플의 제품검수팀이 환불될 제품을 검수하고, 실제 환불이 진행되는 날짜가 12일쯤이라고 안내를 받았는데, 그 즈음하여 내가 제품을 받을 수 있을거라는 안내였다.
처음에 이 문구를 확인했을때는, '그냥 오류겠지'라고 생각했는데, 얼마 지나지 않아서 다음과 같은 이메일을 받았다.
아니, 이쯤되면 오류가 아니라 진짜 12일~14일에 제품을 받아볼 수 있다는 말 아닌가?!
저때가 되어봐야 실제 제품 수령 여부를 확인할 수 있겠지만, 어쨋거나 내가 안내받은 7월 26일~28일보다 대략 2주나 빠른 기간이기 때문에, 나는 다시 한번 설레고 있다. (사실 이 게시글도 맥북으로 작성하고 있지만...)
이번에 느낀건데 맥북 정말 쫀쫀하다. 키보드 타이핑하는 맛이 있다! 단점이라면,, 한영 변환할 때, 0.4초 정도의 딜레이가 있고, 이 사이에 키를 누르면 내가 요청했던 한영환이 씹힌다. 맥OS의 문제인지, 아니면 하드웨어와의 Communication간에 문제가 있는건지(결국에 Operating System에서 사용자의 요청 IO에 대하여 적절히 처리하지 못하는거지만...) 잘 모르겠지만, 이거 빼곤 아직 다 괜찮다!
M1이 나온지 얼마 안됐기 때문에 개발 IDE(인텔리제이, 이클립스)의 반응속도 문제는 뭐.. 참아줄만하다. (일단 맥북이 너무 예쁘고, 키감이 너무 쫀쫀하고, 배터리가 너무 오래간다........ 저장용량은 뭐.. 내가 옵션을 안넣어서 어쩔 수 없는거고..)
원래 적어도 이틀에 하나씩 글을 쓰려 했지만, 학기중 스케쥴이 은근 바빠서 실천하지 못했다..ㅠㅠ 여튼! 오늘은 Java Tree 구현법을 보려고 한다.
앞의 ArrayList, Stack, Queue를 모두 본 사람은 알겠지만, 우리는 정보를 담는 어떤 객체와 이 객체를 어떠한 구조를 사용하여 데이터를 저장할 것인가를 다룰 것이다.
트리 구조에서는 흔히 객체를 담는 구조를 노드라고 하며, 이를 가지로 연결하여 나무처럼 만든다 해서 트리라 부른다. 트리에 사용되는 용어는 다음과 같다.
root: 뿌리. 최상위 노드 parent: child node를 갖는 노드 child: parent node를 갖는 노드 edge: 노드를 연결하는 선, branch라고도 함 depth: root부터 어떤 특정 노드까지의 깊이 height: 해당 노드까지 트리의 높이 (level-1) leaf: 자식이 없는 최말단 노드 degree: 자식 수
아 맞다. 구현하는 글을 쓰고 있었지. 트리의 개념은 따로 정리해서 글을 쓰겠다.
Top Down, Bottom Up
트리는 위에서부터 아래로 만들어 나가는 Top down 방식과 최말단 노드에서부터 위로 올라가는 Bottom Up 방식이 있다. 본 글에서는 탑다운 방식을 구현할 예정이다. Root를 먼저 만들고, 그 뿌리에 가지를 하나씩 이어나가는 방식으로 말이다.
Tree에는 어떤게 필요할까?
Full Binary Tree
나무(식물)을 떠올려보면, 모두 뿌리를 먼저 내리고 그 이후에 줄기, 기둥, 가지, 잎, 꽃, 그리고 열매를 만들어 나간다.
즉 우리는 먼저 트리의 뿌리, root를 먼저 내려야 한다. 따라서 root를 설정할 수 있어야 하고, 뿌리로부터 나머지 가지들을 칠 수 있어야 한다.
root를 설정하는건 생성자로 할 수도 있고, setRoot와 같은 함수를 통해 할 수도 있다.
가지를 치는 것은 부모에서 자식을 설정하는 것이고, (반대로 자식에서 부모를 찾는 기능이 추가적으로 있어도 된다!) 본 글에서는 이진트리(Binary Tree)를 구현할 예정이라 setLeft, setRight (혹은 addLeft, addRight)를 만들 예정이다.
추가로 있으면 좋을 기능에는 size, height, depth, 그리고 트리의 꽃인 순회 기능이 있다.
본 글에서는 size와 순회기능을 추가 구현하고, 늘 그렇듯 height와 depth는 간단하기 때문에 구현하지 않을 예정이다.
Tree의 Node!
우선 Tree를 책임질 Node를 만들 것이다. Node는 내 부모를 가리킬 수 있어야 하고, 내 자식들을 가리킬 수 있어야 한다.
상상해보라. 나무에서 가지가 끊어진 상태로 존재할수는 없다. 끊어진 나뭇가지는 본체와 아무관계가 없으며, 죽은 가지일 것이다! (마찬가지로 열매도 가지 혹은 꽃으로부터 떨어진다면 더 이상 나무와는 관계 없다.)
노드는 정말 나의 데이터를 설정하고, 부모와 왼쪽, 오른쪽 노드를 가리키는것이 전부이기 때문에 한번에 코드를 올린다.
<T>는 제네릭 형태인데, 쉽게 말하면 이 노드는 T형태의 데이터를 갖겠다는 뜻이다. 이 T는 String, int, float 등 아무 객체타입이 될 수 있다.
Tree 구현!
자 이제 Tree를 구현 해보자! 트리의 생성자는 다음과 같다.
public class Tree<T> {
private Node<T> root;
private int size;
public Tree(){
this(null);
}
public Tree(Node<T> root){
this.root = root;
if(root != null)
size = 1;
}
}
나무를 아직 안심었을 수도 있고, 나무를 심었을 수도 있기 때문에 두 가지로 나누었다.
여기에 root, 그리고 트리의 왼쪽, 오른쪽 노드를 설정하는 코드는 다음과 같다.
...
public int size(){ return this.size; }
public Node<T> getRoot(){ return this.root; }
public Tree<T> setRoot(T element){
if(root == null)
size = 1;
this.root = new Node(element);
return this;
}
public Tree<T> setRoot(Node<T> element){
if(root == null)
size = 1;
this.root = element;
return this;
}
public Node<T> addLeft(Node<T> parent, Node<T> child){
if(parent.getLeft() != null){
System.out.println("Already have left");
return null;
}
size++;
parent.setLeft(child);
return parent;
}
public Node<T> addRight(Node<T> parent, Node<T> child){
if(parent.getRight() != null){
System.out.println("Already have right");
return null;
}
size++;
parent.setRight(child);
return parent;
}
public Node<T> removeLeft(Node<T> parent){
Node<T> target = parent.getLeft();
if(target != null)
size--;
parent.setLeft(null);
return target;
}
public Node<T> removeRight(Node<T> parent){
Node<T> target = parent.getRight();
if(target != null)
size--;
parent.setRight(null);
return target;
}
...
해당 코드를 보면 root를 설정하거나 획득하는 것을 볼 수 있다.
보면 알겠지만, 트리에서 각 노드들에 대한 왼쪽, 오른쪽 노드를 설정하는 것에 깊게 관여하지 않는다. Node에 기본적으로 왼쪽, 오른쪽을 설정하는 코드가 포함되어 있기 때문에, 노드가 잘 할것이라 믿고 노드에게 준다. 다만, 트리는 이미 자식 노드가 설정되어 있을 때 덮어씌우면 안되기 때문에, 해당 경우에 한해서만 "Already have left!"와 같은 말을 출력해준다.
이제 트리의 꽃인 순회이다. 순회는 크게 3가지 방향이 있다.
height가 1인 full binary tree를 떠올려 보면 다음 표의 왼쪽과 같은 그림이다.
이진 바이너리 트리
이 트리를 더 확장해보면 아마 오른쪽과 같이 확장 될 것이다. 트리의 모양이 삼각형과 비슷하지 않은가?
자! 삼각형을 한붓 그리기로 그려봐라. 이 때, 각 꼭짓점은 full binary tree의 각 노드를 가리킨다고 하자. 그러면 우리는 이렇게 그릴수 밖에 없다. A-B-C, B-A-C, C-B-A. (각각의 가지수가 더 있지만, 여기까지만 표현하겠다. 그 이유는 다음줄에서 바로 나온다!)
트리의 순회도 똑같다. 부모-왼쪽-오른쪽(부모-오른쪽-왼쪽), 왼쪽-부모-오른쪽(오른쪽-부모-왼쪽), 왼쪽-오른쪽-부모(오른쪽-왼쪽-부모)로 순회할 수 있다. (통상적으로 오른쪽-부모-왼쪽 혹은 오른쪽-왼쪽-부모 의 오른쪽 먼저보다 왼쪽을 먼저 순회한다.)
각각의 순회 방법에 있어서 현재 내 노드(부모)를 기준으로 이름이 붙여지는데, 각각 전위순회, 중위순회, 후위순회라고 부른다(preorder, inorder, postorder).
순회를 할 때 연결된 모든 노드를 순회해야 하며, 이를 재귀를 이용하여 쉽게 나타낼 수 있다.
Full Binary Tree
다시 사진을 보면서 생각해보자! 설명은 preorder만 하고, 나머지 inorder, postorder는 직접 생각해보길 바란다. 원리는 같다.
순회를 A로부터 시작한다고 하자. 그러면 A를 돌고, 왼쪽자식 B, 오른쪽자식 I를 돌아야 한다. 그런데 이 때, B를 순회할 때 또 다시 (부모)-(왼쪽자식)-(오른쪽자식)을 돌아야 하는 상황이 발생하고, B-C-F를 돌게 된다. 마찬가지로 C를 확인할 때 또 다시 C-D-E순으로 돌게 된다. 이후 왼쪽자식이 더 이상 돌 게 없으니, B는 F를 확인하게 된다.
즉, (나)-(왼쪽자식)-(오른쪽자식)을 먼저 돌 때 A-B-C-D-E-F-G-H-I ... 순으로 순회해야하는 것을 알 수 있다.
