알고리즘 문제408 [leetcode] 1632. Rank Transform of a Matrix 문제 : https://leetcode.com/problems/rank-transform-of-a-matrix/ m x n 크기의 배열이 있을 때, 이들의 랭크를 매긴 배열을 반환하라. 순위는 1부터 시작하며 두 개의 요소 p, q가 같은 행 혹은 같은 열에 있으면 아래와 같은 규칙에 따라 순위를 매긴다. 1. p q : rank(p) > rank(q) 랭크는 가능한한 작게 매겨져야 한다. 예시 4를 보자. 7 3 6 1 4 5 9 8 2 만약 배열의 모든 수가 유니크한 수를 가진다면 정답을 구하기는 생각보다 간단하다. 요소 값을 기준으로 오름차순 정렬한다. 요소값(x, y) 1 (1,0) -> 2.. 2021. 8. 12. [leetcode] 415. Add Strings 문제 : https://leetcode.com/problems/add-strings/ 가산기 구현 문제. 학창시절에 배운적이 있는데 그때의 기억을 되살려서.. carry 변수를 하나 둔다. 올림되는 수가 있다면 1, 아니면 0일 것이다. 입력 문자열 num1, num2의 인덱스 변수를 ind1, ind2로 두고 해당 변수들은 입력문자열의 가장 뒤의 인덱스를 초기화 값으로 가진다. 덧셈뺄셈을 할 때, 같은 자리수에 있는 수들을 더해야 하기 때문이다. num1[ind1], num2[ind2]를 각각 변수 a, b라 하자. 만일 ind1, ind2가 문자열 num1, num2의 인덱스 범위를 넘어선다면(0 미만) 0으로 본다. 탐색 후 ind1, ind2를 1씩 감소시킨다. a + b + carry 를 나누기.. 2021. 8. 11. [leetcode] 132. Palindrome Partitioning II 문제 : https://leetcode.com/problems/palindrome-partitioning-ii/ 문자열 s가 주어지면 s를 잘라 부분문자열들을 만들었을 때 모든 부분문자열들이 펠린드롬이 되는 최소 절단횟수를 구하여라. 먼저 DP로 2차원 배열을 만들어 펠린드롬[i][e] = 문자열[i,e]가 펠린드롬인지를 구한다. 펠린드롬[i][j] = 펠린드롬[i+1][j-1] (s[i] == s[j]) = false (s[i] != s[j]) 문자열[i~j]은 문자열의 첫문자와 끝 문자가 다르면 false, 첫문자와 끝문자가 같다면 문자열[i+1, e-1]이 펠린드롬인 경우는 펠린드롬, 아니면 펠린드롬이 아니다. 위 점화식으로 펠린드롬 여부를 구하면 이번엔 1차원 배열을 만든다. dp[i] = s[0.. 2021. 8. 7. [leetcode] 429. N-ary Tree Level Order Traversal 문제 : https://leetcode.com/problems/n-ary-tree-level-order-traversal/ 트리가 주어지면, 레벨 순서 순회 결과를 구하여라. 탐색문제. 너비우선탐색으로 구할 수 있다. 큐를 만들고 해당 큐에 루트 노드를 넣는다. 큐를 빌때까지 탐색하면서 새로운 큐에 탐색한 노드들의 자식 노드들을 넣는다. 큐가 빌때까지 탐색한 노드들이 같은 레벨에 있는 노드들이다. 새로운 큐를 만들었으면 해당 큐를 다시 빌때까지 탐색하면서 또다른 큐(다음 레벨의 노드들)를 만드는 과정을 반복한다. 시간복잡도는 O(N). N = 노드 개수. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/429.%20N-ary.. 2021. 8. 7. [Programmers] 타겟 넘버 문제 : https://programmers.co.kr/learn/courses/30/lessons/43165 DFS 방식으로 탐색하면서 모든 인덱스의 숫자들을 더하거나 빼는 경우의 합을 구한다. 모든 numbers 를 탐색했을 때 합이 targetSum과 같다면 정답 +1을 해준다. 시간복잡도는 하나의 인덱스에 더하거나 빼는 경우, 두 번을 탐색하므로 O(2^N). N = |numbers| 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/%ED%83%80%EA%B2%9F%20%EB%84%98%EB%B2%84.cpp 2021. 8. 5. [leetcode] 113. Path Sum II 문제 : https://leetcode.com/problems/path-sum-ii/ 정수로 이루어진 이진트리와 targetSum이 주어질때, 루트에서 리프노드까지 경로의 노드들의 합이 targetSum과 같은 경로들을 구하여라. 백트래킹으로 경로들을 저장하면서 루트에서 리프노드에 도달할 때까지의 경로들의 합을 구한다. 리프노드에 도달했을때 합이 targetSum인 경우 정답 배열에 저장한다. 시간복잡도는 O(N). N = 트리의 노드 개수 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/113.%20Path%20Sum%20II.cpp 2021. 8. 4. 이전 1 ··· 17 18 19 20 21 22 23 ··· 68 다음
