본문 바로가기

플밍 is 뭔들/알고리즘

Recursion의 응용 [Counting Cells in a Blob] ※ 문제 설명 private static int BACKGROUND_PIXEL = 0; private static int IMAGE_PIXEL = 1; private static int VISITED_IMAGE_PIXCEL = 2; private static int[][] grid ={ {1,0,0,0,0,0,0,1}, {0,1,1,0,0,1,0,0}, {1,1,0,0,1,0,1,0}, {0,0,0,0,0,1,0,0}, {0,1,0,1,0,1,0,0}, {0,1,0,1,0,1,0,0}, {1,0,0,0,1,0,0,1}, {0,1,1,0,0,1,1,1} }; public static void main(String[] args) { int x=0; int y=0; int blob =0; ArrayList c.. 더보기
Recursion의 응용 [미로찾기1] ※ 재귀함수를 이용한 미로찾기 - 재귀함수를 이용하여 위의 미로의 형태에서 출구를 찾는 알고리즘을 구현 한다. - 문제에서는 findExit 메소드의 리턴값을 boolean으로 두고 출구가 있느냐 없느냐를 true, false로 나타내는데서 끝냈지만 개인적으로 탐색한 경로를 알고싶어서 아래와 같은 식으로 구현했다. public class mazeEx { private static int PATH_WAY = 0; private static int WALL = 1; private static int VISITED_WAY =2; private static int EXIT = 3; private static boolean IS_ESCAPE = false; private static int [][] MAZE = .. 더보기
순환(RECURSION)의 개념과 기본 예제3 ※ 순환 알고리즘 설계(Design Recursion) 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 된다. 모든 case는 결국 base case로 수령되어야 함. 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔라 - 암시적 변수와 명시적 변수? **일반적인 반복문을 이용해서 배열탐색을 할때 아래와 같은 방식으로 구현을 한다. 여기서 명시적 변수는 n,data,target이 되고 암시적 변수는 i가 된다.(변수 선언이 되어있지 않다.) public static int search(int n, int [] data, int target){ for(int i=0;iend){ return -1; }else if(target==data[begin]).. 더보기
순환(RECURSION)의 개념과 기본 예제2 ※ 순환적으로 사고하기(Recursive Thinking) - Recursion은 수학함수뿐 아니라 다른 많은 문제들도 해결 가능하다.(반복문) ※ 예제 - 글자 길이구하기 public class ex { public static void main(String[] args) { int iLength = getLength("hello"); System.out.println(iLength); } public static int getLength(String str){ if(str.equals("")){ return 0; }else{ return 1+getLength(str.substring(1)); } } } - 글자 거꾸로 출력하기(CASE1) public class ex { public static vo.. 더보기
순환(RECURSION)의 개념과 기본 예제1 ※ RECURSION? - 자기 자신을 다시 호출하는 메소드(재귀함수) - 무한루프에 빠질 수 있으므로 적어도 하나의 breaking point를 만들어준다. (Base Case) - recursion을 반복하다보면 결국 base case로 수렴해야 한다(Recursive Case) ※ 예제 - Factorial(n!) public class factorial { public static void main(String[] args) { int iResult = fn_factorial(5); System.out.println(iResult); } public static int fn_factorial(int n){ if(n==1){ return 1; }else{ return n*fn_factorial(n-.. 더보기
알고리즘의 분석, 공간 복잡도, 시간복잡도 ※ 알고리즘 분석 - 알고리즘의 실행 시간 및 기타 자원의 사용량을 분석 - 기타 자원으로는 메모리, 저장장치, 통신 등이 있다. - 알고리즘 분석에는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)를 이용한다. - 주로 수행시간(시간 복잡도)을 분석한다. ※ 공간 복잡도 - 알고리즘을 실행하여 종료할때까지 필요한 기억장치의 크기 - 알고리즘과 무관한 부분 : 프로그램 코드를 저장하기 위한 공간, 프로그램을 수행하기 위해 시스템이 필요로 하는 공간 - 알고리즘과 밀접한 부분 : 문제를 해결하기 위해 필요한 공간 ex)변수를 저장하기 위한 공간 예제) 공간 복잡도의 계산 public int fn_abc(int a, int b, int c){ return (a+b+c.. 더보기

티스토리툴바