이진탐색

 이진 탐색(binary search)는 정렬되어 있는 자료들의 집합에서 특정 자료를 찾고자 할 때 많이 사용되며 매우 빠른 탐색 알고리즘이다. 이진 탐색은 '퀵정렬'과 유사하게 '분할 후 정복(divide and conquer)'의 전략을 사용한다. 이 전략을 사용하는 알고리즘은 문제를 나누어 해결해 나가는 방법이기 때문에 실행시간은 log의 설징을 갖는다. 특히 문제의 크기를 정확히 양분하는 경우에는 최악의 경우라고 logN의 성능을 보장한다.

 이진 탐색의 탐색 시간은 'T = K * logN'으로 O(logN)이다. 선형 탐색의 시간보다 상당히 빠르지만 이진 탐색은 반드시 정렬이 되어있어야 한다. 그러므로 정렬되지 않는 리스트의 경우에는 정렬하는 비용 또한 상당히 들 것이다. 이와 같은 단점에도 불구하고 다음과 같은 상황에서 이진 탐색은 효율적인 성능을 제공한다.

 1) 새로운 자료가 추가되었어도 모든 자료가 재정렬이 일어나지 않는 경우 -> 해싱, 인덱스를 이용하는 경우

 2) 획기적으로 빠르고, 효율적인 자료의 재정렬이 가능한 자료 구조를 사용할 경우 -> B-트리 계열의 트리 구조 사용


다음은 이진 탐색의 JAVA 소스이다.

package Search;

public class BinarySearch {
	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

		binarySearch(2, arr);
	}

	public static void binarySearch(int iKey, int arr[]) {
		int mid;
		int left = 0;
		int right = arr.length - 1;

		while (right >= left) {
			mid = (right + left) / 2;

			if (iKey == arr[mid]) {
				System.out.println(iKey + " is in the array with index value: " + mid);
				break;
			}

			if (iKey < arr[mid]) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}

		}
	}
}


+

기술면접에서 이진탐색을 왜 구현하지 못했을까... 자료구조 시간에 그렇게 공부하고 이해하고 구현하고 다 해본 것을ㅠㅠ

기본을 먼저 보고 갔어야 하는 건데, 괜히 다른 알고리즘을 너무 보고 갔더니 간단한 알고리즘조차 어렵게만 생각하고 복잡하게 풀려고 한 것 같다.. 그래서 다시 기본기를 훑어보고자 이렇게 블로그에 남겨놓는다.

'대학 생활 > JAVA' 카테고리의 다른 글

[JAVA] 기수정렬(RadixSort)  (0) 2015.11.20
[JAVA] 피보나치 - 재귀사용  (0) 2015.11.13
[JAVA] 퀵정렬(QuickSort)  (0) 2015.11.06
[JAVA] 딕스트라 최단경로(Dijkstra Shortest Paths)  (0) 2015.10.31

'대학 생활 > JAVA' 카테고리의 다른 글

[JAVA] 이진탐색(Binary Search)  (0) 2015.11.27
[JAVA] 기수정렬(RadixSort)  (0) 2015.11.20
[JAVA] 퀵정렬(QuickSort)  (0) 2015.11.06
[JAVA] 딕스트라 최단경로(Dijkstra Shortest Paths)  (0) 2015.10.31

'대학 생활 > JAVA' 카테고리의 다른 글

[JAVA] 피보나치 - 재귀사용  (0) 2015.11.13
[JAVA] 퀵정렬(QuickSort)  (0) 2015.11.06
[JAVA] 병합정렬(MergeSort)  (0) 2015.10.30
[JAVA] 버블정렬(BubbleSort)  (0) 2015.10.23

삽입정렬

- 안정정렬

- 시간복잡도: 

- 설명: 왼쪽에 있는 항목들은 정렬된 것으로 가정하고, 증가하는 인덱스의 값을 삽입하는 방법.

