프로그래민👨‍💻

누적합을 사용한 문제였다. 문제를 맨처음 봤을때 단순히 브루트포스로 접근하여 모든 라인에서 모든 장애물을 카운트하는 방식을 사용하려고 했으나, 최대 장애물의 수가 200,000개, 최대 라인의 수가 500,000이 나오게 됨으로 시간초과를 피할수 없을것같다는 생각이 들었다. 그래서 생각해본게 높이당 장애물의 수를 저장하고, 그것을 이용하여 높이당 넘어야할 장애물의 누적수를 구한다음 모든 높이(라인)에서 몇개의 장애물을 넘어야하는지 계산하였다. 다만 주의할점은 장애물이 위방향, 아래방향 두가지가 나오게 됨으로 나누어서 계산을하고 인덱스를 적절히 조정하여 높이(라인)에서 몇개의 장애물을 넘는지 구하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2..

이분탐색을 활용하는 문제였다. 맨처음 문제를 접하였을 때 부술수 있는 바위를 고르는 방법을 우선적으로 생각했는데, 바위의 갯수가 50,000이기 때문에 50000C2 라는 조합을 한다면 시간초과가 날것이라고 생각했다. 그래서 다른 바위말고 distance를 기준으로 문제를 접근해보았고 distance가 1,000,000,000으로 주어졌기 때문에 시간복잡도가 효율적인 이분탐색을 사용해보았다. low값을 바위사이의 최소 거리인 1, 그리고 high값을 바위 사이의 최대거리인 distance로 두고, 이분탐색을 돌면서 mid 값보다 크거나 같도록 바위를 배열하게 된다면 몇개의 바위를 부숴야 하는지 확인하고, 바위를 부술 수 있는 최대값 n 과 비교하여 바위 사이의 최대 간격을 찾는 방법으로 문제를 해결해보았..

lowerBound와 upperBound를 활용하여 풀 수있는 문제였다. 총의 사정거리 L에대해 사대의 위치 와 동물의 위치 x,y에 대해 다음과 같은 공식이 문제에 주어져있다. | 사대 - x | + y

다익스트라를 활용하는 최단거리 문제이다. 문제를 맨처음 보았을 때 단순하게 백트래킹으로 모든 경로를 확인해보았다. 하지만 주어질 수 있는 동굴의 크기의 최대값이 125이기 때문에 시간초과가 발생하게 된다. 따라서 다익스트라를 활용해보았다. 다익스트라는 기본적으로 다음과 같은 원리로 동작한다. 출발 노드를 설정 최단 거리 테이블을 최대값으로 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 위 과정에서 3번 4번을 반복 그래프와 다르게 2차원 배열에서는 4방향을 갈수있다고 가정하고, 우선순위 큐를 이용하여 구현해보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..

이 문제는 BFS를 활용한 문제였다. 문제를 맨처음 접했을 때 당연하게 2차원 visit배열을 이용하여 벽을 만났을 때 현재 위치에서 남은 벽 부수는 횟수를 이용하여 단순하게 벽을 부수는 방법으로 접근을 하였다. 이러한 경우 다음과 같은 문제점이 발생하게 된다. 0 1 1 1 0 0 1 0 이러한 맵이 부술수 있는 벽이 1개 존재한다고 가정하자. 이 상황에서 최단 거리는 당연히 직관적으로 (1,1) -> (2,1) -> (2,2) -> (2,3 부수기) -> (2,4)를 확인 할 수가 있다. 다만 맨처음에 접근했던 방법을 이용하여 BFS를 돌았을 때 단지 벽부는 횟수만 체크하게 된다면 (1,1) -> (1,2 부수기) -> (2,2) 에서 끝나는 상황을 충분히 마주치게 된다. 그러므로 벽 부수는 것에 대..

스택을 사용하는 그리디 문제였다. 이 문제는 숫자의 앞에서부터 스택에 집어넣으며 순서를 지키며 가장 큰 수를 만드는 문제이다. 즉 다음과 같은 로직을 가진다. 현재 스택에 집어넣어야할 숫자에 대해서 만일 지울 수 있는 횟수가 남아있고, 스택의 top 값이 현재 숫자보다 작다면 스택의 top을 제거하는 것을 반복하고 현재 숫자를 스택에 push해주는 원리이다. 그후 최종적으로 N-K만큼의 길이를 스택의 bottom에서부터 보여주는 방식으로 해결할 수 있다. 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 ..

