Posts

안녕하세요. 오늘은 카카오 코드 페스티벌 예선에 나온 5번 캠핑 문제에 대해 풀이를 해보겠습니다. 문제는 https://www.welcomekakao.com/learn/challenges/667 에서 확인하실 수 있습니다. 시간 복잡도 간단히 모든 경우의 수를 다 고려한다고 생각하고 시간 복잡도를 간단히 생각해보면, 1개의 쐐기에 대해 본인 쐐기를 제외한 N-1 개의 쐐기와 쌍을 지어서, 나머지 N-2 쐐기에 대해 주어진 조건을 만족하는지 확인해야 합니다.쐐기가 N 개이니까, N*(N-1)*(N-2), 이므로 O(n^3)이 되기 때문에 풀기가 힘들어집니다. 팁으로 N의 개수와 시간 복잡도를 어림짐작할 때 쓸 수 있는 방법으로, 주먹구구 법칙이라는 게 있는데요. 간단히 말해서, O(x) 일 때 x가 1억을 넘어가면 시간 초과가 나기 쉽다는 말입니다.위의 경우 x = n^3이고, n이 최대 5000이기 때문에 5000개에 대해서 수행할 때는 1250억 정도가 나옵니다. 제한된 시간 내에는 절대 불가능합니다. 적어도 N^2 까지는 줄여줘됩니다. ※자세한 내용은 http://book.algospot.com/estimation.html 를 참고하세요. 해당 문제에서는 S[i][j] 배열을 만들어 (0,0)을 기준으로 x좌표가 i, y좌표가 j인 사각형 내부에(경계선 포함) 존재하는 쐐기의 개수를 미리 구함으로써쐐기 쌍이 선택됐을 때(N*(N-1) 개) 텐트가 만들어질 수 있는 조건을 S를 참고해 바로 구함으로써 N^2의 시간에 수행할 수 있게 됩니다. (x, y) , (x2, y2) 쌍의 사각형 내부에 쐐기가 있는지 없는지를 확인하려면 ...

이전에 포스팅한 정석 풀이 말고 다른 풀이를 보여드리겠습니다. 다른 정답들을 보다가 출제의도와는 다르지만 최적화를 통해 시간내에 풀었고(하지만 시간 차이는 꽤 납니다), 코드도 깔끔하니 예뻐서 포스팅 합니다. 파란색의 주석을 보면서 읽으시면 이해하기 쉬울꺼에요. ...

처음으로 참가한 알고리즘 대회인데, 이 대회 덕분에 알고리즘 공부를 시작하게 되었죠. 본선 진출 1문제 차이로 탈락했었습니다. 이 문제는 1번 문제인데요, 행렬로 주어진 그림에서 영역(상하좌우에서 같은 색으로 된 부분은 같은 영역)의 갯수와 최대 영역의 크기를 구하는 문제입니다. 재귀 문제입니다. flood_fill 알고리즘을 이용해서 푸시면 됩니다. ...

플랫폼 별로 다 만들어주고 html코드까지 제공해줌 히트다 히트 https://realfavicongenerator.net/

자세히 보아야 예쁘다 오래 보아야 사랑스럽다 너도 그렇다

주의해야 할것은 오버플로우! 나머지 연산이 포인트 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public class TryHelloWorld { static long[] dp = new long[10000]; public int tiling(int n) { dp[0] = 1; dp[1] = 2; for(int i=2;i<n;i++) { dp[i] = (dp[i-2]*2)+(dp[i-1]-dp[i-2]); if(dp[i]>99999) dp[i]%=100000; } return (int) dp[n-1]; } public static void main(String args[]) { TryHelloWorld tryHelloWorld = new TryHelloWorld(); // 아래는 테스트로 출력해 보기 위한 코드입니다. System.out.print(tryHelloWorld.tiling(262)); }}

Date 오브젝트 쓰기! 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 import java.text.ParseException; import java.text.SimpleDateFormat; import java.util.Date; public class TryHelloWorld { public String getDayName(int a, int b) { String answer = ""; SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd"); SimpleDateFormat sdf2 = new SimpleDateFormat("E"); String dateInString = "2016-"+a+"-"+b; Date date; try { date = sdf.parse(dateInString); answer = sdf2.format(date).toUpperCase(); } catch (ParseException e) { } return answer; } public static void main(String[] args) { TryHelloWorld test = new TryHelloWorld(); int a=5, b=24; System.out.println(test.getDayName(a,b)); } }

2개의 값에 대하여 gcd를 이용해 lcm을 구하는 것을 N개에 대해 반복함 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 public class NLCM { public long gcd(long a,long b) { if(a==0) return b; else return gcd(b%a,a); } public long lcm(long a,long b) { return a*b/gcd(a,b); } public long nlcm(int[] num) { long answer=num[0]; for(int i=0;i<num.length-1;i++) { answer = lcm(answer,num[i+1]); } return answer; } public static void main(String[] args) { NLCM c = new NLCM(); int[] ex = { 2, 6, 8, 14 }; // 아래는 테스트로 출력해 보기 위한 코드입니다. System.out.println(c.nlcm(ex)); } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class StringExercise{ String getMiddle(String word){ int len = word.length(); if(len%2==0) {//짝수 return word.substring(len/2-1, len/2+1); } else {//홀수 return word.substring(len/2, len/2+1); } } // 아래는 테스트로 출력해 보기 위한 코드입니다. public static void main(String[] args){ StringExercise se = new StringExercise(); System.out.println(se.getMiddle("power")); } } 아래와 같은 풀이도 있다. 짝수와 홀수를 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 class TryHelloWorld { public int findLargestSquare(char [][]board) { int max=0; int min=0; for(int i=0;i<board.length;i++) { for(int j=0;j<board[0].length;j++) { if(board[i][j]=='O') board[i][j]=1; else board[i][j]=0; } } for(int i=0;i<board.length-1;i++) { for(int j=0;j<board[0].length-1;j++) { if(board[i][j]==0||board[i][j+1]==0||board[i+1][j]==0||board[i+1][j+1]==0) continue; else{ min = board[i][j] < board[i][j+1] ? (board[i][j] < board[i+1][j] ? board[i][j] : board[i+1][j]) : (board[i][j+1] < board[i+1][j] ? board[i][j+1] : board[i+1][j]); board[i+1][j+1] = (char) (min+1); if(board[i+1][j+1]>max) max=board[i+1][j+1]; } } } return max*max; } public static void main(String[] args) { TryHelloWorld test = new TryHelloWorld(); char [][]board ={ {'X','O','O','O','X'}, {'X','O','O','O','O'}, {'X','X','O','O','O'}, {'X','X','O','O','O'}, {'X','X','X','X','X'}}; System.out.println(test.findLargestSquare(board)); } }