알고리즘 문제408 [leetcode]1047. Remove All Adjacent Duplicates In String 문제 : https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/ 문자열을 탐색하면서 정답 문자열을 만든다. 만약 탐색중인 문자가 정답 문자열의 마지막 문자와 같다면 문자를 추가하지 않고 정답 문자열의 마지막 문자를 삭제한다. 정답문자열이 비어있거나 탐색중인 문자와 정답 문자열의 마지막 문자와 다르다면 정답문자열에 탐색중인 문자를 추가한다. 시간복잡도는 O(N). N = |입력 문자열| 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1047.%20Remove%20All%20Adjacent%20Duplicates%20In%20String.cpp 2021. 6. 28. [leetcode] 684. Redundant Connection 문제 : https://leetcode.com/problems/redundant-connection/ n개의 노드와 n개의 간선으로 이루어진 무방향 그래프가 주어질 때, n개의 노드로 이루어진 트리가 될 수 있도록 제거해야 하는 간선을 구하여라. 조건에 그래프들은 연결되어 있고 노드가 n개인데 간선도 n개라고 하니, 트리의 특징 중 하나인 간선의 개수는 정점 개수 - 1 이다.를 생각하면 정답이 되는 간선은 1개가 나올 수 있고. 이 간선은 사이클을 만듬을 알아낼 수 있다. 크루스칼 알고리즘 구현에서 사이클이 생성됨을 알아내기 위해 유니온 파인드를 사용했었다. 이를 응용하여, 입력으로 주어지는 간선들을 Union-Find 의 Union 연산으로 하나의 집합으로 합치면서 이미 같은 집합인데 Union 연산.. 2021. 6. 26. [Leetcode][576] Out of Boundary Paths 문제 : https://leetcode.com/problems/out-of-boundary-paths/ DP. 메모이제이션이 필요하다. 남은 maxCount 횟수, 현재 좌표가 같다면 정답 횟수는 같아진다. 즉, dp[maxCount][row][column] = 경계를 벗어나는 경로 횟수 를 저장한다. dp[maxCount][row][column] = dp[maxCount-1][row][column+1] + dp[maxCount-1][row][column-1] + dp[maxCount-1][row+1][column] + dp[maxCount-1][row-1][column] 이동은 상하좌우로 할 수 있기 때문에 점화식은 다음과 같다. 더한 값에 1000000007을 나눈 나머지값을 저장해줘야한다. 만일 r.. 2021. 6. 25. [leetcode][118] Pascal's Triangle 문제 : https://leetcode.com/problems/pascals-triangle/ numRows가 주어질 때, numRows 크기의 파스칼의 삼각형을 구하여라. 파스칼의 삼각형의 원소는 바로 위에 있는 두 원소의 합이다. answer[i][j] = answer[i-1][j-1] + answer[i-1][j] 위 연산을 모든 원소에 적용하면 답을 수할 수 있다. 시간복잡도는 1+2+ ... + numRows = 대략 O(numRows^2 /2). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/118.%20Pascal's%20Triangle.cpp 2021. 6. 22. [leetcode][778] Swim in Rising Water] 문제 : https://leetcode.com/problems/swim-in-rising-water/ N x N 배열 grid가 입력으로 주어진다. grid[i][j] = (i,j) 위치의 높이. 시간 t에서 모든 grid 위치의 수심은 t이고, 인접한 위치의 고도가 t 이하인 경우에만 이동가능하다. 이동하는데 드는 시간은 고려하지 않는다. grid의 (0,0)에서 (N-1, N-1)로 이동할 때 도달할 수 있는 최소시간은 얼마인가 이동하는데 드는 시간은 고려하지 않으므로 결국 (0, 0) -> (N-1, N-1)로 이동하는 경로의 고도값들의 최대값의 최소값을 구하는 문제이다. 다익스트라로 풀었다. 간선의 가중치는 u -> v로 이동한다고 했을 때, v 위치의 높이가 된다. 즉, 높이가 낮은 인접한 위치.. 2021. 6. 21. [leetcode][795] Number of Subarrays with Bounded Maximum 문제 : https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/ 양수 배열 nums, 두 개의 양수 left, right 가 입력으로 주어진다. nums 배열의 하위배열(연속적인 부분배열. 비어있지 않음)의 최대 원소가 left 이상, right 이하인 하위배열들의 수를 구해라. 재미있는 투포인터문제~ nums를 처음부터 탐색하면서 정답이 될 수 있는 범위를 l, r 변수에 저장한다. (l = 왼쪽, r = 오른쪽 인덱스) l 변수는 nums[i]가 부분배열에 포함될 때 정답이 절대 불가능할 때 갱신한다. 최대값만 left, right를 비교하기 때문에 정답이 절대 불가능한 경우는 nums[i]가 right보다 큰 경우이다. r 변.. 2021. 6. 19. 이전 1 ··· 20 21 22 23 24 25 26 ··· 68 다음
