Algorithm

피보나치 수를 구하는 가장 기초적인 알고리즘입니다. $$ F_n = F_{n-1} + F_{n-2} (n>=2) $$ 점화식을 그대로 구현하여 재귀적으로 풀어내면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 /** * */ import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; /** * @author jaeji * */ public class Main { static int fibonacci(int no) { if(no==0) return 0; else if(no==1) return 1; else return fibonacci(no-1)+fibonacci(no-2); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) ); //BufferedReader br = new BufferedReader( new FileReader("input.txt" ) ); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int result = fibonacci(n); System.out.println(result); } }

피보나치 수 두번째 입니다. DP로 푸는 문제입니다. 점화식으로 풀때는 Top-down 방식이지만 DP로 풀때는 Bottom-up 방식입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; /** * @author jaeji * */ public class Main { static long[] arr = new long[91]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) ); //BufferedReader br = new BufferedReader( new FileReader("input.txt" ) ); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); arr[1] = 1; for(int i=2;i<=n;i++) { arr[i] = arr[i-1] + arr[i-2]; } System.out.println(arr[n]); } }

Scanner는 성능이 떨어지기 때문에 입력이 많은 경우 문제가 생깁니다. BufferedReader와 StringTokenizer를 이용해 입력받는 것을 습관화 시키는게 좋습니다. ...

드디어 네트워크플로우 처음에 목표한 알고리즘이 MCMF까지였기 때문에, 곧 결과에 쫓기듯 공부할 필요는 없을꺼같다. 배울 알고리즘이 참 많지만 사실 그런알고리즘은 내가 앞으로 쓸일이 있을까 하는 의문이 들어서 필요성을 느끼지 못하겠다. 그리고 필요하다면 그 때 배워서 사용하면 될꺼같기도 하다. 시험문제로 나온다면.. 그저 슬플수 밖에 ...

완전 초급용은 아닌 dp 이제 자신감이 좀 붙는고만 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 import java.awt.Point; import java.util.HashMap; class Solution { static int[] intarr; public static int solution(String arr[]) { HashMap<Point,Integer> dmax = new HashMap<Point,Integer>(); HashMap<Point,Integer> dmin = new HashMap<Point,Integer>(); int len = arr.length; int max_temp = 0; int min_temp = 0; int max = 0; int min = 0; // 숫자로 변환, 및 기본값 세팅 intarr = new int[arr.length]; for(int i=0;i<len;i++) { if(arr[i].equals("+")) { intarr[i] = 1001; // 플러스는 1001로 치환 } else if (arr[i].equals("-")) { intarr[i] = 1002;// 마이너스는 1002로 치환 } else { intarr[i] = Integer.parseInt(arr[i]); dmax.put(new Point(i,i), intarr[i]); dmin.put(new Point(i,i), intarr[i]); } } for(int i=2;i<len;i+=2) { //하나의 연산을 포함하는 길이에서 입력의 모든 연산을 포함하는 길이가 될때까지, 길이의 증가는 +2씩(연산자 하나, 숫자하나) for(int j=0;j+i<len;j+=2) { // 0자리 부터 시작해서 해당 순서의 길이까지 반복, 최대 길이를 넘지 않아야 함 max_temp = 0; min_temp = 0; max = Integer.MIN_VALUE; min = Integer.MAX_VALUE; for(int k=j;k<i+j;k++) { // +,- 연산이 오는 경우 범위에서의 min과 max를 구한다. if(intarr[k]==1001) { max_temp = dmax.get(new Point(j,k-1)) + dmax.get(new Point(k+1,i+j)); min_temp = dmin.get(new Point(j,k-1)) + dmin.get(new Point(k+1,i+j)); if(max_temp>max) max = max_temp; if(min_temp<min) min = min_temp; } else if(intarr[k]==1002) { max_temp = dmax.get(new Point(j,k-1)) - dmin.get(new Point(k+1,i+j)); min_temp = dmin.get(new Point(j,k-1)) - dmax.get(new Point(k+1,i+j)); if(max_temp>max) max = max_temp; if(min_temp<min) min = min_temp; } } dmax.put(new Point(j,j+i), max); dmin.put(new Point(j,j+i), min); } } return dmax.get((new Point(0,len-1))); } }

BFS로 구현했는데, 효율성 테스트에서 자꾸 시간초과가 나서 고민했던 문제 알고보니 중복방문을 방지하기 위한 코드가 없었음.. 방문 확인의 중요성!! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 import java.util.LinkedList; import java.util.Queue; import java.awt.Point; class Solution { public static int solution(int[][] maps) { int X = maps[0].length; int Y = maps.length; boolean[][] visited = new boolean[Y][X]; Queue<Point> q = new LinkedList<Point>(); int x = 0; int y = 0; int size = 0; int cnt = 0; Point p = new Point(); q.add(new Point(Y-1,X-1)); while(q.isEmpty()==false) { size = q.size(); cnt++; for(int i=0;i<size;i++) { p = q.peek(); x = p.y; y = p.x; q.remove(); if(visited[y][x]==true) continue; maps[y][x] = 0; visited[y][x] = true; if(x==0 && y==0) { return cnt; } if(x-1>-1 && maps[y][x-1]==1) { //왼쪽 한칸 q.add(new Point(y,x-1)); } if(x+1<X && maps[y][x+1]==1) { //오른쪽 한칸 q.add(new Point(y,x+1)); } if(y-1>-1 && maps[y-1][x]==1) { //위쪽 한칸 q.add(new Point(y-1,x)); } if(y+1<Y && maps[y+1][x]==1) { //아래쪽 한칸 q.add(new Point(y+1,x)); } } } return -1; } }

문제를 잘 파악하면 어렵지 않은 문제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import java.util.HashSet; import java.util.Iterator; public class Solution { public int solution(int[] nums) { HashSet<Integer> abc = new HashSet<Integer>(); for(int i=0;i<nums.length;i++) { abc.add(nums[i]); } if(abc.size()>nums.length/2) return nums.length/2; else return abc.size(); } }

알고리즘을 풀다 보면 좌표압축이라는 테크닉이 필요합니다.저는 좌표압축을 “순위가 중요한 알고리즘에서, 입력값의 갯수보다 입력값의 범위가 클 때 사용하는 방법”, 이라고 생각하고 있습니다. 1차원의 좌표로 예를 들어보겠습니다.n개의 x값 을 입력 받아, 입력 중 두개의 x1,x2를 선택하여 사이에 존재하는 점의 개수를 구하는 작업이 있다고 가정합시다. x의 범위는 int형의 범위인 -2^31 ~ 2^31-1 이고 중복은 없습니다. n은 5000 이하입니다.입력은 n : 7, -2^31, -10000, 0 , -2000, 3, 6, 30000 , x1 = -10000, x2 = 30000 대략적으로 보면 그림과 같이 나타나게 됩니다. ...

타입에러 때문에 제공하는 정렬함수를 쓸 수 없을때 그리고 형변환 하기 귀찮을 때 comparator, comparable의 재정의 없이 간단하게 정렬할 수 있는 방법입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 //예; sort라는 오름차순정렬 함수가 정의된 경우 int[] B = ~~~~~~ //오름차순 정렬 sort(B); //내림차순 정렬 for(int i=0;i<B.length;i++) B[i] = -B[i] sort(B); for(int i=0;i<B.length;i++) B[i] = -B[i]

(n)을 했을때 fib(0),와 fib(1)이 몇번 콜되는지 구하는 문제입니다. 전략 : 전역 변수 2개를 할당해, fib(0)을 부를때 증가시키고, fib(1)을 부를때 증가시키는 것으로 해서 풀었습니다. ...