농부공학자

재귀 함수란 자기 자신을 재 호출하는 함수를 말한다. 예를 들어 코드를 보자 package algorithm; public class recursive_fun { public static void main(String[] args) { recursive_function(); } public static String recursive_function() { System.out.println("재귀 함수 호출"); return recursive_function(); } } 위와 같은 코드가 있다면 recursive_function() 함수를 호출한 뒤 "재귀 함수 호출"을 print 하고 다시 recursive_function() 함수를 재호출하여 "재귀 함수 호출"을 print 하는 방식을 반복한다. 그 ..

알고리즘 문제를 풀다보면 중복된 문자를 제거해야하는 경우가 많이 생긴다. 맨날 헷갈리니까 아예 정리해놓으려고 한다. import java.util.Scanner; public class duplicateChar { public static void main(String[] args) { duplicateChar main = new duplicateChar(); Scanner scan = new Scanner(System.in); String str = scan.next(); System.out.println(main.solution(str)); } public static String solution(String str) { String answer = ""; for(int i = 0; i < str.l..

그리디 알고리즘은 문제를 해결하는 과정에서 가장 좋다고 생각하는 방법을 선택하는 알고리즘이다. 예를 들어 노드 값의 최대 합은 5 -> 7 -> 9를 거쳐 21임을 알 수 있다. 그러나 그리디 알고리즘을 사용하면 그때그때 최대값이 될 것이라고 추측되는 값을 사용하게 된다. 따라서 5 다음에 7, 10, 8 중 가장 큰 값인 10을 사용하고 4, 3 중 큰 값인 4를 사용하게 된다. 이처럼 그리디 알고리즘이 문제의 해결에 있어서 최적의 해를 매번 보장하지는 않는다. 그러나 그리디 알고리즘은 계산 속도가 빠르다. 그리디 알고리즘이 적절하다고 판단되는 문제에서는 최적의 해를 빠르게 산출할 수 있다. 예시 출처 : 이것이 취업을 위한 코딩 테스트다 예를 들어 N = 5이고 각 모험가의 공포도가 2 3 1 2 2..

이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 예시를 보자!! 이렇게 가운데에 있는 값을 확인하면서 검색하는 방법이 이진검색이다. 처음 시작할 때 a = 0이고 b = n-1값이면 검색할 가운데 값은 (a+b) / 2 값이 된다. 오름차순일 때 키값이 찾으려는 값보다 크면 b값은 중앙값 - 1 이 되고 키값이 찾으려는 값보다 작으면 a값은 중앙값 + 1이 된다. 이 방법을 코드로 짜보면 import java.util.Scanner; public class binarysearch { static int binSearch(int[] x, int n, int key) { int a = 0; int b = n - 1; do { int c = (a..

정수 n에 대하여 아래의 조건을 만족시키면 소수임을 알 수 있다. 2부터 n-1까지의 어떤 정수로도 나누어떨어지지 않는다. 먼저 어떤 정수 이하의 소수를 모두 나열하는 알고리즘을 직관적으로 풀어보자. public class PrimeNumber { public static void main(String[] args) { int counter=0; for(int n = 2; n

정숫값을 기수로 변환하는 알고리즘을 살펴보자. 기수 = 수를 나타내는 데 기초가 되는 수로 10진수, 2진수, 8진수, 16진수가 있다. 10진수 10진수는 아래 10종류의 숫자를 사용해 수를 나타낸다. 0 1 2 3 4 5 6 7 8 9 10진수의 각 자리는 아랫자리부터 100,10¹, 10², ...으로 10의 거듭제곱 값을 갖는다. 1234 = 1 x 10³ + 2 x 10² + 3 x 10¹ + 4 x 100 와 같이 풀어쓸 수 있다. 8진수 8진수는 아래 9종류의 숫자를 사용하여 수를 나타낸다. 0 1 2 3 4 5 6 7 8진수의 각 자리는 아랫자리부터 80, 8¹, 8², ...으로 8의 거듭제곱 값을 갖는다. 5306 = 5 x 8³ + 3 x 8² + 0 x 8¹ + 0 x 80 와 같이..

배열 요소를 역순으로 정렬하는 알고리즘을 살펴보자. 배열 역순 정렬 과정 위 그림은 n=7 일 때 역순으로 정렬하는 과정을 그린 그림이다. 교환 횟수는 n / 2 이며 n이 홀수일 때 가운데 요소는 교환하지 않기 때문에 나머지는 버려준다. 위의 예시에선 n = 7이므로 7 / 2 = 3이므로 3번의 교환이 이루어졌다. 교환 방법 위 그림에서 파란색의 자릿수를 i라고 하면 i와 n-i-1과의 교환이 계속해서 이루어지게 된다. 여기서 배열 안 값을 교환하는 방법으로 변수 t를 활용할 수 있다. 따라서 값의 교환은 다음과 같이 이루어진다. 메서드 swap 구현하기 배열 안의 두 요소를 교환하는 것은 자주 쓰이므로 독립적인 메서드로 구현하는 것이 좋다. //배열 요소 a[idx1]과 a[idx2]의 값 교환하기..