자바
Java의 거대 정수를 담을 수 있는 BigInteger
대학교 학창시절에 BigInteger만들기를 자료구조 시간에 C로 만들어 본적이 있다. 그리고 실질적으로 실무에서는 Long값을 벗어난 데이터를 담아서 사용해본적이 없어 자바의 BigInteger라는 객체가 존재하는지 몰랐다. 매주 진행하는 알고리즘 스터디에서 문제를 풀다가 Long값 이상의 데이터가 필요해서 찾다가 사용하게 되었다. 몇 가지 정리해보자. BigInteger 객체 생성 방법 팩토리 메서드와 기존 constant 객체로써 제공하는 방법으로 BigInteger객체를 만들 수 있다.12345678910// ConstantBigInteger zero = BigInteger.ZERO;BigInteger one = BigInteger.ONE;BigInteger ten = BigInteger.TEN;..
백준 6603번 로또 문제 풀이
매주 진행중인 알고리즘 공부 중 오늘은 백준 6603번 DFS와 백트래킹 문제를 풀어보자. #문제 https://www.acmicpc.net/problem/6603#풀이과정사용자로 부터 로또번호를 생성할 번호의 개수 k를 입력받고 입력받은 k개의 숫자를 이용하여 로또를 오름차순으로 6개짜리 배열을 만들어 출력해야한다. 처음에 문제를 보자마자 재귀를 써야겠다는 생각은 하였지만 백트래킹을 써야하는지는 감이 오지 않아서 고민을 많이 했다. 시작점을 0번째 부터 로또를 딱 만들수 있는 크기인 k - 5번까지 사용하는 반복문을 만들어서 배열을 만든다. 그리고 findLottoNum 메소드에 현재 인덱스와 만들고 있는 String값을 전달해준다. 그럼 현재 인덱스 바로 앞에 위치할 숫자를 구해서 String에 붙혀..
백준 알고리즘 10988번 문제 팰린드롬 문제 풀기
팰린드롬은 단어를 앞뒤로 거꾸로 했을 때 동일한 단어를 이야기한다. 코드가 아주 간단하다.입력받은 String 길이의 반만큼 반복문을 돌면서 앞과 뒤가 맞는지 체크하고 앞에서오는 인덱스 i와 뒤에서 오는 인덱스 j가 서로 교차하는 순간까지 서로 다르지 않으면 1을 반환하고 체크하던 도중에 한부분이라도 같지 않으면 0을 반환하면 된다.자세한 코드는 아래 또는 github에서 확인 가능하다. 12345678910111213141516171819202122232425262728293031323334package test; import java.util.Scanner; public class WedulPlindrom { public static void main(String args[]) { Scanner sc..
피보나치 수열 재귀, DP, loop 방법으로 구현하고 차이 확인
피보나치 수열을 이용한 재귀 프로그래밍은 대학교 1학년때 처음 재귀를 구하면서 접했었다. 당시에는 재귀의 예제로써 피보나치와 팩토리얼함수를 구현하는 것으로 소개되었다.하지만 시간복잡도에 대해 다시 공부하던 중 우리가 배웠던 피보나치 수열의 재귀는 좋은 방식이 아니라는 것을 알게되었다. 피보나치 수열의 3가지 방식에 대해 구현해보고 차이를 느껴보자. 우선 피보나치 수열은 현재 값을 구하기위해서는 이전의 값(n-1)과 그 더 이전의 값(n-2)을 더하면서 구한다.N = (n - 2) + (n -1)0, 1, 1, 2, 3, 5, 8, 13, 21, 34........ 1) 재귀방식재귀로 구현하는 방식은 가장 익숙한 방법이지만 매번 구할 때 마다 처음까지 가야하는 가장 안좋은 BigO(2^n)의 시간 복잡도를..
백준 알고리즘 2167 2차원 배열의 합 DP 알고리즘으로 풀기 (JAVA)
알고리즘 문제를 계속해서 연습해야겠다고 생각한 시점에서 백준 알고리즘 2차원 배열문제를 풀어보기로 했다. 문제는 간단하게 말하면 2차원 배열이 주어졌을 때, 특정 i, j 위치에서 x, y위치 까지의 value들의 합을 구하는 문제이다. 나는 특정 알고리즘을 생각하지 않고 단순하게 접근해서 array에 value를 다 넣어놓고 1,1에서 2, 3 까지 value를 구하라고 하면 1,1에서 2,3까지 반복문을 돌면서 value를 다 더했었다. 하지만 그렇게 하는게 아니라 DP 알고리즘을 사용해야 한다고 한다. 우선 자세한 문제는 백준 홈페이지에서 확인하시면 된다. https://www.acmicpc.net/problem/2167 그리고 먼저 말했던 단순하게 접근한 코드는 다음과 같다. 1 2 3 4 5 6..
규칙 74 - Serializable 인터페이스를 구현할 때는 신중하라.
클래스 선언부에 implements Serializable를 붙히면 간단하게 직렬화 가능 객체를 만들수 있다. 그렇기 때문에 개발자 입장에서는 Serializable을 붙혀서 직렬화 기능을 만드는 것이 간단하다고 생각할 수 있다. 여기서 먼저 직렬화에 대해서 간단한 예제를 보고 가자. import java.io.Serializable; public class Student implements Serializable { private static final long serialVersionUID = 1L; public Student(String name, int number, int height) { this.name = name; this.number = number; this.height = heigh..
규칙 73 - 스레드 그룹은 피하라.
스레드 그룹(thread group)은 원래 applet을 격리시켜 보안문제 해결할 목적으로 만들어졌으나 성공하지 못했다. 그러면 이런 스레드 그룹은 왜 남아있는가? 아예 쓸곳이 없는가? 그렇지는 않다. 스레드 기본연산을 여러 스레드에 동시에 적용할 수 있도록 하는 기능을 가지고 있다. 하지만 대부분이 deprecated 되었다. 결론을 이야기하자면 이미 다 페기가 되어버린 기능이다. 그렇기 때문에 신경쓸 것 없이 사용하지 말아야한다. 출처 : 조슈아 블로크, 『 Effective Java 2/E』, 이병준 옮김, 인사이트(2014.9.1)
규칙 72 - 스레드 스케줄러에 의존하지마라.
실행해야 할 스레드가 많을 경우 어떠한 스레드를 얼마나 오랫동안 실행할지 결정은 스레드 스케줄러가 진행한다. 운영체제마다 스레드 스케줄러는 다르기 때문에 아무리 운영체제에서 효율적으로 진행한다고 하더라고 이에 의존하여 프로그램을 제작해서는 안된다. 정확하고 좋은 스레드 프로그램은 의존하는것이 아니라 실행가능한 스레드의 개수가 프로세수 개수보다 넘지 않도록 제작하는 것이다. 그렇게되면 스레드 스케줄러가 순차적으로 스레드를 실행시켜줄뿐 정책에 신경쓰지않는다. 그렇다면 실행중인 스레드의 개수를 최대한 줄일 수 있는 방법은 무엇일까? 바로 사용하지 않는 스레드는 실행하지 않고 정지하거나 종료해야한다. 그래서 바로 직전에 공부했던 스레드 풀을 사용하여 적절하게 스레드를 관리하면 좋은 프로그램을 만들 수 있다. 그..
규칙 71 - 초기화 지연은 신중하게 하라
Lazy initialization(초기화 지연)은 필드 초기화를 실제로 그 값이 쓰일 때까지 미루는 것이다. 대부분 초기화 지연의 이유는 초기화의 비용이 증가하고 사용빈도가 특별한 경우에 사용하는 필드에 대해서 그렇게 적용한다. 만약 그렇지 않은 경우에도 초기화 지연을 사용하면 어떨까?이럴 경우 클래스를 초기화하고 객체를 생성하는 비용은 줄이지만 필드 사용 비용은 증가시킨다. 그럼 동기화가 필요한 다중 스레드 환경에서는 초기화 지연은 어떻게 구현해야할까? 생각만 해도 어렵다. 몇가지 방법을 살펴보자.우선 초기화 지연을 사용하지 않고 진행하는 일반적인 초기화는 다음과 같다.1234567891011 public class TestClass { // 일반적인 초기화 기법 // 클래스가 처음 로드될 때 바로 ..
규칙 70 - 스레드 안전성에 대해문서로 남겨라.
클래스를 사용할 때 클래스의 객체와 정적 메서드가 병렬적으로 이용되었을 때, 어떠한 부작용이 있을 수 있는지 안전한지에 대한 정보가 없으면 추후에 큰 문제를 야기할 수있다. JavaDoc에서 synchronized 키워드를 통해 병렬설 지원 여부를 확인할 수있다고 알고 있으나 실상 그렇지 않다. 왜냐하면 Javadoc이 만드는 문서에는 Javadoc이 들어가지 않는다. 왜냐하면 synchronized 키워드는 메서드의 구현 상세에 해당하는 정보이며, 공개 API의 일부가 아니기 때문이다. 그렇기 때문에 synchronized 키워드를 통해 판단해서는 안되고 병렬적으로 사용해도 되는지의 여부는 문서에 남겨져 있어야 한다. 출처 : 조슈아 블로크, 『 Effective Java 2/E』, 이병준 옮김, 인사..