- 특징: 정렬대상이 적거나, 이미 부분적으로 정렬되어 있는 상황일 경우 효율적. 선택정렬과 버블보다는 빠름



'대학 생활 > JAVA' 카테고리의 다른 글

[JAVA] 병합정렬(MergeSort)  (0) 2015.10.30
[JAVA] 버블정렬(BubbleSort)  (0) 2015.10.23
[JAVA] 선택정렬(SelectionSort)  (0) 2015.10.09
[JAVA] 쉘정렬(ShellSort)  (0) 2015.10.02

'대학 생활 > JAVA' 카테고리의 다른 글

[JAVA] 버블정렬(BubbleSort)  (0) 2015.10.23
[JAVA] 삽입정렬(InsertionSort)  (0) 2015.10.16
[JAVA] 쉘정렬(ShellSort)  (0) 2015.10.02
[JAVA] 달팽이 만들기  (0) 2015.06.23

쉘정렬, (불안정) 간격을 두어 나눈 하위배열을 삽입정렬 반복


StringTokenizer 클래스 사용방법

토큰을 따로 지정하지 않으면 공백을 구분으로 나누어진다. 따로 구분문자를 지정하려면 생성자에 넣어준다.

StringTokenizer st = new StringTokenizer("this is a test");
while(st.hasMoreTokens()) {
    System.out.println(st.nextToken());
}
StringTokenizer st = new StringTokenizer("a|b|c|d", "|");
while(st.hasMoreTokens()) {
    System.out.println(st.nextToken());
}

String클래스의 split() 사용하기

String[] result = "this is a test.".split("\\s");
for(int i = 0; i < result.length; i++) {
    System.out.println(result[i]);
}


참고사이트 Link

'대학 생활 > JAVA' 카테고리의 다른 글

[JAVA] 쉘정렬(ShellSort)  (0) 2015.10.02
[JAVA] 달팽이 만들기  (0) 2015.06.23
[JAVA] 리스트와 배열 간 복사 방법  (0) 2015.04.08
[JAVA] String 인코딩  (0) 2015.04.01
import java.util.Arrays;
import java.util.List;

public class Test {
	public void copyByArray(int[] source) {
		int[] target = new int[source.length];
		// arraycopy(원본 배열, 복사 시작 위치, 대상 배열, 대상 배열의 시작 위치, 복사 길이);
		System.arraycopy(source, 0, target, 0, source.length);
	}

	public List copyByList(Integer[] args) {
		List list = (List) Arrays.asList(args);
		return list;
	}

}
package report1;

import java.io.UnsupportedEncodingException;

public class CharacterIncoding {

