땅콩의 일기장

재귀(Recursion) 어떤 함수(혹은 프로시져, 서브 프로그램)에서 직접적으로 혹은 간접적으로 자기 자신 함수를 다시 호출하는 것. 무한 재귀에 빠지지 않도록 base case를 잘 정해주고, 반복되는 부분은 recursive step로 정의해준다. Function call stack 프로그램 중 함수를 호출하면 (Context switching) 지금 실행중인 함수의 지역변수 등 가지고 있는 정보를 저장해두어야 한다. 그리고 새로운 함수 수행이 완료되면 다시 원래의 함수로 제어가 돌어오고, 기존의 정보를 복원해서 사용하여야 한다. 이때 현재 함수가 가지고 있던 정보를 저장하는 연속적인 메모리 공간을 activation record라고 하고, 이 activation record를 call stack ..

stable sorting algorithm 크기가 같은 데이터가 정렬 이후에도 입력된 순서 그대로 유지되는 알고리즘 ex) Merge sort, Insertion Sort, Bubble Sort, Cocktail Shaker Sort In-Place algorithm 입력 데이터를 저장하는 메모리 이외는 상수 크기의 메모리만 필요한 알고리즘 ex) Heap sort, Insertion sort, Selection sort, Shell sort, Bubble sort, Comb Sort, Cocktail shaker sort Bubble sort 인접한 두 숫자를 비교하여 두 수의 정렬순서가 맞지 않는 경우에는 교환(swap)한다. (stable, in-place) public static void bu..

재귀란? 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는것을 말한다. 간단한 예로 팩토리얼을 들 수가 있다. n! = n * (n-1) 팩토리얼을 메서드로 구현하여 사용한 코드는 다음과 같다. import java.util.*; public class Main { //양의 정수 n의 팩토리얼을 반환합니다. static int factorial(int n){ if(n>0) return n * factorial(n-1); else return 1; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("정수를 입력하세요.:"); int x = scanner.n..

큐란? 데이터를 일시적으로 쌓아놓은 자료구조이다. 데이터의 입출력순서는 선입선출(먼저 들어온 것이 먼저 나감)이다. 큐에 데이터를 넣는 작업을 인큐(enqueue), 꺼내는 작업을 디큐(dequeue)라고 한다. 즉 어떤 데이터를 인큐하면 큐의 맨 뒤에 데이터를 추가하고, 데이터를 디큐하면 큐의 맨 앞 데이터를 제거한다음 한칸씩 앞으로 당긴다. 근데 이렇게 디큐할때의 복잡도는 O(n)으로, 데이터를 하나 꺼낼때마다 이런 처리를 한다면 효율이 매우 떨어진다. 이런 문제점은 링버퍼를 사용하여 큐를 구현하면 개선할 수 있다. 프런트와 리어 값을 업데이트하며 인큐와 디큐를 수행하게 되기 때문이다. [ O(1) ] 다음은 링버퍼로 큐를 구현하는 코드이다. 구간별 설명은 주석으로 대신한다! import java.u..

스택이란? 데이터를 일시 저장하는 자료구조. 데이터의 입출력순서는 후입선출(나중에 들어온 것이 먼저 나감)이다. 스택에 데이터를 넣는 작업을 푸시(push) 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다. 자바에서 메서드를 호출하고 실행할때도 내부적으로 스택을 사용한다. 다음은 스택클래스 IntStack을 구현하고 이를 사용하는 프로그램이다. 각 메서드에 대한 설명은 주석에 적혀있다! import java.util.*; public class Main { static class IntStack{ private int max; //스택 용량 private int ptr; //스택 포인터 private int[] stk; //스택 본체 //실행시 예외: 스택이 비어있음 public class Emp..

이진검색 이진검색은 요소가 오름차순 또는 내림차순으로 이미 정렬된 배열에서 검색하는 알고리즘이다. 배열의 가운데 인덱스와 찾고싶은 값을 비교하면서 검색범위를 반씩 줄여가며 원하는 값을 찾아낸다. [ O(log n) ] import java.util.*; public class Main { //길이가 n인 배열 a에서 key를 이진검색합니다. static int binSearch(int[] a, int n, int key){ int pl = 0; //검색 범위의 첫 인덱스 int pr = n-1; //검색 범위의 끝 인덱스 do{ int pc = (pl + pr) / 2; //중앙 인덱스 if(a[pc]==key) //검색 성공 return pc; else if(a[pc]

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 값을 찾을때까지 맨 앞부터 순서대로 요소를 검색하면 된다. 이것을 선형검색(linear search)또는 순차검색(sequential search)이라고 한다. 그리고 배열을 이용해 선형검색을 수행하는 코드는 다음과 같다. import java.util.*; public class Main { //배열의 길이가 n인 배열 a에서 key라는 값을 검색하여 존재하면 인덱스 i를, 존재하지않으면 -1을 반환한다. static int seqSearch(int[] a, int n, int key){ for (int i = 0; i < n; i++) { if(a[i]==key) return i; //검색성공 } return -1; //검색실패 } public s..

자바의 2차원 배열을 이용하여 한 해의 경과일수를 구하는 코드이다. 평년과 윤년을 2차원배열에 담아 사용했다. import java.util.*; public class Main { static int[][] mdays = { {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, //평년의 일수 {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, //윤년의 일수 }; //year년은 윤년인가 평년인가? (윤년이면 1, 평년이면 0) static int isLeap(int year){ return (year%4==0 && year%100!=0 || year%400==0) ? 1 : 0; } //y년 m월 d일의 그 해 경과 일 수를 ..

다음은 1000 이하의 소수를 나열하는 코드이다. public class Main { public static void main(String[] args) { int counter = 0; //나눗셈의 횟수 for (int n = 2; n

원하는 10진수를 2진수~36진수중 원하는 기수로 변환해주는 코드이다. package com.company; import java.util.*; public class Main { //정수값 x를 r진수로 변환하여 배열 d에 아랫자리부터 넣어두고 자릿수를 반환. static int cardConvR(int x, int r, char[] d){ int digits = 0; //변환후의 자릿수 String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; do{ d[digits++] = dchar.charAt(x%r); //x를 r로 나눈 나머지를 저장 x/=r; }while (x != 0); return digits; } public static void main(Str..