Ho__sing.log

[BOJ] 21609. 상어 중학교

Fri, 17 Jan 2025 10:52:45 GMT

Intuition

문제의 조건만 잘 생각하면서 푼다면 큰 어려움은 없다. 다만 구현량이 지금까지 경험했던 문제들에 비해서 조금 많다.

Approach 및 개선점

BFS vs DFS

블록 그룹들을 찾는 탐색 방식으로 BFS와 DFS를 떠올려 볼 수 있다. 둘 중 어느 방식을 쓰든 이 문제에서는 큰 차이가 없다. 나는 DFS를 썼다.

다만, 삼성 코딩테스트에서는 stack 메모리가 1MB로 제한되기 때문에 앞으로는 재귀함수 사용은 지양하는 것이 좋을 듯 하다.

void findGroup(int r, int c, int color) {
  for (int i = 0; i < 4; i++) {
    int nr = r + dr[i];
    int nc = c + dc[i];

    if (nr >= 0 && nr < n && nc >= 0 && nc < n && game[nr][nc] != -1 &&
        visited[nr][nc] == 0 && game[nr][nc] <= m) {
      if (game[nr][nc] == 0 || game[nr][nc] == color) {
        ...
        visited[nr][nc] = 1;
        ...
        findGroup(nr, nc, color);
      }
    }
  }
}

이때, 무지개 블럭은 다른 그룹에서는 재방문이 가능하기 때문에 초기화를 시켜줬다.

int findMAX() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!visited[i][j] && game[i][j] != 0 && game[i][j] != -1 &&
          game[i][j] <= m) {
        visited[i][j] = 1;
        ...
        findGroup(i, j, game[i][j]);
        ...
        zero_cnt = 0;
        // 0은 재방문 가능
        for (int k = 0; k < zero_d_cnt; k++) visited[zero_r[k]][zero_c[k]] = 0;
      }
    }
  }
  return block_cnt_MAX * block_cnt_MAX;
}

좌표 저장

문제를 풀다보면 무지개블럭, 최대 블록그룹 등 블럭들의 좌표를 저장해야하는 상황이 생긴다. N의 최댓값이 20이기 때문에 400짜리 크기의 배열을 2개 만들어서 row와 column을 각각 저장했다.

int group_MAX_r[400];
int group_MAX_c[400];
int number_of_group_MAX;

int group_MAX_r_tmp[400];
int group_MAX_c_tmp[400];
int group_MAX_tmp_idx;
...
        // 크기가 가장 큰 블록그룹의 좌표와 배열의 크기를 저장
        if ((block_cnt_MAX < block_cnt) ||
            (block_cnt_MAX == block_cnt && zero_cnt_MAX <= zero_cnt)) {
          block_cnt_MAX = block_cnt;
          zero_cnt_MAX = zero_cnt;
          number_of_group_MAX = group_MAX_tmp_idx;
          for (int k = 0; k < group_MAX_tmp_idx; k++) {
            group_MAX_r[k] = group_MAX_r_tmp[k];
            group_MAX_c[k] = group_MAX_c_tmp[k];
          }
        }

좀 더 편한 방법이 없을까 찾아보니 C++의 vector와 pair를 사용하는 방법이 있었다.

vector> var;

C++을 거의 안쓰다보니 STL을 잊어먹어서 생긴 문제다.

중력

열 하나를 위에서 아래로 순회하여 완전하게 마무리를 하고 다음 열로 넘어가는 방식으로 진행했다. stack에 무지개블럭과 일반블럭을 push했다가, -1이나 바닥에 도달하면 전부다 pop하며 위로 하나씩 채운다. -1이나 천장에 도달하기 전까지 위로 올라간다. stack이 빈 경우에는 m+1값으로 표시한다.

void gravity() {
  stack blocks;

  for (int c = 0; c < n; c++) {
    for (int r = 0; r < n; r++) {
      if (game[r][c] >= 0 && game[r][c] <= m) blocks.push(game[r][c]);

      if (r + 1 == n || game[r + 1][c] == -1) {
        // 현재 칸부터 채워야함
        for (int i = r; i >= 0 && game[i][c] != -1; i--) {
          if (!blocks.empty()) {
            game[i][c] = blocks.top();
            blocks.pop();
          } else
            game[i][c] = m + 1;
        }
      }
    }
  }
}

마찬가지로 stack memory가 1MB로 한정되기 때문에, 앞으로는 stack을 전역변수로 할당하거나 stack을 사용하지 않고 처리하는 것이 좋겠다.

회전

회전은 좌표를 비교해보면 행과 열간의 규칙을 발견할 수 있다.

void rotate() {
  int game_tmp[20][20];
  for (int i = 0; i < 20; i++) {
    for (int j = 0; j < 20; j++) {
      game_tmp[i][j] = game[i][j];
    }
  }

  for (int r = 0; r < n; r++) {
    for (int c = 0; c < n; c++) {
      game[r][c] = game_tmp[c][n - 1 - r];
    }
  }
}

극한까지 메모리가 제한된다면 in-place 방식으로도 처리를 하는 방법이 있다.

Solution

#include 

#include 

using namespace std;

int game[20][20];
int visited[20][20];

int zero_d_cnt;
int zero_r[400];
int zero_c[400];

int group_MAX_r[400];
int group_MAX_c[400];
int number_of_group_MAX;

int group_MAX_r_tmp[400];
int group_MAX_c_tmp[400];
int group_MAX_tmp_idx;

int n, m;
int score, block_cnt_MAX, zero_cnt, zero_cnt_MAX;
int block_cnt = 1;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

void findGroup(int r, int c, int color);
int findMAX();
void gravity();
void rotate();

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      scanf("%d", &game[i][j]);
      if (game[i][j] == 0) {
        zero_r[zero_d_cnt] = i;
        zero_c[zero_d_cnt++] = j;
      }
    }
  }

  int score_tmp;
  while ((score_tmp = findMAX()) > 1) {
    score += score_tmp;

    // 저장된 좌표 통해서 최대블록그룹 지우기
    for (int i = 0; i < number_of_group_MAX; i++)
      game[group_MAX_r[i]][group_MAX_c[i]] = m + 1;

    gravity();
    rotate();
    gravity();

    // 0개수 및 위치 재확인
    zero_d_cnt = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (game[i][j] == 0) {
          zero_r[zero_d_cnt] = i;
          zero_c[zero_d_cnt++] = j;
        }
      }
    }
    // init
    block_cnt_MAX = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        visited[i][j] = 0;
      }
    }
  }

  printf("%d\n", score);
  return 0;
}

void findGroup(int r, int c, int color) {
  for (int i = 0; i < 4; i++) {
    int nr = r + dr[i];
    int nc = c + dc[i];

    if (nr >= 0 && nr < n && nc >= 0 && nc < n && game[nr][nc] != -1 &&
        visited[nr][nc] == 0 && game[nr][nc] <= m) {
      if (game[nr][nc] == 0 || game[nr][nc] == color) {
        if (game[nr][nc] == 0) zero_cnt++;
        visited[nr][nc] = 1;
        block_cnt++;
        group_MAX_r_tmp[group_MAX_tmp_idx] = nr;
        group_MAX_c_tmp[group_MAX_tmp_idx++] = nc;
        findGroup(nr, nc, color);
      }
    }
  }
}

int findMAX() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!visited[i][j] && game[i][j] != 0 && game[i][j] != -1 &&
          game[i][j] <= m) {
        visited[i][j] = 1;
        group_MAX_r_tmp[group_MAX_tmp_idx] = i;
        group_MAX_c_tmp[group_MAX_tmp_idx++] = j;
        findGroup(i, j, game[i][j]);

        // 크기가 가장 큰 블록그룹의 좌표와 배열의 크기를 저장
        if ((block_cnt_MAX < block_cnt) ||
            (block_cnt_MAX == block_cnt && zero_cnt_MAX <= zero_cnt)) {
          block_cnt_MAX = block_cnt;
          zero_cnt_MAX = zero_cnt;
          number_of_group_MAX = group_MAX_tmp_idx;
          for (int k = 0; k < group_MAX_tmp_idx; k++) {
            group_MAX_r[k] = group_MAX_r_tmp[k];
            group_MAX_c[k] = group_MAX_c_tmp[k];
          }
        }

        // init
        group_MAX_tmp_idx = 0;
        block_cnt = 1;
        zero_cnt = 0;
        // 0은 재방문 가능
        for (int k = 0; k < zero_d_cnt; k++) visited[zero_r[k]][zero_c[k]] = 0;
      }
    }
  }
  return block_cnt_MAX * block_cnt_MAX;
}

void gravity() {
  stack blocks;

  for (int c = 0; c < n; c++) {
    for (int r = 0; r < n; r++) {
      if (game[r][c] >= 0 && game[r][c] <= m) blocks.push(game[r][c]);

      if (r + 1 == n || game[r + 1][c] == -1) {
        // 현재 칸부터 채워야함
        for (int i = r; i >= 0 && game[i][c] != -1; i--) {
          if (!blocks.empty()) {
            game[i][c] = blocks.top();
            blocks.pop();
          } else
            game[i][c] = m + 1;
        }
      }
    }
  }
}

void rotate() {
  int game_tmp[20][20];
  for (int i = 0; i < 20; i++) {
    for (int j = 0; j < 20; j++) {
      game_tmp[i][j] = game[i][j];
    }
  }

  for (int r = 0; r < n; r++) {
    for (int c = 0; c < n; c++) {
      game[r][c] = game_tmp[c][n - 1 - r];
    }
  }
}