	public static void main(String[] args) {

		String word = "무궁화 꽃이 피었습니다.";
		try {
			System.out.println("utf-8 -> euc-kr        : "
					+ new String(word.getBytes("utf-8"), "euc-kr"));
			System.out.println("utf-8 -> ksc5601       : "
					+ new String(word.getBytes("utf-8"), "ksc5601"));
			System.out.println("utf-8 -> x-windows-949 : "
					+ new String(word.getBytes("utf-8"), "x-windows-949"));
			System.out.println("utf-8 -> iso-8859-1    : "
					+ new String(word.getBytes("utf-8"), "iso-8859-1"));
			System.out.println("iso-8859-1 -> euc-kr        : "
					+ new String(word.getBytes("iso-8859-1"), "euc-kr"));
			System.out.println("iso-8859-1 -> ksc5601       : "
					+ new String(word.getBytes("iso-8859-1"), "ksc5601"));
			System.out.println("iso-8859-1 -> x-windows-949 : "
					+ new String(word.getBytes("iso-8859-1"), "x-windows-949"));
			System.out.println("iso-8859-1 -> utf-8         : "
					+ new String(word.getBytes("iso-8859-1"), "utf-8"));
			System.out.println("euc-kr -> utf-8         : "
					+ new String(word.getBytes("euc-kr"), "utf-8"));
			System.out.println("euc-kr -> ksc5601       : "
					+ new String(word.getBytes("euc-kr"), "ksc5601"));
			System.out.println("euc-kr -> x-windows-949 : "
					+ new String(word.getBytes("euc-kr"), "x-windows-949"));
			System.out.println("euc-kr -> iso-8859-1    : "
					+ new String(word.getBytes("euc-kr"), "iso-8859-1"));
			System.out.println("ksc5601 -> euc-kr        : "
					+ new String(word.getBytes("ksc5601"), "euc-kr"));
			System.out.println("ksc5601 -> utf-8         : "
					+ new String(word.getBytes("ksc5601"), "utf-8"));
			System.out.println("ksc5601 -> x-windows-949 : "
					+ new String(word.getBytes("ksc5601"), "x-windows-949"));
			System.out.println("ksc5601 -> iso-8859-1    : "
					+ new String(word.getBytes("ksc5601"), "iso-8859-1"));
			System.out.println("x-windows-949 -> euc-kr     : "
					+ new String(word.getBytes("x-windows-949"), "euc-kr"));
			System.out.println("x-windows-949 -> utf-8      : "
					+ new String(word.getBytes("x-windows-949"), "utf-8"));
			System.out.println("x-windows-949 -> ksc5601    : "
					+ new String(word.getBytes("x-windows-949"), "ksc5601"));
			System.out.println("x-windows-949 -> iso-8859-1 : "
					+ new String(word.getBytes("x-windows-949"), "iso-8859-1"));
		} catch (UnsupportedEncodingException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

equals() 와 hashCode() 는 함께 오버라이드 할 것.

자료형

해시 값 계산 방법

boolean

(value ? 1 : 0)

byte, char short, int

(int) value

float

Float.floatToIneBits(value)

double

Double.doubleToLongBits(value)

 String 및 기타 객체

"test".hashCode() 

package Test;

public class Test {
	int intVal;
	String strVal;

	public Test(int intVal, String strVal) {
		this.intVal = intVal;
		this.strVal = strVal;
	}

	public int getIntVal() {
		return intVal;
	}

	public void setIntVal(int intVal) {
		this.intVal = intVal;
	}

	public String getStrVal() {
		return strVal;
	}

	public void setStrVal(String strVal) {
		this.strVal = strVal;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + intVal;
		result = prime * result + ((strVal == null) ? 0 : strVal.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Test other = (Test) obj;
		if (intVal != other.intVal)
			return false;
		if (strVal == null) {
			if (other.strVal != null)
				return false;
		} else if (!strVal.equals(other.strVal))
			return false;
		return true;
	}

}

이클립스에서는 만드는 방법

단축키 Shift + Alt + S 

Generate hashCode() and equals()... 선택




int(정수)를 String(문자열)로 바꾸는 여러가지 방법

평소에 정수타입의 변수를 문자열로 바꿀 때 +"" 를 자주 사용하였다. 편리하기도하고 습관이 되었기 때문이다. 그러다가 갑자기 궁금해져서 바꾸는 방법에 대해서 페이스북 생활코딩 그룹에 도움을 청했다. 댓글을 통해서 2012년도에 작성된 String.valueOf(int) vs ""+int라는 글을 보았고, 몇가지 더 추가해서 실험해보았다. 실험에 사용된 코드는 아래와 같다.

코드

package Test1;

import java.io.IOException;

public class TestClass {
	public static void main(String... args) throws IOException {
		for (int i = 0; i < 10; i++) {
			long svo = perfStringValueOf();
			long qqp = perfQuoteQuotePlus();
			long its = perfIntegerToString();
			long sf = perfStringFormat();
			System.out.printf("String.valueOf() : %.3f\t", svo / 1e3);
			System.out.printf("Integer.toString() : %.3f\t", its / 1e3);
			System.out.printf("\"\"+ : %.3f\t", qqp / 1e3);
			System.out.printf("String.Format() : %.3f\n", sf / 1e3);
		}
	}

	private static long perfStringValueOf() {
		long start = System.nanoTime();
		final int runs = 100000;
		String s;
		for (int i = 0; i < runs; i++) {
			s = String.valueOf(i * i);
			if (s.length() < 1)
				throw new AssertionError();
		}
		long time = System.nanoTime() - start;
		return time / runs;
	}

	private static long perfQuoteQuotePlus() {
		long start = System.nanoTime();
		final int runs = 100000;
		String s;
		for (int i = 0; i < runs; i++) {
			s = "" + i * i;
			if (s.length() < 1)
				throw new AssertionError();
		}
		long time = System.nanoTime() - start;
		return time / runs;
	}

	private static long perfIntegerToString() {
		long start = System.nanoTime();
		final int runs = 100000;
		String s;
		for (int i = 0; i < runs; i++) {
			s = Integer.toString(i * i);
			if (s.length() < 1)
				throw new AssertionError();
		}
		long time = System.nanoTime() - start;
		return time / runs;
	}

	private static long perfStringFormat() {
		long start = System.nanoTime();
		final int runs = 100000;
		String s;
		for (int i = 0; i < runs; i++) {
			s = String.format("%d", i * i);
			if (s.length() < 1)
				throw new AssertionError();
		}
		long time = System.nanoTime() - start;
		return time / runs;
	}
}

결과


첫 실행 속도로 보았을 땐 Integer.toString() < String.valueOf() < ""+ < String.Format()  이다. 하지만 여러번 반복하고 평균적으로 보았을 땐 ""+ < Integer.toString() < String.valueOf() < String.Format() 이었다.

속도와 간단함으로 보았을 땐 ""+ 이었지만 추후에 좀더 성능을 고려해서 다시 실험해보아야겠다.

메서드 배열 만들기

public class Node {
    ...
    public void goNorth() { ... }
    public void goSouth() { ... }
    public void goEast() { ... }
    public void goWest() { ... }

    interface MoveAction {
        void move();
    }

    private MoveAction[] moveActions = new MoveAction[] {
        new MoveAction() { public void move() { goNorth(); } },
        new MoveAction() { public void move() { goSouth(); } },
        new MoveAction() { public void move() { goEast(); } },
        new MoveAction() { public void move() { goWest(); } },
    };

    public void move(int index) {
        moveActions[i].move();
    }
    public void allMove() {
        for (MoveAction m : moveActions)
            m.move();
    }
}

참고


toArray() 사용법

보톤 반복문을 통해 하나하나 배열에 넣는 방법을 사용하는데, 속도도 느리고 효율성도 좋지 않다고 한다. 또한 arr = (String[])list.toArray(); 와 같은 코드를 사용한다면 List의 요소가 정확히 어떤 형태로 형변환을 해야 할지 명시하지 않아 java.lang.ClassCastException이 발생한다.


package Test;

import java.util.ArrayList;
import java.util.List;

public class Example {
	public static void main(String[] args) {
		List list = new ArrayList<>();
		list.add("test1");
		list.add("test2");
		list.add("test3");

		String[] arr = (String[]) list.toArray(new String[list.size()]);
		for (String str : list) {
			System.out.println(str);
		}
	}

}

IP주소는 하드코딩을 피해라.

책 '자바 코딩, 이럴 땐 이렇게'에서 이번에도 꼭 알아두어야 할 것 같은 부분을 보고 남기려고 한다. 서버 프로그램을 작성할 때 서버의 IP를 소스코드에 하드코딩하는 습관이 바람직하지 않다고 한다.

첫 번째 이유는 관리적인 측면과 유지보수의 측면에서 볼 수 있다. 말 그대로 서버의 IP가 바뀌었거나, 소스 수정을 할 때 하나하나 찾아가며 바꿔야 하기 때문이다. 

두 번째 이유는 보안적인 측면인데, 자바 소스는 디컴파일(decompile)이 가능하기 때문이다. 즉 JVM이 인식하는 코드 .class코드가 유출된다면 IP정보가 쉽게 유출된다는 점이다.


해결 방안

package Test;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.util.Properties;

public class Example {
	private static final String DEFAULT_PROPERTIES_PATH = "d://test.properties";

	private static String serverIP;

	public static void main(String[] args) throws Exception {
		setServerIP(Example.getKey("serverIp"));
	}

	public static String getKey(String key) throws Exception {
		String value = null;
		InputStream is = new FileInputStream(DEFAULT_PROPERTIES_PATH);
		Properties properties = null;
		try {
			properties = new Properties();
			properties.load(is);
			value = properties.getProperty(key);

		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();

		} finally {
			try {
				is.close();
			} catch (IOException e) {

			}
		}
		return value;
	}

	public static String getServerIP() {
		return serverIP;
	}

	public static void setServerIP(String serverIP) {
		Example.serverIP = serverIP;
	}

}

varargs : Variable Argument List

매개변수가 가변적일 때 사용하는 가변인자. 즉, 여러개의 파라미터를 가변적으로 사용할 때 사용된다. 

방법은 아래와 같이 사용한다. API


    public void printFormat(String... strs) {
        System.out.println("size : " + strs.length);
        for (String str : strs) {
            System.out.printf(" %15s", str);
        }
    }


PreparedStatement 에서 SQL 문 확인하기

System.out.println(preparedStatement);

https://stackoverflow.com/questions/2683214/get-query-from-java-sql-preparedstatement

BigDecimal 객체 생성 방법, 비교

객체를 생성할 때 실수가 아닌 String 형태 혹은 valueOf()를 사용하고 비교할 때는 compareTo()를 사용한다.

import java.math.BigDecimal;
public class Example {
    public static void main(String[] args) {
        BigDecimal val1 = BigDecimal.valueOf(1.234);
        BigDecimal val2 = new BigDecimal("1.234");

        System.out.println(val1.compareTo(val2) == 0);
    }
}

불필요한 메모리 낭비 방지하기

빈번히 사용되는 수는 매번 인스턴스를 생성하여 사용하지 않고 미리 정의된 상수를 사용한다.

import java.math.BigInteger;

public class Exam {
    public static void main(String[] args) {
        BigInteger biZero = BigInteger.ZERO;
        BigInteger biOne = BigInteger.ONE;
        BigInteger biTen = BigInteger.TEN;

        BigInteger biTest1 = new BigInteger("10000000");
        BigInteger biTest2 = BigInteger.valueOf(1000000);

        System.out.println(biTest1.intValue());
    }
}

summary

먼저 아파치 톰캣이 이클립스에 연동되어있다고 가정한다.
서블릿으로 웹요청을 받아들여 디비랑 통신하기 위한 코드에 대한 템플릿이다. 

DB와의 통신은 서블릿 코드에서 DBConnect.java를 통해 디비에 접속하고 Dao를 통해 질의문을 작성한다.


template_server.zip

git

프로젝트 생성

이클립스 > File > New > Dynamic Web Project

서블릿 파일 생성

File > New > Servlet > 아래 코드

package templete_server.servlet;

import java.io.IOException;
import java.io.PrintWriter;
import java.sql.ResultSet;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class GetData
 */
@WebServlet(name = "GetData", urlPatterns = { "/GetData" })
public class GetData extends HttpServlet {
	private static final long serialVersionUID = 1L;

	/**
	 * @see HttpServlet#HttpServlet()
	 */
	public GetData() {
		super();
		// TODO Auto-generated constructor stub
	}

	protected void processRequest(HttpServletRequest request,
			HttpServletResponse response) throws ServletException, IOException {
		response.setContentType("text/html;charset=UTF-8");
		PrintWriter out = response.getWriter();

		/////////////////////////////////////////////////////////////////
		// HTML SOURCE CODE
		out.println("<html>");
		out.println("<head>");
		out.println("<title>Servlet GetData</title>");
		out.println("</head>");
		out.println("<body>");
		out.println("<h1>Servlet GetData at " + request.getContextPath()
				+ "</h1>");
		out.println("<p>");
		out.println("get data : " + request.getParameter("id"));
		out.println("</body>");
		out.println("</html>");

		out.println("");
		// HTML SOURCE CODE
		/////////////////////////////////////////////////////////////////

		String id = request.getParameter("id");
		System.out.println(id);
	}

	/**
	 * @see HttpServlet#doGet(HttpServletRequest request, HttpServletResponse
	 *      response)
	 */
	protected void doGet(HttpServletRequest request,
			HttpServletResponse response) throws ServletException, IOException {
		processRequest(request, response);
	}

	/**
	 * @see HttpServlet#doPost(HttpServletRequest request, HttpServletResponse
	 *      response)
	 */
	protected void doPost(HttpServletRequest request,
			HttpServletResponse response) throws ServletException, IOException {
		processRequest(request, response);
	}

}

DB Connect ( Mysql)

jdbc나 mysql 드라이버는 'WebContent > WEN-INF > lib' 안에 넣어주어야 한다.

첫 번째 코드는 DB를 연결하기 위함이고, 두 번째 코드는 질의문을 서버에 작성할 수 있다.


DBConnector.java
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;

public class DBConnector {
	private String driver = "com.mysql.jdbc.Driver";
	private String url = "jdbc:mysql://localhost:3306/dbschema?useUnicode=true&characterEncoding=UTF-8";
	private String user = "userid";	//DB user ID
	private String pwd = "password";	//DB user Password
	private Connection conn = null;
	
	public Connection getConnection(){
		try{
			Class.forName(driver);
		}catch(ClassNotFoundException e){
			System.out.println("BusInfoSystem : 드라이버 로딩 실패(getConnection)");
			System.out.println(e.getMessage());
		}
		try{
			conn = DriverManager.getConnection(url,user,pwd);
		}catch(SQLException e){
			System.out.println("BusInfoSystem : DB 연결 실패(getConnection)");
			System.out.println(e.getMessage());
		}
		return conn;
	}
}

tempateDao.java
package templete_server.dao;

import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.Statement;

public class templateDao {

	private DBConnector dbc;

	public templateDao() {
		dbc = new DBConnector();
	}

	public int getData(int arg1) {
		int result = 0;
		Connection conn = null;
		PreparedStatement ps = null;
		ResultSet rs = null;
		String sql = new String("select * from dbtable where ID = ?;");

		conn = dbc.getConnection();
		try {
			ps = conn.prepareStatement(sql);
			ps.setInt(1, arg1);
			rs = ps.executeQuery();
			rs.first();
			while (true) {
				result = rs.getInt("id");
				if (rs.isLast())
					break;
				rs.next();
			}
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			closeDB(rs, ps, conn);
		}

		return result;
	}

	/**
	 * DataBase 자원 반환
	 * 
	 * @param rs
	 * @param ps
	 * @param conn
	 */
	private void closeDB(ResultSet rs, Statement ps, Connection conn) {
		if (rs != null) {
			try {
				rs.close();
			} catch (Exception e) {
			}
		}
		if (ps != null) {
			try {
				ps.close();
			} catch (Exception e) {
			}
		}
		if (conn != null) {
			try {
				conn.close();
			} catch (Exception e) {
			}
		}
	}
}


Boolean 객체의 사용법

인스턴스화하지 않고 static 필드인 TURE, FALSE를 사용한다.

public class BooleanExample {
    public static void main(String[] args) {
        // Boolean bool = new Boolean(ture);
        // Boolean bool2  = Boolean.valueOf(false);

        Boolean bool = Boolean.TRUE;
        Boolean bool2 = Boolean.FALSE;
     }
}

+ Recent posts