프로그래민👨‍💻

간단한 시뮬레이션 문제였다. 이 문제의 경우 for문을 이용한 간단한 문제였지만 최악의 경우가 200,000 * 500 이므로 일중 for문 안에 해결을 해야한느 문제였다. 정렬을 필요로 하는 문제였기에 priortyqueue를 사용하였고, Pos 클래스를 만들어 comprable을 상속받아 compareTo함수를 구현하였다. 이 문제에서는 주의할것이 있었다. 바로 0으로 나누는 경우인데, 보통의 경우 0으로 나누면 Exception뜨게 된다. 하지만 캐스팅을 한경우 별도의 Exception 없이 infinty나 NaN이 뜨게 된다. 항상 0으로 나누는 것은 예외처리를 다시한번 봐주는 습관을 길러야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..

이분탐색을 사용하여 최소값을 탐색하는 문제였다. 이 문제를 접근할때 이분탐색을 접근한이유가 있다. 문제의 조건에 의해 나올수 있는 최대시간은 1,000,000,000명 * 1,000,000,000분 임으로 1중 for문으로 돌릴 수 있는 1억이 그냥 넘어가게 되어, 자연스럽게 최적을 찾을 수 있는 이분탐색을 사용해보았다. 문제에서 조심해야 할 것이 있는데 파라미터로는 int형이 들어오고 리턴형은 long형이기에 이것을 처리해주지 않으면 테스트케이스를 해결하지 못한다. 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 package programmers;..

단순 구현으로 접근하였다. 우선 알파벳의 순위를 정해주는 order 배열을 통해 우선순위를 정해주었다. 그리고 알파벳을 방문한다면 visit 배열을 통해 방문체크를 해주었다. 만족하지 않는 경우는 2가지를 생각하였다. 첫째, 현재 알파벳보다 우선순위가 높은 알파벳인데 방문을 안했다면 거짓, 두번째, 현재 알파벳보다 우선순위가 낮은 알파벳인데 방문을 했다면 거짓. 이런식으로 접근하였다. 체크해야할 알파벳이 26개, 또한 문자열도 최대 26이므로 26*26 이 큰 숫자가 아니어서 단순히 접근하여 풀이를 하였다. 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 ..

스택을 이용하는 괄호의 쌍 문제이다. 이문제는 남은 괄호를 처지하는 횟수를 카운팅해주는 문제이기에 조금 특별한 방식으로 접근하였다. 스택에다가 오직 여는 괄호 { 만을 가지고 있도록 하는방법이다. 만일 } 가 스택에 들어올 차례일때 스택이 비어있다면 카운팅을 해주고 { 를 넣어주는 방식으로 접근하여 풀었다. 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 package study4; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; public cl..

2493번 탑과 비슷한 스택을 사용하는 문제이다. 문제를 접근할때 현재 빌딩에서 몇개를 볼수있느냐가 아니라 현재 빌딩이 몇개의 빌딩에서 보여지냐 를 기준으로 접근하였다. 그래서 스택을 이용하여 순서대로 입력을 받았다. 그리고 입력을 받은 순간 만일 스택의 top에 있는 빌딩의 높이가 현재 들어온 빌딩보다 높다면 그순간의 스택사이즈를 answer에 추가해주었고, 만일 현재 들어온 빌딩이 더 크다면 스택의 top에 위치한 빌딩을 pop해주었다. 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 package study4; import java.io.BufferedReader; import ja..

DP를 이용하여 쉽게 구할 수 있는 문제이다. 이 문제는 끝자리의 자연수가 가장 중요한 문제이다. 그래서 다음과 같은 설계를 해보았다. dp[N][i] => N의 자리수를 가진 자연수 중에서 i의 수를 맨끝 자리로 가지는 자연수, 예를 들면 534 는 dp[3][4]에 속하는 하나의 자연수가 된다. 이와 같은 것을 이용하여 다음과 같은 점화식을 세웠다. dp[N][i]= dp[N-1][i-1] + dp[N-1][i+1] 단, i=0일땐 i+1 만 i=9일땐 i-1만 해준다. 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 package boj.base; import java.io.Buffere..

DP를 이용한 문제이다. 이 문제의 기본 점화식은 다음과 같다. dp[n]= dp[n-1] (1을 더해주는 경우) + dp[n-2] (2를 더해주는 경우) + dp[n-3] (3을 더해주는 경우) , 하지만 이 문제에서는 연속하여 두개이상의 자연수를 사용하면 안되는 조건이 생겼기에 다음과 같이 dp배열을 설계하였다. dp[n][i] => i의 숫자를 맨마지막 숫자로 가지는 경우 예를 들면 n=3일 경우 dp[3][1]은 2+1 이 있으므로 1, dp[3][2]은 1+2 이 있으므로 1, dp[3][3]은 3이 있으므로 1이 나오게 된다. 이런식으로 최종 점화식을 구하면 dp[n][1] = dp[n-1][2] + dp[n-1][3], 1을 더하는 경우 n-1에서 2와 3으로 끝나는 것에 더할 수 있음. d..

DP를 사용하는 문제이다. 이 문제는 DP를 사용하는 문제인데 다음과 같은 점화식을 가진다. dp[n]= max(dp[i] + cost[n-i], cost[n]) (1

DP를 사용하는 전형적인 문제이다. 1X2, 2X2, 2X1 세가지 블럭이 있으므로 다음과 같은 점화식을 구할 수 있다. dp[N]= (dp[N-1]에서 세로블럭 1개 더해서 만들기) + (dp[N-2]에서 가로블록 2개 더해서 만들기) + (dp[N-2]에서 정사각형 블록 1개 더해서 만들기) 위와 같은 점화식으로 쉽게 dp를 구할 수 있고, 조건에서 10007로 나눈 수를 구하라 했으므로 연산 결과마다 10007을 나누어 주었다. 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 package boj.base; import java.io.BufferedReader; import java.io.InputStream..

DP로 푸는 문제이다.n 처음에 문제를 보았을 때, 재귀를 이용하여 접근하였다. 하지만 재귀를 시간초과가 발생하였다. 그래서 DP를 이용하여 풀어보았다. bottom-up 방식을 이용하여 1부터 N까지 갈수있도록 하였다. 이 과정은 시간복잡도가 n이므로 금방 구할수 있었다. 즉, dp[n]= min(dp[n/3], dp[n/2], dp[n-1]) +1 이라는 점화식을 이용하여 풀었다. 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 package boj.base; import java.io.BufferedReader; import java.io.InputStreamR..