다이나믹 프로그래밍을 활용한 문제였다. 이 문제는 성냥개비를 활용하여 가장 큰 수와 가장 작은 수를 만들는 문제였다. 모든 조합의 경우를 확인하는 방법도 있지만 보다 효율적으로 확인할 수 있는 DP가 있기에 DP를 사용하여 큰 수, 작은 수를 각 각 구하였다. 우선 간단한 큰수의 경우 계속 자릿수를 늘려가는 방법 생각해보았다. 우선 가장 작은 성냥개비가 드는 수는 1로써 성냥 두개를 사용하게 되는데 이것을 이용하여 모든짝수를 구할 수 있었다. 홀수의 경우 7이 성냥 세개를 사용하는데 이것을 이용하여 하나의 홀수 + 나머지는 짝수를 사용하는 방식을 사용할 수 있었다. 따라서 다음과 같은 점화식을 사용할 수 있었다. dp[2] = 1, dp[3] = 7, dp[i] = concat(dp[i-2], 1) 또한..

스택을 이용하는 문제이다. 이 문제는 스택을 활용하여 연산자들을 스택에 저장하면서 수식을 후위표기식으로 출력하는 문제였다. 스택을 보다 자유롭게 활용할 수 있는 deque를 사용하였다. 이 문제에서는 연산자들마다 우선순위가 있기에 그것을 고려하여 스택을 탐색하는 과정이 필요했다. 입력을 하나씩 확인하면서 다음과 같은 규칙을 적용하였다. 1. A~Z의 경우 바로 출력 2. (의 경우 바로 스택에 넣기 3. )의 경우 스택에서 (를 만나기 전까지 출력 4. +,-의 경우 우선순위가 *,/보다 낮기때문에 스택이 비거나 (를 만나기전까지 스택에서 빼서 출력 5. *,/의 경우 우선순위가 +,-보다 높기때문에 스택이 비거나 +,-,(를 만나기전까지 스택에서 빼서 출력 1 2 3 4 5 6 7 8 9 10 11 1..

LIS의 대표적인 예제이다. 이 문제같은 경우 11053번(링크)와 다르게 n의 범위가 1000000까지라 lower_bound를 사용하는 LIS문제 유형이다. Java의 경우 lower_bound를 따로 제공해주지 않기에 직접 구현하여 사용하였다. lower_bound를 사용하는 LIS경우 LIS배열을 생성하는데 이때 LIS[i]의 값은 i만큼의 길이의 최장 증가 수열에서 가지게 되는 가장 작은 마지막 원소값을 의미하게 된다. 즉 위의 예제 입력을 예로 들면 LIS[2]는 최장 증가 수열 길이가 2일때 가지는 경우의 수 가 10 20, 10 30, 10 50, 20 30, 20 50 등이 있는데 이때 가장 작은 마지막 원소값은 10 20에서의 20이 되게 된다. 따라서 LIS[2] = 20을 가지게 된..

LIS의 대표적인 예제 문제이다. LIS를 구현함에 있어 크게 n^2의 시간복잡도를 가지는 dp, nlogn의 시간복잡도를 가지는 lower_bound가 있다. 이 문제 같은 경우는 n의 최대 크기가 1000이기에 dp를 이용하여 풀어보았다. dp를 이용하여 푸는 경우 LIS배열을 하나 생성한다. 이 LIS 배열의 경우 LIS[i]가 나타내는 것은 arr[i]를 마지막으로 가지는 가장 긴 수열의 길이를 의미하게 된다. 즉, 위의 예제입력을 예로 들면 LIS[5]의 경우 arr[5]의 값 즉 50을 가장 마지막으로 가지는 최장 증가 수열의 길이를 의미하게 된다. 이것을 확인하는 원리는 기준의 되는 인덱스 i에 대해 비교 인덱스 j를 두고 1. j