지적 및 질문 환영

[BOJ] 14503. 로봇청소기

Sun, 12 Jan 2025 08:18:50 GMT

Intuition

문제에 기술되어 있는 대로 구현만 하면 된다. 특별한 알고리즘이 필요하지 않았다.

Approach

좌표 처리

네 방향의 좌표들을 편리하게 처리하기 위해 아래 같은 방식을 사용했다.

  int dr[4] = {-1, 0, 1, 0};
  int dc[4] = {0, 1, 0, -1};
  ...
  for (int i = 0; i < 4; i++) {
    if (room[r + dr[i]][c + dc[i]] == 0)
      ...
  }
  if (...) {
    for (int i = 0; i < 4; i++) {
      d = (d + 3) % 4;
      if (room[r + dr[d]][c + dc[d]] == 0) {
        clean(r + dr[d], c + dc[d]);

테두리

이런 배열을 활용하는 문제는 항상 테두리에 주의해야 한다. 배열의 크기를 넘어가지는 않는지, 인덱스가 0이 되지는 않는지 말이다. 그러나 이번 문제 같은 경우는 항상 동서남북으로 벽이 있다. 그리고 이 벽을 코드 구조상 접근하지 않기 때문에, 따로 범위를 체크할 필요는 없다.

Solution

#include 

int room[50][50];
int cnt;
int n, m;
int d;
void clean(int r, int c);

int main(void) {
  scanf("%d %d", &n, &m);
  int r, c;
  scanf("%d %d %d", &r, &c, &d);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      scanf("%d", &room[i][j]);
    }
  }
  clean(r, c);
  printf("%d\n", cnt);
}

void clean(int r, int c) {
  // printf("%d %d\n", r, c);
  if (room[r][c] != 2) {
    room[r][c] = 2;
    cnt++;
  }
  int dr[4] = {-1, 0, 1, 0};
  int dc[4] = {0, 1, 0, -1};
  int status = 0;
  for (int i = 0; i < 4; i++) {
    if (room[r + dr[i]][c + dc[i]] == 0)
      status = 1;
  }
  if (status) {
    for (int i = 0; i < 4; i++) {
      d = (d + 3) % 4;
      if (room[r + dr[d]][c + dc[d]] == 0) {
        clean(r + dr[d], c + dc[d]);
        break;
      }
    }
  } else {
    // printf("%d\n", d);
    int d_back = (d + 2) % 4;
    if (room[r + dr[d_back]][c + dc[d_back]] != 1)
      clean(r + dr[d_back], c + dc[d_back]);
  }
}

Time Complexity

정확하게 계산하지 못해서 rough하게만 생각해봤다. 후진하는 케이스로 인해 이미 방문한 곳을 또 방문하지만, 그래봤자 $2N^2$일 것이라 추정했다. $O(N^2)$

지적 및 질문 환영

[LeetCode] 312. Burst Balloons

Wed, 08 Jan 2025 14:57:17 GMT

Intuition

하나씩 풍선을 터뜨려가면서 그때그때 최선의 선택을 찾는 알고리즘은 불가능해보였다. 작은 케이스의 결과가 큰 케이스의 결과를 알아내는 데에 도움을 줄 수 있어보였다.

Approach

Def.) nums[i:j]에서 최대로 구할 수 있는 코인의 수를 coin[i][j]라 한다. (단, 0<=i,j) Goal) nums[0][numsSize-1]


풍선의 인덱스가 아래와 같을 때,
nums[i:j]의 범위에서 인덱스k의 풍선을 마지막으로 터뜨린다고 가정해보겠다. (단,i<=k<=j)그렇다면 그 이전까지의 과정이 어떻게 되었든 간에 [i:k-1]과 [k+1:j]까지의 풍선은 이미 터졌을 것이고 그 결과 coin[i][k-1]과 coin[k+1][j]를 획득했을 것이다. 이제 남은 풍선 k를 터뜨리게 되면 nums[i-1]*nums[k]*nums[j+1] 만큼의 코인을 획득하게 된다.범위에 있는 k중 어떤 것이 가장 높은 값을 갖는지 비교해보면 된다. 이에 따라 우리는 아래와 같이 점화식을 작성해볼 수 있다.

점화식) coin[i][j]=MAX(coin[i][k-1]+coin[k+1][j]+nums[i-1]*nums[k]*nums[j+1]) (단,i<=k<=j)

이번에도 마찬가지로 인덱스가 우리가 의도한 바와 벗어나지는 않는지 점검해본다. 아무래도 -와 +가 있다보니, i-1과 j+1일 때가 정의되지 않는 범위다. 정의상 coin[a][b]에서 a>b인 케이스는 성립하지 않기 때문에 0으로 처리한다.이제 i와j를 어떤 순서로 순회할지 정해야한다. 쉽게 생각하기 위해, coin[1][2]를 구할 때, 어떤 인덱스들이 필요한지 찾아보겠다. k는 1또는 2가 가능하기 때문에 각각의 경우에 어떤 변수가 필요한지 아래와 같이 정리해볼 수 있다.
따라서 아래 그림과 같은 순서로 i,j를 순회할 때, 우리의 점화식대로 답을 구할 수 있다.
Solution
#define MAX(a,b) ((a)>(b)?(a):(b))
int coin[300][300];

int maxCoins(int* nums, int numsSize) {
    for (int i=numsSize-1;i>=0;i--){
        for (int j=0;jk-1?0:coin[i][k-1];
                int right_coin=k+1>j?0:coin[k+1][j];
                int left_balloon=i-1<0?1:nums[i-1];
                int mid_balloon=nums[k];
                int right_balloon=j+1>=numsSize?1:nums[j+1];
                res=MAX(left_coin+right_coin+left_balloon*mid_balloon*right_balloon,res);
            }
            coin[i][j]=res;
        }
    }
    return coin[0][numsSize-1];
}
Time Complexity
$O(N^3)$
etc.
조재민 교수님께서 말씀하시기로는 이러한 2차원 DP문제의 99.9%는 순회순서가 아래 둘 중에 한 경우라고 한다.
지적 및 질문 환영



[LeetCode] 72. Edit Distance
Tue, 12 Nov 2024 14:25:42 GMT
Intuition
작은 문자열부터 원래문자열까지 하나씩 늘려가며 문제를 해결할 수 있을 것이라 예측했다.
Approach
문제 재해석

Def.) arr[i][j]:=word1[:i]가 word2[:j]로 convert 되는데 필요한 최소 cost

위와 같이 부분 문제를 정의해줄 수 있다.
따라서, 최종목표는 아래와 같이 정의할 수 있다.

Goal) arr[strlen(word1)][strlen(word2)]

base case는 아래 두 경우가 되겠다.

Base case) arr[i][0]=i, arr[0][i]=i

길이 i의 문자열을 빈 문자열로 만들거나, 빈 문자열을 길이 i의 문자열로 만드는데에는 i만큼이 소요된다.
Cost 계산
Case1: word1[i]!=word2[j]
word1[i]와 word2[j]가 같은지 다른지에 따라 cost의 결정 알고리즘이 달라진다.
먼저 다른 경우를 살펴보겠다. 예를 들어, word1[:1]인 h를 word2[:1]인 r로 바꾸는 경우에 대해 생각해보겠다.  
Delete
초록색 부분을 먼저 살펴보자. 기존에 아무것도 없는 문자열에서 'r'로 바꾸는 데에 이미 비용 1 이 필요했다. 그런데 여기서 word1에 'h'가 추가되는 상황이 발생한다. 
arr[1][1]은 arr[0][1]의 값에 word1에 'h'를 추가하는 연산만 더해 계산하면 된다. 비록 arr[1][1]을 h->r로 표현할 수 있지만, 실제로는 arr[0][1]에서 이미 "" -> r 과정이 이루어졌다고 가정할 수 있다. 즉, 이 단계에서 word1은 이미 'r'로 변환된 상태이다. 
이제 arr[1][1]에서 word1에 'h'라는 문자가 추가되었기 때문에 'rh -> r' 상태가 된다. 이 경우 'h'를 삭제해야 하는 비용이 추가적으로 발생하게 된다.
Insert
다음으로 파란색 부분을 보겠다. 기존 'h'를 "none"으로 바꾸는 과정에서 이미 비용 1이 필요했다. word1은 이미 비용1을 소모하여 빈 문자열로 바뀌어있다는 것이다. 이 상태에서 word2[:1]인 'r'로 convert 하기 위해서는 'r'을 추가해주는 비용 1이 추가적으로 필요하다.
Replace
기존이 빈 문자열끼리의 비교였기 때문에 arr[1][1]을 계산하는 과정에서 word1과 word2 모두 각각 'h'와 'r'을 추가적으로 갖게 된다. 즉, 'h->r'인 과정을 계산하는 것이다. 'h'를 'r'로 대체해주는 비용 1이 필요하게 된다. 
다만 기존 arr[0][0]에서 소모된 비용이 없기 때문에 비용 1이 추가적으로 쓰이더라도 결과값이 1이된다.

이처럼 word1[i]와 word2[j]가 다를 때는 대각선, 위, 왼쪽의 값을 가져오는 방식에 따라 각각 replace, delete, insert 연산이 결정된다. 즉, 세 연산에 대한 모든 경우를 비교하여 기존 비용(cost)이 가장 작은 위치에서 +1을 해주면 된다.

arr[i][j]=min(arr[i-1][j-1],arr[i][j-1],arr[i-1][j])+1 if(word1[i]!=word2[j])

