층 수 구하기/flr(층수 구하기 알고리즘)

20151114

*이문제는 dovelet 에 있는 알고리즘 문제입니다.

층 수 구하기/flr 

프로그램 명: flr

제한시간: 1 초

주희는 심심해서 다음과 같이 수를 쓰기 시작 했다.

이렇게 수를 쓰는 경우 어떤 수가 몇 층에 있는지가 궁금해 졌다.

참고로 100 은 7 층에 존재 한다.

입력

32 비트 정수 범위내의 값이 입력으로 주어진다.

출력

층 수를 출력한다.

입출력 예

입력

100

출력

7

♣n 개의 노드를 가지는 complete binary tree 의 depth 를 구하는 문제입니다.

문제 풀이

1) 풀이

import java.io.PrintStream;
import java.util.Scanner;

public class Main {
 
	Scanner sc = new Scanner(System.in);
	static PrintStream p = System.out;
	int n;
	
	public static void main(String[] args) {
		Main m = new Main();
		m.input();
		m.Output();
	}
	void input(){
		n = sc.nextInt();
	}
	void Output(){
		boolean onoff = true;
		int flow = 1;
		while (onoff) {
			if(Math.pow(2, flow) <= n){
				flow += 1;
			}else{
				break;
			}
		}
		p.println(flow);
	}  
}

*짧게 코딩하는것도 좋지만 저는 함수와 객체 지향개념을 쓰고 싶어서 이렇게 코딩 했습니다.

(아래에 보시면 흰트개념이 있는데(log 밑? 값이 2 )를 이용해서 쉽게 풀 수 있습니다.)

그런데 자바에선 log(밑값)2 인 함수를 Math 클래스에서 함수로 제공해주지 않고 또 log2를 어찌 구현해야 할지 몰라서 다른 방식을 이용 했습니다.

위에 문제에서 피라미드를 보시면 층이 생길때마다 그전 층의 2배만큼 커집니다. 그럼 마지막 층은 2의 n승 -1 이 제일 큰수가 되는거죠.

그럼 조건문과 반복문을 이용해서 층을 점점 증가 시키면서  n 값이 증가된 층 값보다 커질때 그전까지 증가했던 층의 수를 출력해주면 됩니다.

말이 더 어렵네요. 그림을 그리고 코드를 따라가면 어렵지 않게 이해할거라 믿어요.ㅎ

아래 흰트 개념이 있습니다. 

흰트 개념을 이용하셔도 쉽게 풀 수 있습니다.

log 를 왜 쓰는지는 아직 이해 못했습니다. 저에게 수학은 정말 힘드네요. :(

흰트 개념

[증명] n 개를 노드를 가진 complete binary tree 의 depth

레벨  에서 가질 수 있는 수의 범위는

양변에 밑을 2 로 하는 log 를 취하면 

1  을 더하면 

    혹은