# 50. Pow(x, n)
x^n 을 구하는 문제
단순히 x 를 n 번 곱해서 문제를 해결할 수도 있지만, 그렇게 해결할 경우 n 이 INT_MIN ~ INT_MAX 범위를 갖기 때문에 시간초과가 날 것으로 생각된다.
때문에 이 방식이 아니라 조금 더 현명하게 문제를 해결하고자 한 방법이 이진법을 생각한 것이었다. 이진법의 경우, 각 자릿수가 2의 승수를 의미하는데 (네 자리라면 8, 4, 2, 1 이런식으로) 각 자리별로 bit 가 1이면 해당 값을 더하고, 0이면 패스하는 식으로 이루어진다.
이 문제는 x 의 n 승을 구하는 문제이므로 더하는 게 아니라 해당 값을 곱하는 방식으로 문제를 풀었다.
추가로, 처음에는 n 이 음수일 경우 값을 나눠주도록 해서 문제를 해결하려 했는데 일반적으로 곱셈보다 나눗셈이 더 시간이 많이 걸린다는 사실을 알지 못했다. 그래서 시간초과가 발생하는 걸 보고, 우선 값을 다 곱해준 뒤 나누기를 해 주는 방식으로 문제를 해결했다.
double myPow(double x, int n) {
double ans = 1;
bool neg = n < 0;
while (n){
if (n & 1)
ans *= x;
x *= x;
n /= 2;
}
if (neg){
ans = 1 / ans;
}
return ans;
}# 53. Maximum Subarray
배열이 주어졌을 때, 해당 배열의 연속된 SubArray 중 가장 큰 합을 갖는 경우의 합을 구하는 문제
DP 의 대표적인 유형 문제로, 배열을 순차 탐색하면서 (이전 인덱스까지의 최대 합 + 현재 인덱스의 값) 과 (현재 인덱스의 값) 을 비교해 더 큰 값을 저장해 나가는 방식으로 문제를 해결했다.
int maxSubArray(vector<int>& nums) {
if (nums.size() == 1)
return nums[0];
int max_sum = nums[0];
int cur_sum = nums[0];
for (int i = 1; i<nums.size(); i++){
cur_sum = max(cur_sum + nums[i], nums[i]);
max_sum = max(max_sum, cur_sum);
}
return max_sum;
}# 54. Spiral Matrix
M * N 행렬이 주어졌을 때, 해당 행렬을 나선형으로 탐색한 결과를 구하는 문제
이 문제는, BFS 문제를 풀 때 주로 사용한 방식으로 문제를 해결했다.
{오른쪽, 아래, 왼쪽, 위} 방향으로 이동할 때의 인덱스 변화량을 미리 저장해 두고 방향만 바꾸는 방식으로 순서대로 탐색을 했다.
이미 탐색한 위치인 경우, 값을 INT_MIN 값으로 바꿔주어서 다시 탐색하지 않도록 하고 행렬의 범위를 벗어나는 경우 방향을 바꾸도록 했다.
int dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int dir = 0, cy, cx;
int n = matrix.size(), m = matrix[0].size();
int size = n * m;
vector<int> ans;
cy = cx = dir = 0;
while (size--) {
ans.push_back(matrix[cy][cx]);
matrix[cy][cx] = INT_MIN;
int ny = cy + dy[dir], nx = cx + dx[dir];
if (ny < 0 || ny >= n || nx < 0 || nx >= m) {
dir = (dir + 1) % 4;
ny = cy + dy[dir], nx = cx + dx[dir];
}
else if (matrix[ny][nx] == INT_MIN) {
dir = (dir + 1) % 4;
ny = cy + dy[dir], nx = cx + dx[dir];
}
cy = ny, cx = nx;
}
return ans;
}'Algorithm > LeetCode' 카테고리의 다른 글
| [LeetCode # 58, 59, 61] 문제 풀이 (0) | 2021.04.28 |
|---|---|
| [LeetCode # 55 ~ 57] 문제 풀이 (0) | 2021.04.07 |
| [LeetCode # 47 ~ 49] 문제 풀이 (0) | 2021.04.02 |
| [LeetCode # 43, 45, 46] 문제 풀이 (0) | 2021.04.01 |
| [LeetCode # 38 ~ 40] 문제 풀이 (0) | 2021.03.30 |