Case2: word1[i]==word2[j]
이제 word1[i] == word2[j]인 상황에 대해 알아보겠다. 

초록색과 파란색의 경우, 이전 과정에서 이미 'o'에 대한 비용이 발생했다. (각각 'o'를 insert, delete한 비용이다.) 그러나 빨간색의 경우 'o'에 대한 비용이 아직 발생하지 않았기 때문에, 'o'가 추가되었을 때 같은 문자라는 이점을 이용하여 이전 비용을 그대로 유지할 수 있다.

arr[i][j]=arr[i-1][j-1] if(word1[i]==word2[j])

Solution
#include 

int arr[501][501];

int MIN(int a, int b, int  c){
    int num[3]={a,b,c};
    int ret=a;

    for (int i=0;i<3;i++) if (ret>num[i]) ret=num[i];

    return ret;
}

int minDistance(char* word1, char* word2) {
    int m=strlen(word1);
    int n=strlen(word2);

    for (int i=0;i

Time Complexity
$O(N*M)$
그 외
이 문제는 다른 이름으로 Levenshtein distance라고도 불리며, 단어의 형태적 유사도를 측정하는 알고리즘이다.
만약에 문제가 어떤 연산이 어떤 순서로 쓰였는지 구하라하면 arr[n][m]에서 부터 어떻게 왔는지 그 과정을 거꾸로 타고 올라가면서 스택에 push하고 pop해주면 된다.
지적 및 질문 환영



[LeetCode] 1143. Longest Common Subsequence
Tue, 27 Aug 2024 13:43:45 GMT
Intuiton
longest와 subsequence의 키워드로 DP풀이를 고려해볼 수 있다.
text1과 text2의 문자를 하나씩 비교하며 같을 때마다 Longest Common Subsequence(이하 LCS)의 길이가 +1될 것이라고 예상했다.
Approach
문제 재정의 및 목표 설정
먼저 subproblem을 아래와 같이 정의한다.

$A[i][j] :$ text1$[0:i]$ 와 text2$[0:j]$에서의 LCS

자연스럽게 최종적으로 구해야하는 목표는 아래와 같이 작성할 수 있다.

Goal : $A[$strlen(text1)$-1][$strlen(text2)$-1]$

점화식 구하기
text1 : fbdk, text2 : kdk 인 input을 가정해보겠다.
text1에서 f, text2에서 k를 가져왔을 때 공통되는 문자가 없으므로 lcs는 0이다.
text1에서 fbdk, text2에서 k를 가져왔을 때, 문자 'k' 하나가 공통되므로 lcs는 1이다.

text1에서 fbd, text2에서 kd를 가져왔을 때, 문자 'd' 하나가 공통되므로 lcs는 1이다.

1에서 fbdk, 2에서 kd를 가져왔을 때, subsequence d 또는 k 가 공통되므로 여전히 lcs는 1이다.즉, 위와 같이 두 문자가 일치하지 않는 경우에는 위쪽($A[i-1][j]$)나 왼쪽($A[i][j-1]$) 의 값을 $A[i][j]$에 할당시켜줘야 함을 알 수 있다.
지금의 경우 위쪽, 왼쪽 모두 lcs가 1이지만 값이 다를 경우에는 더 큰 값을 할당시켜주면 되시겠다.
계속해서,
1에서 fbdk 2에서 kdk를 가져왔을 때, subsequence dk로 lcs는 2가 된다.
이때, 기존의 fbd 와 kd에서 'k'라는 공통된 문자가 추가되면서 common subsequence의 길이가 연장되는 것으로 이해할 수 있다.
즉, 아래와 같이 점화식을 작성해 볼 수 있다.

$A[i][j]=\begin{cases}
    A[i-1][j-1] + 1\quad(t1[i]==t2[j])\
    MAX(A[i-1][j], A[i][j-1])\quad(t1[i]!=t2[j])\
\end{cases}$ 

꼭 대각선이어야 하는가?
문득 이런생각이 들 수 있다.
예를 들어 위쪽의 경우, 기존의fbdk와 kd인 상태에서 text2에만 k가 추가적으로 붙으면서 common subsequence가 +1이 된다라고 생각할 수 있다. 그러나 이 경우에는 대각선, 위, 왼쪽의 값이 같으면서 우연히 답이 같을 뿐이다.
아래와 같이 중복된 문자의 예외를 고려하지 못하는 것을 확인할 수 있다.

패딩 넣기
점화식을 살펴보면 i-1과 j-1을 참조함을 알 수 있다.
따라서 i와 j를 단순히 0부터 시작하게 되면 out of bound error를 범하게 된다.
이를 방지하기 위해 배열의 가로세로에 패딩을 적용시켜준다.배열의 [1][1]부터 채워줘야 하므로 점화식의 A배열 인덱스 변수i, j에 +1씩을 해준다.

$A[i+1][j+1]=\begin{cases}
    A[i][j] + 1\quad(t1[i]==t2[j])\
    MAX(A[i][j+1], A[i+1][j])\quad(t1[i]!=t2[j])\
\end{cases}$ 

Solution
#include 
#define MAX(a,b) ((a)>(b)?(a):(b))

int arr[1001][1001];

int longestCommonSubsequence(char* text1, char* text2) {
    int t1Len=strlen(text1);
    int t2Len=strlen(text2);

    for (int i=0;i

Time Complexity
t1Len=N, t2Len=M 이라고 할 때, $O(NM)$이다.



[LeetCode] 516. Longest Palindromic Subsequence
Sun, 11 Aug 2024 14:20:24 GMT
Intuition
임의의 두 문자가 같거나 다른지에 따라 관계식에 변화가 있을 것이라고 추정했다.
Approach
문제 정의

$A[i][j]$ : $[i:j]$의 범위에서 Longest Palindromic Subsequence(이하 LPS)
Goal : $A[0][strlen(s)-1]$

위와 같이 문제를 정의한다. 
길이가 1인경우에는 그 자체로 LPS이다.

baseCase : $A[i][j]=1$ $(i==j)$

점화식 세우기
임의의 두 원소가 같은 경우, 그 내부(직전) LPS의 길이에서 2만큼 늘어난다.

그렇지 않은 경우, $[i+1:j]$와 $[i:j-1]$의 범위 중 LPS가 더 큰 쪽의 값을 취한다.

점화식 : 
$A[i][j]=\begin{cases}
    A[i+1][j-1] + 2\quad(s[i]==s[j])\
    MAX(A[i+1][j], A[i][j-1])\quad(s[i]!=s[j])\
\end{cases}$ 

이때 i는 i+1에서 참조하고, j는 j-1에서 참조하므로
i는 역순으로, j는 순서대로 순회해야한다.
Solution
#include 
#define MAX(a,b) ((a)>(b)?(a):(b))
int ans[1000][1000];

int longestPalindromeSubseq(char* s) {
    int len=strlen(s);

    ans[0][0]=1;
    for (int i=1;i<=len-1;i++){
        ans[i][i-1]=0;
        ans[i][i]=1;
    }

    for (int i=len-1;i>=0;i--){
        for (int j=i+1;j<=len-1;j++){
            if(s[i]==s[j]) ans[i][j]=ans[i+1][j-1]+2;
            else ans[i][j]=MAX(ans[i+1][j],ans[i][j-1]);
        }
    }  

    return ans[0][len-1]; 
}
사실 ans배열을 전역변수로 선언했기 때문에 0은 굳이 초기화시켜줄 필요는 없다.
Time Complexity
교수님께서 $O(N^2)$으로 교안에 작성해주셨다.
내가 생각하기에는 표로 보았을 때 대각선 기준으로 반절만 순회하기때문에 O(N)이 아닌가 싶다. 
이 문제를 풀때 내가 놓쳤던 점은 너무 순방향(LIS처럼 앞에서 뒤로)으로만 풀이하려했고, 거기에만 집중했다는 점이다. 관계를 생각하기보다, 문제를 간단명료하게 잘 정의하는 것에 집중해보아야겠다.



[LeetCode] 416. Partition Equal Subset Sum
Thu, 08 Aug 2024 14:39:53 GMT
Intuition
각 원소들의 사용여부에 대해 모든 경우의 수를 따져본다.
Approach
[1,5,11,5] 의 배열을 예시로 들겠다.
전체합의 반인 11을 만들 수 있는지 확인해야한다.
첫번째 원소 1의 경우 사용하지 않게 되면 0을 만들 수 있고, 사용하면 1을 만들 수 있다.

두번째 원소 5를 사용하지 않게 되면, 0 또는 1이 그대로 유지된다.

사용하게 되면, 5 또는 6을 만들 수 있다.


즉, 다음과 같은 점화식을 세워볼 수 있다.
$ans[i][j]=True$ (if, $ans[i-1][j]==True$ or $ans[i-1][j-nums[i]]$)

위와 같은 방법으로 마지막 원소까지 확인해준다. 이때, 합이 11을 초과하는 경우는 굳이 살펴볼 필요가 없다.
2차원 배열에서 1차원 배열로
i가 증가할 때, i-1때 T였던 값은 i일때도 T이다.
따라서, 2차원 배열 대신 1차원 배열로 좀 더 간단하게 처리해볼 수 있다.

이전에 True 였던 값들을 따로 유지시켜줄 필요가 없기 때문에, 점화식 또한 간단해진다.
$ans[j]=True$ (if $ans[j-nums[i]]==True$)

이때, 주의할 점은 j를 뒤에서부터 살펴보아야 한다는 점이다.
예를 들어 $nums[i]=3$ 인 경우에는 3과4는 0과 1을 통해 true임을 확인할 수 있다.
그러나 여기서 먼저 true로 표시를 하게되면 6과 7에서도 3과4로 인해 true로 계산된다. 

Solution
#include 

bool canPartition(int* nums, int numsSize) {
    int sum=0;
    for(int i=0;i=nums[i];j--){
            if(ans[j-nums[i]]) ans[j]=1;
            if(ans[half]) return 1;
        }
    }

    return 0;    
}
Complexity
Time Complexity

우선 기본적으로 바깥의 for문은 N번, 안쪽의 for문은 half-nums[i]번 반복된다.
이때, nums배열의 최댓값을 K라고 하겠다.
worst case에 대해 계산하므로 half는 $1\over2$NK가 된다.
따라서 $O(N^2K)$로 표현할 수 있다.
"worst case에 대해 계산하므로 half는 $1\over2$NK가 되어 안쪽 for문은 $1\over2$NK-K번 반복되는 것 아닌가?"라고 생각했지만->교수님께서 이부분에 대해 언급x
Space Complexity
ans배열을 half만큼 추가로 생성한다.
$O(NK)$



[LeetCode] 279. Perfect Squares
Wed, 07 Aug 2024 13:44:34 GMT
Intuition
제곱수들만의 합으로 특정 숫자를 구성한다. 이때, 최소한의 숫자가 몇개인지 구하는 문제이다.
LIS의 변형 느낌이다.
이번 문제는 쉽기때문에 간단하게 요약 작성하였다
Approach and Solution
1을 만들기 위해서는 1만 있으면 된다.
2는 1+1, 0+2 모두 가능하지만, 문제 조건상 전자만 가능하다.
3은 1+1+1
4는 1+1+1+1과 0+4 가 가능하다. 따라서 최소 숫자는 후자인 1개가 된다.

즉, $ans[i]=ans[i-j^2]+1$ if $(ans[i]+1>ans[i-j^2]+1)$ 으로 정리할 수 있다.
int numSquares(int n) {
    int ans[10001];
    ans[0]=0;

    for (int i=1;i<=n;i++){
        ans[i]=ans[i-1]+1;
        for (int j=2;i-j*j>=0;j++) { // j<=10000 빼도 될 것 같음
            if (ans[i]>ans[i-j*j]+1) ans[i]=ans[i-j*j]+1;
        }
    }

    return ans[n];
}




[LeetCode] 462. Minimum Moves to Equal Array Elements II
Mon, 15 Jul 2024 13:28:55 GMT
Intuition
$argmin_x\sum\left\vert arr_i-x \right\vert$을 찾는 문제로 귀결된다.
이때 $x$는 중간의 적당한 어떤 값인 평균이나 중앙값 중 하나일 것이라고 추측했다.
Approach
중앙값일 때 결과값이 최소화되고 중앙값에서 멀어질수록 결과값이 커지는 패턴을 발견할 수 있다.
중앙값을 찾기 위해 배열을 정렬한다음 문제를 풀이해주면 된다.
Solution
#include 
#define ABS(x) (x)<0?-(x):(x)

void merge(int* nums, int l, int r, int mid){
    int i=l;
    int j=mid+1;

    int* tmp=(int*)malloc(sizeof(int)*100000);
    int tmpP=l;

    while(i<=mid&&j<=r){
        if (nums[i]>nums[j]) tmp[tmpP++]=nums[j++];
        else tmp[tmpP++]=nums[i++]; 
    }

    while(i<=mid) tmp[tmpP++]=nums[i++];
    while(j<=r) tmp[tmpP++]=nums[j++];

    for (int k=l;k<=r;k++) nums[k]=tmp[k];
    free(tmp);
}

void split(int* nums, int l, int r){
    if (l

Time Complexity
MergeSort를 사용했기때문에 $O(NlogN)$이 소요된다.
Sorting
MergeSort말고 QuickSort나 HeapSort를 사용해도 무관하다.
아래에는 퀵소트와 힙소트를 작성해보았다.
#include

void swap(int* arr, int a, int b){
    int tmp=arr[a];
    arr[a]=arr[b];
    arr[b]=tmp;
}

int partition(int* arr, int left, int right){
    int low=left+1;
    int high=right;

    while(1){ 
        while(lowleft&&arr[high]>=arr[left]) high--;

        if (high<=low){
            swap(arr,left,high);
            return high;
        }
        swap(arr,low,high);
    }
}

void quickSort(int* arr, int left, int right){
    if (left

#include 

int heap[100];
int heapSize=0;

void insertionHeap(int ele){
    heapSize++;
    int cur=heapSize;
    while(cur>1&&ele>heap[cur/2]){
        heap[cur]=heap[cur/2];
        cur/=2;
    }
    heap[cur]=ele;
}

int getChild(int cur){
    return heap[cur*2]

지적 및 질문 환영



[LeetCode] 946. Validate Stack Sequences
Sun, 07 Jul 2024 11:37:32 GMT
Intuition
pushed의 원소들을 stack에 push하면서 popped의 원소들과 비교해본다.
Approach
예시를 들어보겠다. sp는 stack pointer, pushp와 popp는 각각 push pointer, pop pointer다.1,2,3은 popp의 4와 일치하지 않으므로 모두 stack에 push해준다.이 다음 4까지 push를 해주고나면,popp의 4와 일치하기 때문에 stack에서 4를 pop해주고, popp도 +1시켜준다. 이런식으로 popp이 popped배열의 끝까지 도달한다면, 두 배열이 stack으로 구현 가능함을 의미한다.
Solution
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) {
    int arr[1000];
    int sp=0;
    int pushp=0;
    int popp=0;

    while (pushp0&&arr[sp-1]==popped[popp]){
            sp--;
            popp++;
        }
    }

    return popp==poppedSize;
}
Time Complexity
push와 pop의 모든 동작을 합쳐도 결국에 두 배열의 크기만큼인 2N이다.
따라서, $O(N)$
맞는지 모르겠다
지적 및 질문 환영



[LeetCode] 856. Score of Parentheses
Sat, 06 Jul 2024 11:11:18 GMT
Intuition
stack 에 여는괄호 '(' 를 넣으면서 닫는괄호 ')' 가 나올 때마다 경우에 맞게 처리해주는 방식으로 풀이했다.
Approach
'(()())' 을 예시로 설명해보겠다. 그림으로 표현해보면 아래와 같은 상황이다. sp는 스택포인터다.
여는 괄호가 등장했으므로 스택에 여는 괄호를 의미하는 -1(임의숫자)을 push해준다. 이때 중요한 점은 '('를 그대로 넣지 않는다는 것이다. 여는 괄호도 결국에는 ascii table상 40이기 때문에 점수 계산을 양수인 숫자로 하는 우리에게 혼선을 준다.그 다음 경우도 마찬가지다.이번에는 닫는 괄호를 만났으므로 스택을 확인한다. 여는 괄호가 있기때문에 두 여닫는 괄호가 합쳐저 1점으로 바뀐다.이어서 계속 진행해준다.닫는 괄호를 만났으므로 -1이 나올 때까지 pop한다. 그리고 그 사이에 있는 점수들을 더한 후 2를 곱하여 push해준다.이제 모든 괄호를 다 확인했으므로 pop을 하면 자동으로 답이 튀어나온다.
그렇지만 아래 그림과 같이 합산해줘야 하는 경우도 있으므로 stack이 빌 때까지 pop하여 그 합을 결과값으로 반환한다.
Solution
int sp=0;
int arr[50];

void push(int ele){
    arr[sp++]=ele;
}

int pop(){
    return arr[--sp];
}

int scoreOfParentheses(char* s) {
    for (int i=0;s[i]!=0;i++){
        if(s[i]=='(') push(-1);
        else{
            int ele=pop();
            if(ele==-1) push(1);
            else{
                int tmp=0;
                while(ele!=-1){
                    tmp+=ele;
                    ele=pop();
                }
                push(2*tmp);
            }
        }
    }

    int res=0;
    while(sp>=1){
        res+=pop();
    }

    return res;
}
Time Complexity
$O(N)$
지적 및 질문 환영



[LeetCode] 4. Median of Two Sorted Arrays
Wed, 26 Jun 2024 11:52:39 GMT
Intuition
$O(log(m+n))$의 시간 복잡도 내에 문제를 해결해야 하기 때문에, 실제로 두 배열을 합치는 방식은 배제한다. 실제로 정렬을 수행하지 않으면서 median을 찾는 방법을 고안해야한다. 
중앙값이 $N$개의 원소들을 정렬했을 때 $N\over2$(또는 $N+1\over2$)에 있는 것을 고려하여 개수에 중점을 두고 풀이해본다.  
Approach
[1,3,4,6] [2,7,8]의 두 배열을 합치면 아래와 같은 결과가 나온다.
좀 더 자세하게 표시하면 아래와 같다.즉, 두 배열에서 임의의 개수만큼씩이 빨간 부분에 해당되고 나머지 부분들은 초록 부분에 해당된다는 것이다. 

이때,
1. 합쳐진 배열에서 빨간부분의 개수는 $O(1)$에 구할 수 있다.
2. 그에 따라, nums1에서의 빨간부분의 개수가 정해지면 nums2에서의 빨간부분 개수도 자동으로 정해진다.
이어지는 내용에서 더 자세히 살펴보겠다.

합쳐진 배열이 홀수개인 경우와 짝수개인 경우를, 빨간부분의 인덱스 i와j를 활용하여 각각 표시해보면 아래와 같다.

전자와 후자모두 인덱스 i와j는 2와0이다. 빨간색 부분의 개수는 각각의 인덱스에 +1씩을 하여 i+j+2$\cdots①$ 즉, 2+0+2(개) 가 된다.
빨간 부분의 개수는 두 배열의 사이즈를 통해서도 구할 수 있다.
홀수인 경우와 짝수인 경우 모두, 빨간부분이 M또는 M1을 포함하도록 설계하기 위해 빨간부분의 개수는 $nums1Size+nums2Size\over2$가 아닌, ${nums1Size+nums2Size+1\over2}\cdots②$로 구한다.

①,②에서
$i+j+2={nums1Size+nums2Size+1\over2}$ (개)
$j={nums1Size+nums2Size+1\over2}-(i+1)$ (개)
인덱스 $j$의 값을 구하려면 $-1$을 해준다.
$\therefore j_{index}={nums1Size+nums2Size+1\over2}-i-2$

임의의 $i,j$가 설정 되었을 때
그렇다면 임의의 i와 j가 설정되었을 때, 그것이 올바른 i와j인지 판단하려면 어떻게 해야할까.

빨간 부분과 초록부분이 어떻게 정렬되는지는 우리는 실제로 신경쓰지 않는다. 다만, 제대로 i와j가 설정되었는지 판단하기 위해 빨간부분의 최댓값보다 초록부분의 최솟값이 더 큰지만 확인해주면 된다. 
 
 
물론, 올바른 i와 j가 아닌것으로 판명났을 때에는 조정이 필요하다.
위와 같이 i의 값이 너무 작은 경우에는 그 값을 크게 해주어야 하는데, 얼마나 크게 해줄지를 결정해야한다. 우리는 여기에 이진탐색을 적용한다.
이때, 배열에서 한개도 빨간부분에 포함되지 않는 경우도 존재하기 때문에 이를 인덱스 -1로 나타내기로 한다.

$i=l+{r-l\over2}=-1+{4-(-1)\over2}=1$

i가 1인 경우 nums2의 빨간부분 최대값9와 nums1의 초록부분 최솟값4가 대소관계가 맞지 않는다.
이 경우 l을 i+1로 옮겨 이진탐색을 지속한다.이번에는 i를 줄여줘야 하므로 r을 i-1로 설정함으로써 정답을 찾을 수 있다.
지금까지 설명한 부분을 코드로 작성하면 아래와 같다.
...

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
...
    int l=-1, r=nums1Size-1; // -1은 안쓴다는 뜻
    double res;

    while(1){
        int i=l+(r-l)/2;
        int j=(nums1Size+nums2Size+1)/2-i-2;

       ...
        if(...&&nums1[i]>nums2[j+1]){
            r=i-1; 
            continue;
        }
        if(...&&nums2[j]>nums1[i+1]){
            l=i+1;
            continue;
        }
        else{
            // 올바른 i,j 일 때
        }
  ...
    }
    return res;
}
배열에 접근할 때
배열에 접근할 때에는 유효한 인덱스인지를 체크해줘야한다.
우선 i와 j모두 -1부터 numsSize-1까지만이 유효하다.

$-1\leq i,j \leq numsSize-1$

그런데 i의 경우에는 이진탐색에 의해 통제하기 때문에 유효한 범위에서 벗어날 일이 없다.
j의 경우는 i의 값에 따라 -1보다 작아지거나 nums2Size의 값 이상으로 커지는 경우가 존재한다.
전자는 i의 값이 작아지게, 후자는 i의 값이 커지게 이분탐색함으로써 값을 조정한다.
 
...

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
...
    int l=-1, r=nums1Size-1; // -1은 안쓴다는 뜻
    double res;

    while(1){
        int i=l+(r-l)/2;
        int j=(nums1Size+nums2Size+1)/2-i-2;

        /* 추가된 코드 */
        if(j<-1){
            r=i-1;
            continue;
        }
        if(j>=nums2Size){
            l=i+1;
            continue;
        }
        /* 추가된 코드 */

        if(...&&nums1[i]>nums2[j+1]){
            r=i-1; 
            continue;
        }
        if(...&&nums2[j]>nums1[i+1]){
            l=i+1;
            continue;
        }
        else{
            // 올바른 i,j 일 때
        }
  ...
    }
    return res;
}
 
 
그러나 유효한 값임에도 불구하고 -1이라는 인덱스는 우리가 해당 배열을 사용하지 않을 때를 가정한 가상의 인덱스이기 때문에 따로 처리를 해줘야한다. 추가적으로 j+1이나 i+1 또한 존재하지 않는 케이스를 대비해야한다.
예를 들어, 아래 그림에서 nums2의 빨간부분의 최댓값과 nums1의 초록부분의 최솟값을 비교해야하는데 j는 -1, i+1은 유효하지 않은 인덱스로 비교가 불가능하다.
그러나, 문제상황에서 비교대상 둘 중 하나 이상이 없는 것은 적절한 i와 j가 됨에 문제가 되지 않음을 뜻한다. 
...

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
...
    int l=-1, r=nums1Size-1; // -1은 안쓴다는 뜻
    double res;

    while(1){
        int i=l+(r-l)/2;
        int j=(nums1Size+nums2Size+1)/2-i-2;

        if(j<-1){
            r=i-1;
            continue;
        }
        if(j>=nums2Size){
            l=i+1;
            continue;
        }
        if(i!=-1&&j+1!=nums2Size&&nums1[i]>nums2[j+1]){ // 추가된 코드
            r=i-1; 
            continue;
        }
        if(ㅊnums2[j]>nums1[i+1]){ // 추가된 코드
            l=i+1;
            continue;
        }
        else{
            // 올바른 i,j 일 때
        }
  ...
    }
    return res;
}
중앙값 찾기
올바른 i와 j를 찾았다면 이제 median 값을 구하는 것만 남았다.
홀수개인 경우에는 빨간색 부분의 최댓값만 구하면 된다.
짝수개인 경우에는 초록색 부분의 최솟값도 구하여 두 값의 평균을 구한다.
        else{
            if((nums1Size+nums2Size)%2){ // odd
                int max=-1000001;
                if(i!=-1) max=MAX(max,nums1[i]);
                if(j!=-1) max=MAX(max,nums2[j]);
                res=max; 
            } 
            else{ // even
                int max=-1000001;
                if(i!=-1) max=MAX(max,nums1[i]);
                if(j!=-1) max=MAX(max,nums2[j]);

                int min=1000001;
                if(i+1!=nums1Size) min=MIN(min,nums1[i+1]);
                if(j+1!=nums2Size) min=MIN(min,nums2[j+1]);

                res=(max+min)/(double)2;
            }
            break;
        }
더 작은 배열에서 탐색하기
마지막으로, nums1과 nums2 중 더 작은 배열을 항상 nums1으로 만들어준다.
이진탐색의 범위가 줄어드므로 시간복잡도도 줄어든다.
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    /* 추가된 코드 */
    if (nums1Size>nums2Size){
        int* tmp=nums1;
        nums1=nums2;
        nums2=tmp;
        int tmp2=nums1Size;
        nums1Size=nums2Size;
        nums2Size=tmp2;
    }
    /* 추가된 코드 */

    int l=-1, r=nums1Size-1; // -1은 안쓴다는 뜻
    double res;

    while(1){
        int i=l+(r-l)/2;
        int j=(nums1Size+nums2Size+1)/2-i-2;

        if(j<-1){
            r=i-1;
            continue;
        }
        if(j>=nums2Size){
            l=i+1;
            continue;
        }
        if(i!=-1&&j+1!=nums2Size&&nums1[i]>nums2[j+1]){
            r=i-1; 
            continue;
        }
        if(j!=-1&&i+1!=nums1Size&&nums2[j]>nums1[i+1]){
            l=i+1;
            continue;
        }
        else{
            if((nums1Size+nums2Size)%2){ // odd
                int max=-1000001;
                if(i!=-1) max=MAX(max,nums1[i]);
                if(j!=-1) max=MAX(max,nums2[j]);
                res=max; 
            } 
            else{ // even
                int max=-1000001;
                if(i!=-1) max=MAX(max,nums1[i]);
                if(j!=-1) max=MAX(max,nums2[j]);

                int min=1000001;
                if(i+1!=nums1Size) min=MIN(min,nums1[i+1]);
                if(j+1!=nums2Size) min=MIN(min,nums2[j+1]);

                res=(max+min)/(double)2;
            }
            break;
        }
    }
    return res;
}
Solution
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    if (nums1Size>nums2Size){
        int* tmp=nums1; nums1=nums2; nums2=tmp;
        int tmp2=nums1Size; nums1Size=nums2Size; nums2Size=tmp2;
    }

    int l=-1, r=nums1Size-1; // -1은 안쓴다는 뜻

    while(1){
        int i=l+(r-l)/2;
        int j=(nums1Size+nums2Size+1)/2-i-2;

        if(j<-1){ r=i-1; continue; }
        if(j>=nums2Size){ l=i+1; continue; }
        if(i!=-1&&j+1!=nums2Size&&nums1[i]>nums2[j+1]){ r=i-1; continue; }
        if(j!=-1&&i+1!=nums1Size&&nums2[j]>nums1[i+1]){ l=i+1; continue; }
        else{
            int max=-1000001;
            if(i!=-1) max=MAX(max,nums1[i]);
            if(j!=-1) max=MAX(max,nums2[j]);

            if((nums1Size+nums2Size)%2) return max;

            int min=1000001;
            if(i+1!=nums1Size) min=MIN(min,nums1[i+1]);
            if(j+1!=nums2Size) min=MIN(min,nums2[j+1]);

            return (max+min)/(double)2;
            break;
        }
    }
    return 0; // 여기까지 올 일은 없다.
}
Time complexity
nums1과 nums2중 더 작은 배열에서 이분탐색을 진행한다.
$O(log(MIN(n,m)))$



[LeetCode] 33. Search in Rotated Sorted Array
Sun, 24 Mar 2024 05:29:50 GMT
Intuition
문제에서 한번 회전된 배열이 input으로 들어오는 경우, 이진탐색을 적용할 수 없다.
즉, 회전되기 전의 배열을 구해야한다.
Approach
회전되기 이전의 배열을 구하기 위해 회전이 된 기준점인 pivot을 이진탐색을 통해 탐색했다.

우선, numsSize가 1인 경우의 pivot은 0일수밖에 없고, 회전이 되어있지 않은 케이스는 nums[l]

int search(int* nums, int numsSize, int target) {
    int originalZeroIdx;
    int l=0;
    int r=numsSize-1;
    if (numsSize==1) originalZeroIdx=0;
    else{
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[l]

 
가령, [6,7,8,9,1] 이라는 배열이 있다.
nums[l],nums[mid],nums[r]은 각각 6,8,1이 된다. nums[l]nums[r] 이므로 l부터 mid까지는 정렬이 되어있고 mid부터 r까지는 정렬이 되어있지 않은 즉, mid부터 r까지사이에 pivot이 있음을 알 수 있다.
그러므로 다음 번 탐색때는 r=mid로 두고 [8,9,1] 을 탐색한다. 한번 더 같은 과정을 반복하면 [9,1] 만 남게되고 l과 mid가 같아지게 된다.
이때 회전이 되지 않은 경우는 위에서 걸러졌으므로, 해당 배열은 무조건 회전이 한번 발생하였고 그 결과로 pivot이 항상 r에 위치하게 된다.
int search(int* nums, int numsSize, int target) {
    int originalZeroIdx;
    int l=0;
    int r=numsSize-1;

    if (numsSize==1) originalZeroIdx=0;
    else{
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[l]nums[mid]&&nums[mid]

여기까지의 과정을 통해 pivot을 구했다.
[6,7,8,9,1]의 경우 pivot index는 4이다.이제 원래 배열을 구할 수 있고, 이진탐색도 가능해졌다.
가령, nums[0]에 접근했을 때 6이 아니라 나머지 연산을 통해, 회전시키기 전의 값인 1이 나오게만 만들어주면 된다.
Solution
int search(int* nums, int numsSize, int target) {
    int originalZeroIdx;
    int l=0;
    int r=numsSize-1;

    if (numsSize==1) originalZeroIdx=0;
    else{
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[l]nums[mid]&&nums[mid]target) r=mid-1;
        else l=mid+1;
    }

    return -1;
}
교수님 풀이
우리는 정렬되어 있는 배열 내에서는 이진탐색을 활용할 수 있고, 또한 범위내에 target값이 존재하는지 여부에 대해서도 알 수 있다.
교수님의 풀이는 정렬되어있는 부분을 활용하여 이진탐색 알고리즘을 개선한다.
본 문제에서는 최대 한 번의 회전이 일어날 수 있기 때문에 배열을 반으로 나누면, 둘 중 하나는 무조건 정렬이 되어있을 수 밖에 없다.
가령 [6,7,8,9,1]에서 target이 6이라 할때, 배열은 [6,7,8] 과 [9,1]로 나뉜다.
nums[l]과 nums[mid]의 대소비교, nums[mid]와 nums[r]의 대소비교를 통해 각각의 정렬 여부를 알 수 있다.
정렬된 배열 [6,7,8]의 범위내에 target 6이 속하기 때문에 [6,7,8]과 [9,1] 중 전자에 대해 이진탐색을 계속한다. 만약 target이 9였다면 정렬된 배열[6,7,8]의 범위에 속하지 않기 때문에 후자를 택한다.
Solution
int search(int* nums, int numsSize, int target) {
    int ans=-1;
    int l=0;
    int r=numsSize-1;
    while (l<=r){
        int mid=l+(r-l)/2;

        if (nums[mid]==target){
            ans=mid;
            break;
        }
        else if (nums[l]<=nums[mid]){ // l부터 mid까지가 정렬된 배열인지 판단
            if (nums[l]<=target&&target

Time Complexity
내 풀이와 교수님 풀이 모두 이진탐색만을 사용하므로 $O(log N)$이다.
지적 및 질문 환영



[LeetCode] 275. H-Index II
Sat, 09 Mar 2024 15:10:30 GMT
Intuition
citations.length에 따라 h의 최댓값이 결정되는 점에 주목하여 이진탐색을 진행했다.
Approach
[3,3,100] 이라는 배열이 있을 때, 배열의 길이가 3이므로 h는 최소1, 최소3 의 범위 내에서 구할 수 있다.
1부터 3까지의 범위에서 이진탐색을 진행해보겠다.
중간값은 2이고, 이 값이 정답후보가 되기 위해서는 배열의 뒤에서부터 두번째 부분이 2보다 크거나 같은지만 확인해주면 된다. (배열이 오름차순 정렬이기때문에 그 외에는 확인할 필요가 없다.)

일반화하면, l부터 r까지의 범위에서 이진탐색을 진행한다. (각각, 1과 배열의 크기로 초기화)
중간값이 정답후보가 되려면 배열의 뒤에서부터 mid번째 원소가 mid값보다 크거나 같아야한다.
 
크거나 같다면, mid는 정답후보가 되고, 조건을 만족하는 더 큰 h가 존재할 수도 있으므로 l은 mid+1이 된다.
 
그렇지 않다면, mid값이 너무 큰 것이므로 r은 mid-1이 된다.

int hIndex(int* citations, int citationsSize) {
    int ans;
    int l=1;
    int r=citationsSize;

    while (l<=r){
        int mid=l+(r-l)/2;
        if (citations[citationsSize-mid]>=mid){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }

    return ans;
}
그러나 우리가 l을 1로 초기화했기 때문에 배열에 0만 존재하는 경우에 대해서는 대응할 수 없게 된다.

조금 더 구체적으로는 citationsSize가 n이라고 할때, 나올 수 있는 모든 경우의 수는 n+1개이다. 그러나, 우리가 이진탐색으로 살펴보는 범위는 1부터 n까지로, n개이다. 한가지 경우의 수를 빼먹은 것인데 그것이, h가 0이 나오는 경우이다.  

따라서 ans를 0으로 초기화하여 이런 케이스까지 대응할 수 있다.
Solution
int hIndex(int* citations, int citationsSize) {
    int ans=0;
    int l=1;
    int r=citationsSize;

    while (l<=r){
        int mid=l+(r-l)/2;
        if (citations[citationsSize-mid]>=mid){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }

    return ans;
}
Time Complexity
이진탐색의 시간복잡도와 동일하다.
$O(log N)$
지적 및 질문 환영



[LeetCode] 400. Nth Digit
Sat, 24 Feb 2024 14:41:15 GMT
Intuition
이진탐색으로 output후보를 탐색하면서, 그때그때마다 해당 후보가 정답범위에 있는지를 체크하기로 했다.
Approach
예를 들어 12는 10에서 2만큼 차이가 나고, 또 두자리수이기 때문에 10에서 1씩 커질때마다 digits는 2씩 증가한다. 따라서 10+(12-10)2=14 즉, 12에서 1은 14번째 자리수이다.
또 다른 예시로 99는 10+(99-10)2=188 즉, 각각 188번째, 189번째 수가 될 것이다.
이어서 100은 99의 다음 숫자이므로, 100의 1은 190번째 수가 된다.
마지막 예시로 777은 190+(777-100)3 으로 계산할 수 있다.


위와 같이 일반화할 수 있다.

즉, 우리가 어떤 수 k의 자리수(ex. 두자리수, 세자리수)와 해당 자리수의 시작하는 출발digit(?)(위 표에서 1,10,190,x에 해당하는 부분)만 알고있다면 $O(1)$만에 k의 digits을 구할 수 있다는 것을 알 수 있다는 것이다.
digits을 구하고나서, n에서 digits을 뺀 값이 자리수보다 작다면 어떤 숫자 k에 정답이 존재하는 것이다.
예를 들어, n이 542이고 이진탐색 과정으로 나온 후보 숫자 k가 217이다.
190+(217-100)3=541이므로 217은 각각 541번째, 542번째, 543번째 digits이다.
{n}-{digits}=542-541=1<{자리수}=3이므로 k에 정답인 digits이 존재함을 알 수 있다.
즉, {자리수}-({n}-{digits})=3-(542-541)=2이므로 일의 자리부터 두번째 자리에 정답이 위치하는 것을 알 수 있다.
두번째 자리 숫자를 구하기 위해 217을 10으로 한번 나누고 %10연산을 한 번 취해주면 정답인 1을 구할 수 있게 된다.
Solution
long startArray[10]; // 위의 표에서 x에 해당하는 부분을 담는 배열

int check(int mid, int n){
    int digits=0; // 자리수를 담는 변수 (ex. 두자리수, 세자리수 ...)
    int tmp=mid;
    while (tmp!=0){
        tmp/=10;
        digits++;
    }

    int ten=1; 
    tmp=digits;
    while (--tmp) ten*=10; // 자리수만큼 10의 제곱을 만들어주기
    long calc=startArray[digits-1]+((long)mid-ten)*digits;

    if (calc>n) return 0; 
    if (n-calc

Time Complexity
startArrayFunc는 최초 실행시 딱 한 번 수행된다.
이진탐색과 함께 매번 check함수가 호출되지만 기껏해야 반복문은 10번돈다.
따라서,이진탐색의 시간복잡도만 유의미한 영향을 미칠 것으로 예상한다.
$O(logN)$
지적 및 질문 환영



[LeetCode] 1011. Capacity To Ship Packages Within D Days
Fri, 23 Feb 2024 14:33:16 GMT
Intuition
가능한 capacity를 이진탐색을 통해 후보를 정한 다음, 그때그때 그것이 가능한지 체크한다.
이때, 점점 capacity가 작아지도록 이진탐색하여 최솟값을 찾는다. 
Approach

어떤 시점 x부터는 capacity가 모두 가능해진다. 이 x를 찾기 위해 이진탐색을 진행할 것이다. 


위의 표에서는 편의를 위해 최댓값을 $2^{31}$로 썼지만, 실제로 이 문제에서의 최댓값은 계산이 가능하다. 문제의 조건에 따라, 최대의 무게로 최대한의 weight length만큼을 1일만에 옮기기 위한 capacity 즉, $500(510^4)=25*10^6$이다.
이진탐색을 진행하며, capacity후보가 days안에 수송이 가능한지 체크하고 가능한 경우 최댓값 변수를 중앙값-1로 업데이트하여 더 작은 capacity후보를 찾도록 설계한다.
int shipWithinDays(int* weights, int weightsSize, int days) {
    int m=1;
    int M=25000000;
    int ans;

    while (m<=M){
        int med=m+(M-m)/2;

        if (possible(med,weights,weightsSize,days)){
            ans=med;
            M=med-1;
        }
        else m=med+1;
    }    

    return ans;
}
 
이제 capacity후보가 days안에 수송이 가능한지 체크를 하는 함수를 작성해야한다.
기본적으로, weights[i]가 capacity보다 크면 해당 capacity는 불가능하다.
int possible(int med, int* weights, int weightsSize, int days){
    ...

    for (int i=0;imed) return 0;

        ...
    }
    ...
}
 
weights[i]를 누적하다가 capacity를 초과하는 경우, day를 하루 증가시키고 오늘 옮기지 못한 weights[i]는 남겨둔다.
for문이 끝났을 때, 내일 옮겨야 할 weights[i]가 항상 남아있게 되므로 day는 0이 아니라 1로 초기화시킨다.
int possible(int med, int* weights, int weightsSize, int days){
    int cnt=0;
    int day=1;

    for (int i=0;imed) return 0;

        cnt+=weights[i];
        if (cnt>med){
            day++;
            cnt=weights[i]; // 내일 옮길 weights[i]
        }
    }

    return days>=day;
}
Solution
int possible(int med, int* weights, int weightsSize, int days){
    int cnt=0;
    int day=1;

    for (int i=0;imed) return 0;

        cnt+=weights[i];
        if (cnt>med){
            day++;
            cnt=weights[i];
        }
    }

    return days>=day;
}

int shipWithinDays(int* weights, int weightsSize, int days) {
    int m=1;
    int M=25000000;
    int ans;

    while (m<=M){
        int med=m+(M-m)/2;

        if (possible(med,weights,weightsSize,days)){
            ans=med;
            M=med-1;
        }
        else m=med+1;
    }    

    return ans;
}
Time Complexity
상수로 표현하면,
capacity후보를 이진탐색하는데에 capacity의 최댓값에 log를 취한 $log(2510^6)$,
해당 capacity가 가능한지 확인하는데에 weights.length인 $510^4$ 이다.
rough하게 $O(N logN)$이라 표현할 수 있다.



[LeetCode] 1079. Letter Tile Possibilities
Mon, 19 Feb 2024 11:10:28 GMT
Intuition
같은 문자끼리는 구분하지 않으므로 개수를 기준으로 풀이하면 될 것이라 생각했다.
Approach&Solution
int alphabet[26]; // A-Z까지 각각 몇 번이 나오는지 카운트하는 배열
int cnt; // 결과값

void counter(){
    for (int i=0;i<26;i++){
        if (alphabet[i]>0){ // 1 이상이면 해당 문자를 다 쓰지 않았다는 뜻, 또한 이 line이 사실상 base case가 됨
            alphabet[i]--; 
            cnt++; // 모든 문자를 다 썼을때만 결과값을 카운트하는게 아님
            counter();
            alphabet[i]++;
        }
    }
}

int numTilePossibilities(char* tiles) {
    for (int i=0;i<26;i++) alphabet[i]=0;
    cnt=0;

    for (int i=0;tiles[i]!=0;i++){
        alphabet[tiles[i]-'A']++;
    } 

    counter();
    return cnt;
}
교수님 풀이
예를 들어, 우리가 모든 문자를 다 써야하는 문제라면 단순히 팩토리얼 계산으로도 쉽게 해결할 수 있다. (특히, 이 문제의 경우 n이 작으므로)
그러나 이 문제는 문자를 다 사용하지 않는 경우에 대해서도 고려해야하므로, 이 과정을 재귀로 풀이해볼 수 있다.
예를 들어 문자 AACZZZ가 있다면,
A 1개, C 0개, Z 0개 일 때의 경우의 수 부터
A 1개, C 1개, Z 0개
A 1개, C 1개, Z 1개
A 1개, C 1개, Z 2개
.
.
.
A 2개, C 1개, Z 3개 일 때의 경우의 수에 이르기까지, 각각 알파벳들의 개수를 재귀로 처리할 수 있다.
그리고 각각의 경우에는 단순 팩토리얼로 계산이 가능하다.

지적 및 질문 환영



[LeetCode] 44. Wildcard Matching
Sun, 18 Feb 2024 14:55:57 GMT
Intuition
'*'가 등장할 때마다 이를 분기로 삼고 재귀를 호출하는 방식으로 진행하면 되겠다고 생각했다.
그리고 이렇게 가능성 있는 케이스를 모두 살펴보고 한번이라도 가능한 케이스가 발견되면 true를 반환하면 될 것이라고 생각했다.
Approach

문자열 s와p 둘 중 하나라도 끝날때까지 문자열을 순회한다.
이때, 두 문자가 같지 않은 경우는 따로 처리를 해줘야한다. 그러나, 패턴이 '?'라면 넘어가줘도 된다.

int check(char* s, char* p, int sIdx, int pIdx){
    for (;s[sIdx]!=0&&p[pIdx]!=0;sIdx++,pIdx++){
        if (s[sIdx]!=p[pIdx]&&p[pIdx]!='?'){ // 두 문자가 '?'도 아니면서 일치하지 않을 경우
            ...
        }
    }
}

두 문자가 일치하지 않지만 true의 가능성을 갖기 위해서는 패턴이 asterisk여야 한다.
그런데 이때, asterisk가 연속으로 존재할 경우는 asterisk가 하나 있는 것과 다름이 없으므로 다른 문자가 나올때까지 패턴인덱스를 넘겨준다.
그런데 이렇게 넘겼는데 문자열이 끝나면, 마지막에 asterisk가 있으므로(이전까지의 과정에서 문제가 없었고) source문자열에 무엇이 있든간에 상관이 없다. (ex. abcd / a*)

int check(char* s, char* p, int sIdx, int pIdx){
    for (;s[sIdx]!=0&&p[pIdx]!=0;sIdx++,pIdx++){
        if (s[sIdx]!=p[pIdx]&&p[pIdx]!='?'){
            if (p[pIdx]=='*'){
                while (p[++pIdx]=='*') {} // 연속된 asterisk pass
                if (p[pIdx]==0) return 1; // 문자열이 끝난 경우
                ...
            }
            else return 0;
        }
    }
}

pIdx가 asterisk의 다음문자를 가리키고 있는 상황에서 sIdx 또한 pIdx의 문자와 동일한 문자가 나오는 케이스들을 모두 true의 가능성이 있는 경우로 볼 수 있다.
물론, asterisk의 다음문자가 '?'라면 sIdx에 어떤 문자가 오든 상관이 없다.

int check(char* s, char* p, int sIdx, int pIdx){
    for (;s[sIdx]!=0&&p[pIdx]!=0;sIdx++,pIdx++){
        if (s[sIdx]!=p[pIdx]&&p[pIdx]!='?'){
            if (p[pIdx]=='*'){
                while (p[++pIdx]=='*') {}
                if (p[pIdx]==0) return 1;
                for (;s[sIdx]!=0;sIdx++){ // 모든 케이스를 보기 위한 반복문
                    if (s[sIdx]==p[pIdx]||p[pIdx]=='?'){ 
                        if (check(s, p, sIdx+1, pIdx+1)) return 1; // 한 번이라도 가능한 케이스가 발생하면 바로 1을 반환하며 함수를 종료
                    } 
                }
                return 0; // 위의 for문을 마치고 이 line까지 왔다는 것은 asterisk와 매치되는 문자열이 존재하지 않는다는 뜻
            }
            else return 0;
        }
    }
}

위의 가장 큰 for문이 끝나게 되면, 두 문자열을 어디까지 순회하였는지 체크해야한다.
두 문자열 모두 끝까지 확인했다면, 특별히 문제가 없는 경우가 될 것이다.
그렇지 않다면 둘 중에 하나만 끝난경우로 두 문자열이 매치되지 않는 경우이다.
그러나, 마지막에 asterisk가 남아있는 경우는 예외이다. 이 경우 asterisk는 empty sequence와 매치되기 때문이다.

int check(char* s, char* p, int sIdx, int pIdx){
    for (;s[sIdx]!=0&&p[pIdx]!=0;sIdx++,pIdx++){
        if (s[sIdx]!=p[pIdx]&&p[pIdx]!='?'){
            if (p[pIdx]=='*'){
                while (p[++pIdx]=='*') {}
                if (p[pIdx]==0) return 1;
                for (;s[sIdx]!=0;sIdx++){ 
                    if (s[sIdx]==p[pIdx]||p[pIdx]=='?'){ 
                        if (check(s, p, sIdx+1, pIdx+1)) return 1; 
                    } 
                }
                return 0; 
            }
            else return 0;
        }
    }
}
if (s[sIdx]==0&&p[pIdx]==0) return 1;
else if (s[sIdx]==0) {
    while (p[pIdx]!=0) if (p[pIdx++]!='*') return 0; // asterisk외의 문자가 있는 경우 false
    return 1;
} 
else return 0;
여기까지 하게되면 기본적인 알고리즘은 완성된다. 그러나, 이상태로 submit하게되면 'Time Limit Exceeded'메세지가 뜨며 통과가 되지 않는다. 최적화를 위해 memoization을 적용해준다.
Solution
int memo[2000][2000];

int check(char* s, char* p, int sIdx, int pIdx){
    for (;s[sIdx]!=0&&p[pIdx]!=0;sIdx++,pIdx++){
        if (s[sIdx]!=p[pIdx]&&p[pIdx]!='?'){
            if (p[pIdx]=='*'){
                while (p[++pIdx]=='*') {}

                if (p[pIdx]==0) return 1;

                for (;s[sIdx]!=0;sIdx++){
                    if (s[sIdx]==p[pIdx]||p[pIdx]=='?'){ 
                        if(memo[sIdx+1][pIdx+1]==1) return memo[sIdx+1][pIdx+1]; 
// memo에 0이 적혀있더라도, for문에서 모든 가능성을 체크해야하므로 값을 return해서는 안된다.
                        if (memo[sIdx+1][pIdx+1]==-1){
                            if (memo[sIdx+1][pIdx+1] = check(s, p, sIdx+1, pIdx+1)) return 1;
                        }
                    } 
                }

                return 0;
            }

            else return 0;
        }
    }

    if (s[sIdx]==0&&p[pIdx]==0) return 1;
    else if (s[sIdx]==0) {
        while (p[pIdx]!=0) if (p[pIdx++]!='*') return 0;
        return 1;
    } 
    else return 0;
}

bool isMatch(char* s, char* p) {
    int slen;
    int plen;
    slen = plen = 0;

    while(s[slen]) slen++;
    while(p[plen]) plen++;

/*
memo[sIdx'+1'][pIdx'+1']까지 사용하므로 slen-1이 아니라 slen까지 memo를 초기화시켜줘야한다.
또한, 최대 범위가 2000이므로 slen과 plen을 상수로 처리한다고 생각할 수도 있는데, 그 경우에는 매번 4백만번의 반복문이 실행되고 여기에 1000개의 테스트케이스를 실행하게되면 엄청난 시간이 걸리게된다. 
memset함수의 경우 상수로 초기화해도 통과되는데, 이에 대해서는 추후에 다뤄보도록 하겠다.
*/
    for(int i = 0; i <= slen; i++) { 
        for(int j = 0; j <= plen; j++) memo[i][j] = -1;
    }

    return check(s,p,0,0);
}
지적 및 질문 환영




[LeetCode] 52. N-Queens II
Sun, 11 Feb 2024 14:18:28 GMT
Intuition
퀸이 공격할 수 있는 가로,세로, 대각선 방향을 체크하면 되겠다고 생각했다.
Approach
퀸을 배치할 때마다, 이전에 놓인 퀸 중 가로, 세로, 대각선 방향으로 공격할 수 있는 퀸이 존재하는지 확인해야 한다.

그러나, 직접 퀸의 좌표를 저장하는 것 대신 체스판 좌표의 특징(?) 을 활용해 볼 수 있다.
가령, (0,1)에 퀸이 있을 경우 다음에 오는 퀸의
row값은 0이 될 수 없고,
column값은 1이 될 수 없다.



대각선 방향은 합 또는 차가 같은 경우로 구분할 수 있다.



따라서, 각각의 경우를 masking하는 배열을 만들어서 $O(1)$만에 특정좌표가 배치가 가능한지 알 수 있다.
row의 경우는 재귀함수의 인자를 통해 구분하고,
column은 col배열, 합을 통해 구분하는 대각선 방향은 diag1, 남은 대각선 방향은 daig2로 구분했다.
이때 col의 최댓값은 $n-1$, diag1의 최댓값은 $2(n-1)$, diag2는 $-n+1$부터 $n-1$까지의 범위를 갖는다.

diag2는 음수가 발생하므로 값 자체를 인덱스로 사용하지 못한다. 따라서 항상 $n-1$을 더하여 $0$부터 $2(n-1)$까지의 범위를 갖도록 조정한다.

이 문제는 n이 9로 한정되므로 masking 배열의 size를 상수로 작성했다.
Solution
int cnt;
int size;
int col[9];
int diag1[17];
int diag2[17];


void checker(int row){
    if (row==size) cnt++;
    else{
        for (int i=0;i

Time Complexity
정확하게 계산해내지 못했다. 매우 rough하게, 최악의 경우 chessboard를 모두 순회하므로 $O(N^2)$으로 예상한다.
지적 및 질문 환영



[LeetCode] 733. Flood Fill
Fri, 09 Feb 2024 07:08:47 GMT
Intuition
4-directionally라는 문제 조건에 맞춰, 재귀함수를 상하좌우로 호출하면 될 것이라고 생각했다.
Approach

본격적으로 문제를 풀기에 앞서 2차원 배열을 반환하기 위한 세팅을 해줘야한다. 관련 설명은 [LeetCode] 77. Combinations에 기술했다.

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
//
#include 
//
int imgSize;
int imgColSize;
int targetColor;
int originColor;
int** res;
...
int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int color, int* returnSize, int** returnColumnSizes) {
    imgSize=imageSize;
    imgColSize=*imageColSize;
    targetColor=color;
    originColor=image[sr][sc];
    //
    *returnSize=imageSize;
    *returnColumnSizes=(int*)malloc(sizeof(int)*imageSize);
    for (int i=0;i


특정 좌표에 문제에서 원하는 color로 색칠을 해주는 함수를 만들어준다.

void paint(int sr, int sc){
    res[sr][sc]=targetColor;
    ...
}

이후 sequence는 상하좌우(순서무관)로 함수를 호출하면 되는데, 이때 호출조건은 다음과 같다.


grid의 밖으로 벗어나지 않아야 한다.
즉, column과 row의 값이 0이상이며 각각 columnSize와 rowSize보다 작아야한다.
원래 color와 동일해야 한다.
 
함수를 호출할 때에는 상하좌우 각각을 code 네줄로 처리할 수도 있지만 아래와 같은 테크닉으로 한줄로 처리하는 것이 간편하다.int xpos[4] = {1, 0, -1, 0};
int ypos[4] = {0, 1, 0, -1};
//
void paint(int sr, int sc){
 res[sr][sc]=targetColor;
...
 for(int i = 0; i < 4; i++) {
     int new_r = sr + ypos[i];
     int new_c = sc + xpos[i];
     if(new_r < imgSize && new_r >= 0 && new_c < imgColSize && new_c >= 0 && res[new_r][new_c]==originColor) paint(new_r, new_c);
 }
}

stackOverflow 및 불필요한 호출을 피하기 위해 한 번 방문한 grid는 다시 방문하지 않는다.int xpos[4] = {1, 0, -1, 0};
int ypos[4] = {0, 1, 0, -1};
//
void paint(int sr, int sc){
 res[sr][sc]=targetColor;
 visited[sr][sc]=1; // visited 배열은 0으로 초기화 된 상태, 방문한 경우 1로 체크 
 for(int i = 0; i < 4; i++) {
     int new_r = sr + ypos[i];
     int new_c = sc + xpos[i];
     if(new_r < imgSize && new_r >= 0 && new_c < imgColSize && new_c >= 0 && !visited[new_r][new_c] && res[new_r][new_c]==originColor) paint(new_r, new_c); // visited 조건 추가
 }
}


Solution
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

#include 

int imgSize;
int imgColSize;
int targetColor;
int originColor;
int** res;
int** visited;

int xpos[4] = {1, 0, -1, 0};
int ypos[4] = {0, 1, 0, -1};

void paint(int sr, int sc){
    res[sr][sc]=targetColor;
    visited[sr][sc]=1;
    for(int i = 0; i < 4; i++) {
        int new_r = sr + ypos[i];
        int new_c = sc + xpos[i];
        if(new_r < imgSize && new_r >= 0 && new_c < imgColSize && new_c >= 0 && !visited[new_r][new_c] && res[new_r][new_c]==originColor) paint(new_r, new_c);
    }
}

int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int color, int* returnSize, int** returnColumnSizes) {
    imgSize=imageSize;
    imgColSize=*imageColSize;
    targetColor=color;
    originColor=image[sr][sc];

    *returnSize=imageSize;
    *returnColumnSizes=(int*)malloc(sizeof(int)*imageSize);
    for (int i=0;i

Time Complexity
visited 여부와 color에 따라 그때그때 함수 호출횟수가 변경되서 정확한 시간복잡도 계산은 해내지 못했다. 매우 Rough하게 매번 상하좌우를 체크하므로 $O(4^n)$
지적 및 질문 환영