JAVA/알고리즘
[공유] 시간 복잡도와 공간복잡도 정리
시간복잡도와 공간복잡도 관련하여 많이 잊어먹어서 정리된 사이트를 공유합니다. https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/
재귀 문제점과 꼬리 재귀와의 함수 비교
재귀함수는 자기 자신을 호출하는 방식으로 다양하게 사용된다. 재귀함수에는 일반재귀와 꼬리 재귀가 있는데 나는 둘 다 사용해온것 같은데 정확한 명칭과 사용방법에 대해서는 제대로 알지 못하는 것 같아 정리하게 되었다. 코드도 짧고 간결한 장점이 있다. 하지만 결국에는 함수를 계속 호출하는 방식이기에 함수가 끝나고 돌아가야할 위치에 대해 스택에 기록된다. 계속 함수가 호출되어 스택 영역의 최대 이상의 크기를 넘어가게 되면 Stack over flow가 발생한다. 편리함을 찾다가 더 위험한 상황이 초래된다. 그리고 성능적으로도 문제가 있다. 피보나치 수열의 예시를 확인해보자.12345private static int factorial(int n) { if (n == 1) return n; return n * f..
백준 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..
정렬알고리즘 - 버블정렬
1234567891011121314151617for(int i = money.length; i>0; i--){ for(int j=0;jmoney[j+1]){ temp=money[j]; money[j]=money[j+1]; money[j+1]=temp; } } }Colored by Color Scriptercs
10진수 2진수 변환
1234567891011121314151617181920212223242526272829303132package java8; import java.util.Scanner; public class MainClass { public static void main(String args[]) { Scanner in = new Scanner(System.in); StringBuilder result = new StringBuilder(); int input; System.out.print("10진수를 입력하세요. : "); input = in.nextInt(); //10 -> 2진수 while (input != 1) { result.insert(0, String.valueOf(input % 2)); input =..