Algorithm

토마토의 상태가 행렬로 주어질 때, 모든 토마토가 익는데 걸리는 시간을 구하는 문제입니다. 큐를 이용해서 BFS로 풀었습니다. 공부많이 됐네용. 입력값이 행렬로 주어져서 인접행렬로 풀었는데, 다음에는 인접 리스트로 푸는 문제를 도전해보겠습니다 ...

안녕하세요. 오랜만에 카카오 코드 페스티벌 풀이를 쓰네요.문제가 어렵다 보니 쉽게 손이 안 갑니다. ㅎㅎ 4번 문제는 https://www.welcomekakao.com/learn/challenges/630 에서 확인하실 수가 있습니다. 동적계획법으로 푸는 문제인데요. 저는 도중에 몰라서 간단하게 설명된카카오의 풀이를 참고했습니다. 풀이를 보면 동적계획법(DP)을 아시는 분이면 푸실 수가 있는데요.주의하실 점은 나머지 연산(모듈로 연산)입니다. 처음에 저는 마지막 리턴 값에 만 나머지 연산을 적용해서계속 정답 처리를 못 받고 있었는데, 값을 계산할 때 매번 해줘야 한다고 다른 분들께서 알려주셨어요.그리고 저는 dp의 크기를 최대 입력값 500보다 하나 크게 잡았습니다.i, j 위치에서 값을 계산할 때 i-1, j-1의 값을 불러오기 때문에 0인 경우에 인덱스 범위를 벗어나서if문을 넣어 계속 체크를 해주는 것보다는 0행과 0열에 0으로 된 값을 넣어서 해결했습니다. ...

안녕하세요. 오늘은 카카오 코드 페스티벌 예선에 나온 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 알고리즘을 이용해서 푸시면 됩니다. ...

주의해야 할것은 오버플로우! 나머지 연산이 포인트 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)); } }