이번 포스트에서는 재귀가 왜 필요한지와 기본적인 재귀의 흐름에 대해서 살펴보자. 재귀함수 재귀란?재귀(再歸, recursion )란 러시아의 전통인형 마요르카 처럼 내 안에 또 다른 나 즉 모양이나 동작은 동일하지만 크기만 작은 나를 찾아가는 과정이다. 우리는 수학 시간에도 재귀의 성격을 잘 배운적이 있다. 1부터 n까지의 곱을 구하는 펙토리얼 연산이 그 예이다.n! = 1 * 2 * 3 * ... * (n-2) * (n-1) * n 여기서 맨 마지막의 *n을 제외하면 나머지는 (n-1)! 이 된다. 즉 크기만 1작아진 펙토리얼이다.이렇게 하나의 문제 내에 크기는 다르지만 동일한 성격의 다른 문제를 하나 이상 포함하고 있는 것을 재귀적 구조라고 한다. 이런 재귀를 프로그래밍 함수에 적용한 것을 재귀 함수..

입출력 관련 예제 풀어보기 BJ_B3_10952_A+B_5더보기마지막 입력 처리에 신경쓸 것https://www.acmicpc.net/problem/10952  BJ_B2_10953_A+B_6더보기,를 delimiter로 사용https://www.acmicpc.net/problem/10953   BJ_B3_11022_A+B_8더보기출력문 포멧https://www.acmicpc.net/problem/11022  BJ_B2_11721_열개씩끊어출력하기더보기출력문 포멧https://www.acmicpc.net/problem/11721

백준 사이트에 입출력 속도 비교하는 내용이 있는데 유용한 자료같다.https://www.acmicpc.net/blog/view/56 입력 속도 비교여러가지 언어와 입력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다. 방법: 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일www.acmicpc.net  https://www.acmicpc.net/blog/view/57 출력 속도 비교여러가지 언어와 출력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다. 방법: 총 N개의 줄에 1부터 10,000,000까지의 자연수를 한 줄에 하나씩 출력하는 시간을 측정. 10번 측정해서 평www.acmicpc.net 이중 Ja..

이번 포스트에서는 표준 출력에 대해서 살펴보자. 표준 출력 표준 출력 메서드자바에서 표준 출력으로는 PrintStream이 사용되는데 일반적으로 System.out.을 통해서 얻을 수 있다. 다음은 PrintStream에서 출력을 위해 제공되는 메서드이다. 메서드 명선언부와 설명print()public void print(Object obj)obj를 콘솔에 출력한다.println()public void println(Object x)x를 콘솔에 출력하고 줄바꿈 한다.printf()public PrintStream printf(String format, Object ... args)지시자로 구성된 format에 의거해서 args를 콘솔에 출력한다.  출력 포멧마지막에 사용된 printf()는 다양한 포멧문..

Scanner는 입력을 가장 편하게 처리할 수 있는 클래스이지만 BufferedReader에 비해 상대적으로 느리다. 이번 포스트에서는 BufferedReader에 대해 알아보자. * 사실 많은 APS 사이트에서 Java의 표준 입력으로 Scanner를 지정하고 있기 때문에 Scanner로 대부분 문제를 풀 수 있다. 다만 약간의 시간을 더 줄여야할 필요가 있다면 BufferedReader를 썼을 때 확실히 성능의 향상을 이룰 수 있다. BufferedReader 생성과 데이터 읽기BufferedReader 역시 Scanner와 마찬가지로 키보드, 파일, 문자열을 통해서 데이터를 읽어올 수 있다.// 키보드를 이용한 입력 처리BufferedReader br = new BufferedReader(new I..

이번 포스트에서는 자바에서 입력을 가장 손쉽게 처리할 수 있는  Scanner에 대해서 알아보자. Scanner 기본 사용법Scanner를 만들기 위한 생성자는 InputStream 타입의 파라미터 source를 받는다.public Scanner(InputStream source) {...}이 source가 어디에서 자료를 받을것인지를 결정하는데 일반적으로 키보드에서 받을 경우 System.in, 파일로 부터 받을 경우 FileInputStream이 사용된다. Scanner에서 데이터를 읽어들일 때는 일반적으로 hasNextXXX() --> nextXXX()의 두 단계를 거친다.여기서 XXX는 데이터 형에 따라 여러 가지 형태가 있다. 각각의 데이터 즉 토큰에 대한 구분은 공백문자('\t',space, ..

Union-Find 연산의 성능 개선 어떤 요소들이 하나의 그룹으로 구성될 수 있는지 파악하기 위한 Disjoint-Set 자료구조를 처리하기 위해 Union-Find 연산을 사용한다. 이번 post에서는 union-find 연산의 성능 개선을 위한 path compression과 rank 활용에 대해 알아보자. 기본 코드는 다음과 같다. package ch07_unionfind; import java.util.Arrays; public class P01_UnionFindTree { static int[] src = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; static int[] repres = new int[src.length + 1]; // 각각의 멤버를 대표자로 하는 집합 생성 s..

LinkedList vs ArrayList Java에서 순서 있는 목록을 관리하는 인터페이스는 java.util.List 인터페이스이다. List의 특징은 순서가 있는 데이터의 집합으로 순서가 있기 때문에 데이터의 중복이 허용된다. List는 인터페이스이기 때문에 직접 객체를 생성할 수 없고 구현체 class가 필요하다. 이 구현체의 가장 대표적인 클래스가 java.util.ArrayList와 java.util.LinkedList이다. 먼저 각각의 특성에 대해 살펴보자. ArrayList ArrayList는 배열에서 출발한 List ArrayList는 이름에서 풍기듯이 내부적으로 배열을 만들고 데이터를 관리한다. transient Object[] elementData; // non-private to s..