본문 바로가기

알고리즘 문제/Leetcode283

[leetcode][275] H-Index II 문제 : https://leetcode.com/problems/h-index-ii/오름차순으로 정렬된 양의 정수 배열이 주어진다고 하자. (let, 배열 크기 = N)이 배열은 논문들이고, 각 배열 값은 i번째 논문이 몇 개의 논문을 인용했는지를 나타낸다. 즉, arr[2] = 3이라면 2번째 논문은 3개의 논문을 인용하여 작성되었음을 의미한다.N개의 논문중 h개의 논문이 h개 이상의 논문을 인용하고 N-h개는 h개 이하를 인용하는 경우 h-인덱스라고 한다.배열의 가능한 h-인덱스 값 중 최대값을 구해라.이분 탐색으로 풀어보자. 어쨌든 h의 범위는 논문의 개수이다.l, r 은 배열의 시작인덱스, 종료인덱스로 잡자.m = (l+r)/2이다.h = N - m라고 하고 h가 정답이 가능한지 판단한다.문제 초반.. 2020. 6. 18.
[leetcode][1029] Two City Scheduling 문제 : https://leetcode.com/problems/two-city-scheduling/ 2N명을 도시 A, B에 각각 N명씩 이동시키려고 한다. 각각 A, B로 이동시키는 비용이 주어질 때 이동시키는 비용의 최소값을 구해라. A아니면 B로 이동시킨다. -> 둘 중 하나는 선택되어야 한다. 하나는 선택되어야 하므로 한 명의 A, B 이동 비용을 비교해야 되고 두 방법 중 이동 비용이 작은쪽으로 이동시켜야 이득이다. 각자 A로 이동시키는 비용 - B로 이동시키는 비용을 구해서 오름차순으로 정렬한다. (B가 A보다 크거나, A비용이 더 크지만 B와의 비용 차이가 별로 나지 않을 수록 앞에 정렬된다.) 앞에서부터 N명은 A로, 그 뒤 N명은 B로 이동시킨다. 시간복잡도는 O(NlogN). 소스코드 .. 2020. 6. 4.
[leetcode][72] Edit Distance 문제 : https://leetcode.com/problems/edit-distance/ word1에서 word2를 만들고자 한다. 최소 편집횟수를 구하라. 편집 방법은 총 3가지가 있다. 1) 문자 추가. 2) 문자 삭제. 3) 문자 대체(변경) 대표적 DP 문제 중 하나. dp[i][j] = word1[0..i]를 word2[0..j]로 만들 때 최소 편집횟수. word1[i], word2[j]가 같다면 dp[i][j] = dp[i-1][j-1]. word1[i], word2[j]가 다른경우 i) 문자 추가 : dp[i][j-1] + 1 ii) 문자 삭제 : dp[i-1][j] + 1 iii) 문자 대체 : dp[i-1][j-1] + 1 위 3가지 방법 중 최소값이 dp[i][j]가 된다. 이를 열우.. 2020. 6. 2.
[leetcode][1277] Count Square Submatrices with All Ones 문제 : https://leetcode.com/problems/count-square-submatrices-with-all-ones/ 1과 0으로 이루어진 N x M 배열이 주어지면 1로 이루어진 정사각형의 개수를 구하라. 행, 열 subsum을 구한 뒤 이를 이용하여 구했다. 입력배열이 위와 같으면 행, 열 부분합 배열은 각각 위와같이 만들어진다. (2,1) 한 칸이 정사각형인지 판단하는 방법은 행 부분합에서 (2, 1) - (1,1) 값과 열 부분합에서 (2,1) - (2,0) 값이 둘 다 1이어야 한다. 즉, (2,1) 값이 1인지 확인하기만 하면 된다. 그 다음 (2,1)을 정사각형의 왼쪽 모서리로 두고 사이즈가 2인 정사각형이 가능한지 판단해보자. 이전 단계에서 (2, 1)은 모두 1인 것을 판.. 2020. 5. 23.
[leetcode][367] Valid Perfect Square 문제 : https://leetcode.com/problems/valid-perfect-square/ 양수 num이 주어졌을 때, num이 완벽한 제곱수면 true, 아닌경우 false를 반환한다. sqrt 함수를 사용하지 않고 풀어라. 변수 하나를 1로 초기화시킨 후 제곱 수가 num보다 크거나 커질때까지 1씩 증가한다. 제곱수가 num과 같은 경우 true를 반환하는 방식으로도 풀 수 있다. 그리고 이분탐색으로도 풀 수 있다. left = 1, right = num으로 두고 중간 값(m)의 제곱이 num이라면 true를 반환, 작다면 left = m+1, 크다면 right = m-1로 세팅하고 left가 right보다 작거나 큰 경우 이를 반복한다. left가 right보다 커질 때까지 true를 반.. 2020. 5. 9.
[leetcode][45] Jump Game II 문제 : https://leetcode.com/problems/jump-game-ii/ 음수가 아닌 정수 배열이 주어진다. 배열 값은 그 인덱스에서 1번의 점프로 최대 몇 개의 인덱스를 이동할 수 있는지를 의미한다. 즉, arr[3] = 2인 경우 3인덱스에서 4, 5로 이동할 수 있다. (4, 5로 이동할 때 1번 점프로 이동가능을 의미) 0인덱스에서 시작할 때, 최소 몇 번의 점프로 마지막 인덱스까지 도달할 수 있는가. (마지막 인덱스까지 도달할 수 없는 경우는 없다고 한다.) 그리디로 해결가능하다. 0부터 탐색하면서 탐색 중인 인덱스까지 도달하기 위해 필요한 최소 점프횟수(ans), 최대로 이동할 수 있는 인덱스(maxInd), 그리고 임시 최대이동가능 인덱스(tmp)를 구한다. tmp는 임시로 저.. 2020. 4. 26.

티스토리툴바