프로그래민👨‍💻

그리디 알고리즘이다. 정확히 말하면 Interval Scheduling Greedy Algorithm 이다. 시간이 정해진 어떤일을 함에 있어 가장 문제에 따라 가장 최적의 효율을 낼수 있는 방법을 찾는 알고리즘이다. 이 알고리즘은 여러가지로 접근할 수 있다. 1. 일의 소요시간이 가장 짧은 순서로 접근 2. 일의 시작시간이 빠른 순서로 접근 3. 일의 끝시간이 빠른 순서로 접근 이 문제는 3번의 방법인 일의 끝 시간 기준으로 접근하여 보았다. 모든 노드들을 일의 끝시간으로 정렬을 한다음, 맨 처음 것을 선택 그 후 부터 다음에 나오는 노드의 시작점이 현재 노드의 끝점보다 같거나 크다면 선택후 현재 노드를 갱신해주는 방식으로 풀었다. 이와 비슷한 문제로 모든 회의를 수용하기 위해 회의실이 최대 몇개가 필..

파싱을 요하는 시뮬레이션 문제이다. 이 문제에서 요점은 입력으로 들어오는 시간을 밀리초(ms) 로 변환시키는 것과 트래픽의 변화가 생기는 것은 시작점과 끝점이라는 것을 파악하는 것이다. 모든 밀리초 시간을 확인할수 없으므로 시작점과 끝점의 1초를 확인하는 방식으로 푼다면 O(n*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 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 73 74 75 76 ..

간단한 시뮬레이션 문제였다. 이 문제의 경우 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