프로그래민👨‍💻

이분 탐색을 사용하는 문제이다. 최소값을 찾는것에 이분탐색을 사용하는것이 좋을것이라 생각했는데, 이분탐색의 다음조건을 넘어가는 check함수를 구현함에 있어서 고민을 많이했다. 맨처음엔 단순하게 arr를 M개로 쪼개는 모든 경우의 수를 생각하였는데, N이 최대 100,000이여서 최악의 경우 이분탐색을 사용하더라도 check함수로 인한 시간초과가 발생할 수 있다고 생각하였다. 그래서 단순하게 현재검증해야하는 값(mid)으로 arr를 나눈다면 몇조각이 나오는지 확인하였고, 그것을 M과 비교하여 M이하면 참, 초과면 거짓을 반환하는 check함수를 만들어 사용하였다. 이 check함수에선 또 하나 체크해야 할 것이 있는데 만일 mid값이 arr의 원소보다 작다면 무조건 거짓을 반환하는 조건을 추가하는 것이다..

생각하기 어려운 수학문제였다. 단순히 생각해서 N개의 소세지를 전체 이어붙이고 M개로 만들기 위해선 (M-1)번의 칼질이 필요하다는 것을 알 수 있다. 하지만 N이 M으로 나눠지거나 M이 N으로 나눠지는 경우 생각하지 않아도 되는 칼질의 경우가 생기는 것을 알 수 있다. 이것을 위해 최대공약수로 나누어 답을 구한다면 (M/GCD - 1) 번의 칼질이 나오는데 이것을 다시 GCD로 곱해야지 최종 답을 알 수 있다. 즉, 칼질횟수 = GCD(M/GCD - 1) = M - GCD 임을 알수가 있다. 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 package study4; import java.io.BufferedReade..

재귀를 이용한 분할정복 문제였다. 처음에 문제를 보고 이해하는데 오래걸렸다. 이문제는 전체 그림을 4등분하여 같은 숫자를 가진다면 하나의 숫자로 묶는 문제였다. 찾아야하는 범위의 숫자가 계속 반(나누기2) 되는 성질을 보니 재귀를 이용하여 풀수 있을 것 같았다. 그래서 함수 하나를 만들었고, 조건을 만족하지 못한다면 4방향에 대해 범위를 반으로 줄여서 계속 호출해주었다. 이 문제를 풀면서 100%에서 계속 틀렸었는데, 이유는 N=1, 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 3..

단순 시뮬레이션 문제이다. 문제에 주어진 조건처럼 단순히 모든 경우수를 체크하는 방식으로 풀어보았다. 다음과 같은 로직으로 해결해보았다. 1. 모든 도형은 3개의 연속블록을 가지므로 가로, 세로로 나누어 3개가 연속이 되는 블럭을 찾음 2. 그 블럭에서 튀어나온 블록 하나를 찾음 3. 튀어나온 블록과 동일선상에 있는 검정블록 2개에 대해 위에서 떨어트릴 수 있는지 체크 4. 가능하다면 답+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 39 40 41 42 43 44 45 46 47 48 ..

이진트리의 순회 문제이다. 이 문제는 이진트리의 노드들이 주어지고 전위순회(루트->좌->우), 후위순회(좌->우->루트)를 구하는 문제였다. 보통의 문제들과 다른점은 간선을 그리는 것이 주요한 문제였다. 따라서 두가지 과정을 거쳐 간선을 그려보았다. 일단 첫번째로 모든 노드들을 y로 내림차순, y가 같다며 x로 오름차순이 되도록 정렬을 하였다. 그 후에 Node라는 클래스를 만들어 left, right를 Node의 형으로 멤버변수(포인터의 개념)를 주고, 정렬된 노드들을 x값을 비교하여 left,right에 할당하며 연결해주었다. 이것을 완료한 후에는 재귀를 이용하여 간단하게 전위순회, 후위순회를 하여 풀었다. 문제의 우선순위, 즉 이문제에서는 간선을 그리는것이 최우선목표인데 그것을 해결하는 것이 중요한..

DFS를 사용하는 문제지만 시간초과를 잘생각해야하는 문제이다. 일반적인 DFS를 사용한다면 시간초과가 쉽게 날수 있는 문제이다. 따라서 시간초과를 줄이기 위해 여러번 같은 노드를 방문하는 것을 주의 해야한다. 예를 들면 예제1번의 경우 1->3->3 이 나오고, 2->1->3->3 이 나온다. 2에서 시작한 경우 불필요하게 중복 방문을 하게 된다. 따라서 이런것을 해결해주기 위해 visit배열과 별개로 finished 배열을 만들어 노드에서 사이클을 이미 뽑아낸적이 있는 지를 체크해주었다. 또한, 탐색의 끝에 있는 노드는 항상 사이클을 형성 해주는 노드중에 하나 이므로 그 노드를 시작으로 다시 사이클을 체크해주는 방식을 사용하였다. 상당히 어려운 문제였다. 다시 풀어볼 필요가 있는 것 같다. 1 2 3 ..

문자열을 파싱하는 문제이다. 주어진 조건대로 단순히 문자열을 파싱해주는 문제이다. 일단 봐야하는 문자열 길이를 1부터 전체길이/2 를 해주었고, keep이라는 변수를 통해 현재까지 같은 누적을 계산하여 문자열의 길이를 구해주었다. 단순 구현 시뮬레이션 문제이므로 조건을 꼼꼼히 읽는 것이 중요한 문제였다. 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 package programmers; public class Solution_2..

그래프의 BFS문제이다. List의 배열을 이용한 간단한 그래프 BFS 문제였다. 촌수를 구하기 위해 visit배열을 -1로 초기화 시켰고 start부터 시작하여 end가 만날때까지 실행을 시켰다. 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 package study4; import java.io.BufferedReader; import java.io.InputStreamReader; impor..

그리디 알고리즘이다. 정확히 말하면 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 ..