Algorithm (2139) 썸네일형 리스트형 (Python3) - LeetCode (Medium) : 2466. Count Ways To Build Good Strings https://leetcode.com/problems/count-ways-to-build-good-strings dp 문제였습니다.📕 풀이방법📔 입력 및 초기화MOD를 선언 후 10**9 + 7로 초기화합니다.📔 풀이과정어떤 문자열 i길이를 만들기 위해 0을 zero개와 1을 one개를 사용할 때 다음과 같은 점화식을 세울 수 있습니다.$${D[i] = D[i-one] + D[i-zero]}$$ 1. 빈 문자열을 만드는 경우는 1이므로 dp[0]은 1로 초기화하고 1에서 high까지 for loop또는 재귀함수를 수행하며 각자 길이를 만드는 경우의 수를 구해줍니다. 2. low에서 high까지 다시 dp 값을 answer에 누적해 더해준 후 MOD연산을 적용해 갱신합니다.📔 정답 출력 | 반환a.. (Python3) - LeetCode (Hard) : 1639. Number of Ways to Form a Target String Given a Dictionary https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionarytop down dp로 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화MOD, 한 단어의 길이 word_len, target의 길이 target_len, 각 단어의 열별 알파뱃의 빈도수를 저장할 해시맵인 freq_map, j번째 타겟의 문자를 만들기 위해 k번째 열의 word를 선택할 경우 만들 수 있는 문자들의 경우의 수를 의미하는 total_ways를 선언 후 적절히 초기화합니다.📔 풀이과정words의 길이가 모두 같기 때문에 단어들을 선택할 때 열별로 선택여부를 결정할 수 있습니다. words = ["abba", "baab", "abc.. (Python3) - LeetCode (Medium) : 1014. Best Sightseeing Pair.py https://leetcode.com/problems/best-sightseeing-pairheap또는 binary search를 사용해 풀어본 문제였습니다.📕 풀이방법📔 입력 및 초기화values의 길이를 length로 저장, 정렬된 값을 저장할 배열 sorted_values, 정답 변수 max_score를 선언 후 적절히 초기화합니다.📔 풀이과정values의 원소를 순회하며 다음을 진행합니다.values에서 values[i] + i값의 최댓값을 O(logN)만에 찾을 수 있다면 sorted_values의 마지막 원소 + values[j] - j값의 최댓값만 찾는다면 O(NlogN)만에 답을 찾을 수 있습니다. 다음 두 가지 방식을 생각해볼 수 있습니다. 1. sorted_values에 넣을 때.. (Python3) - LeetCode (Medium) : 494. Target Sum https://leetcode.com/problems/target-summemoization을 활용한 dfs문제였습니다.📕 풀이방법📔 입력 및 초기화1. 변수 depth선언 후 nums의 길이를 저장합니다. 2.(각 depth별 만들어진 숫자를 key로), 만드는 경우의 수를 value로 hash map인 memo를 선언 후 빈 객체로 초기화합니다.📔 풀이과정문제는 중복 상태를 메모이제이션으로 방지하며 재귀 호출을 최적화하는 방식으로 해결할 수 있습니다. nums 배열의 길이가 최대 20이며 각 원소는 1000 이하, 합계는 -20,000 ~ 20,000 범위를 가지므로 ${( n \cdot S = 20 \cdot 40,001 \approx 800,000 )}$번의 계산으로 해결 가능합니다.풀이 과.. (Python3) - LeetCode (Medium) : 515. Find Largest Value in Each Tree Row https://leetcode.com/problems/find-largest-value-in-each-tree-rowlevel별 탐색하는 BFS 문제였습니다.📕 풀이방법📔 입력 및 초기화1. 탐색을 진해할 deque변수 dq를 선언 후 root를 넣어줍니다. 2. level별 최댓값을 반환할 max_values를 선언 후 빈 배열로 초기화해줍니다.📔 풀이과정dq에 원소가 존재하는 동안 while loop를 수행하며 다음을 진행합니다.1. 현 dq의 size를 구해줍니다. 이는 즉 자식의 node 개수를 의미합니다. 2. 각 자식들이 가지는 원소들을 비교해 최댓값을 저장할 변수 max_value를 선언해줍니다. 3. size만큼 for loop를 수행하며 자식 노드들의 원소를 비교하며 dq에서 po.. (Python3) - LeetCode (Hard) : 3203. Find Minimum Diameter After Merging Two Trees https://leetcode.com/problems/find-minimum-diameter-after-merging-two-trees트리의 지름을 구하는 문제였습니다.📕 풀이방법📔 입력 및 초기화인접리스트 graph1, graph2를 구해줍니다.📔 풀이과정* 트리의 지름은 bfs를 두 번 수행해 구할 수 있습니다.* n개의 노드에 대해 n-1개의 간선이 보장되므로 노드번호 띄엄띄엄 포함된 간선이 입력으로 들어오는 경우가 없습니다.1. 첫 번째 bfs로 끝 노드를 구한 뒤 해당 노드를 시작점으로 두 번째 bfs를 수행한다면 트리의 지름이 나옵니다. 2. 해당 부분을 bfs_diameter라는 함수를 선언해 bfs를 두 번 수행한 결과로 구한 지름 diameter를 구하고 반환합니다. 3. 트리를 .. (Python3) - LeetCode (Medium) : 2471. Minimum Number of Operations to Sort a Binary Tree by Level https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-levelO(n)으로 사이클을 통한 최소 swap 개수를 구하는 BFS 문제였습니다.📕 풀이방법📔 입력 및 초기화정답 변수 totalSwap과 bfs를 위한 deque dq를 선언 후 적절히 초기화해줍니다.📔 풀이과정1. 트리의 레벨별 bfs를 순회하도록 구현해줍니다. 현재 dq의 길이를 size로 두고 size만큼 dq의 원소를 popleft하며 순회하면 구할 수 있습니다. 이를 values배열에 append해줍니다. 2. 레벨별 values를 인자로 받아 최소 사이클의 개수를 반환하는 함수 minCicle을 구현해줍니다. 해당 함수는 다음과 같이.. (Python3) - LeetCode (Easy) : 1974.minimum-time-to-type-word-using-special-typewriter https://leetcode.com/problems/minimum-time-to-type-word-using-special-typewriter/시계, 반시계 방향을 생각해 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화현재 포인터 piv와 움직임 move를 선언 후 각각 'a', 0으로 초기화합니다.📔 풀이과정word의 원소를 순회하며 다음을 진행합니다.1. 시계방향은 현재 문자를 아스키 코드로 변환한 값에서 piv를 아스키 코드로 변환한 값의 차이입니다. 만약 이 차이가 음수라면 같은 방향으로 진행해야하므로 26을 더해줍니다. 2. 반시계 방향은 반대로 piv - 현재 문자가 됩니다. 만약 이 차이가 음수라면 마찬가지로 26을 더해줍니다. 3. 시계, 반시계방향의 움직임의 최솟값을 move에.. 이전 1 2 3 4 5 6 7 ··· 268 다음