Ustory

Problemhttps://leetcode.com/problems/partition-array-for-maximum-sum/ Sol주어진 배열 arr를 최대 길이 'k'인 연속된 배열로 분할하고, 각 부분 배열의 모든 값을 그 부분 배열의 최대값으로 바꾼 후 배열의 합을 최대값을 구하는 문제 (변경된 배열의 최대합 구하기!)  해결 방법👀 작은 부분 문제를 해결하고 전체 문제를 해결하는 DP(Dynamic Programming)을 사용하였습니다. tab라는 저장 배열을 만들어주고 결과를 저장하며 업데이트하는 방식으로 구현했습니다.Bottom-UP1. tab : 배열 arr의 최대합을 저장하는 배열으로, 0으로 초기화2. 외부 반복문(i) : 1부터 n까지  - i : 배열 arr의 인덱스, tab[i]..

Problemhttps://leetcode.com/problems/count-sorted-vowel-strings/ Sol모음 (a, e, i, o, u)를 가지고 길이가 n인 사전순으로 정렬된 모음 문자열의 개수를 계산하는 문제 해결 방법 1: Combination👀  오늘은 문제를 보자마자 중복조합으로 풀어야겠다고 생각해서 math.comb을 사용해서 해결했습니다. 1. 중복 조합 : [식1] 선택할 수 있는 항목이 r개 일때, 중복을 허용하여 n개를 선택하는 경우의 수  ❓ 각 위치마다 모음을 중복하여 선택 가능(aa, oo, .. 가능) ❓문제 예시에서 'ae'가 나왔으면 'ea'는 같다고 취급함을 알려줍니다.2. 식 표현 : [식2] 이 문제에서는 입력으로 주어지는 길이 n, 모음 5개를 선택..

Problemhttps://leetcode.com/problems/all-possible-full-binary-trees/ Soln개의 노드를 가지는 가능한 모든 완전 이진트리(Full Binary Tree)를 생성하는 문제 Dynamic Programming 동적 프로그래밍동적 프로그래밍 DP == 동적 계획법문제를 작은 하위 문제로 나누고결과 저장➡ 동일 하위 문제에 대한 중복 계산 피하기중복되는 하위 문제큰 문제를 해결하기 위해 동일한 하위 문제를 여러번 해결해야 하는 경우, 중복되는 계산을 피하기 위해 사용문제의 최적 해결 방법이 그 하위 문제들의 최적 해결 방법으로 구성될 수 있는 경우Memoization이미 계산한 하위 문제의 결과를 저장해두고 필요할 때마다 결과를 사용하는 방식주로 재귀를 사..

Problemhttps://leetcode.com/problems/container-with-most-water/ Sol가장 많은 물을 담을 수 있는 컨테이너를 만들고 그 양을 찾는 문제 Greedy Algorithm ? Two-pointer ? two-pointer 접근법포인터를 배열의 처음과 끝에 둡니다.포인터가 양끝에서 시작하여 중앙으로 이동하면서 현재 가능한 최대 면적을 유지합니다.현재 가능한 최대 면적을 유지한다는 점에서 탐욕스러운 greedy algorithm 중 하나로 불리는 것 같습니다. 해결 방법👀 컨테이너의 너비를 최대로 시작하여 점점 좁히는 형식으로 접근하였습니다. 1. 시작과 끝에서 점점 좁히기 : 시작점에 left 포인터, 끝 점에 right 포인터 설정2. 면적 구하기 : ri..

Problemhttps://leetcode.com/problems/split-a-string-in-balanced-strings/  Sol문자열 내 L과 R의 균형을 이루는 문자열의 개수를 카운트하는 문제  Greedy Algorithm 🌱 참고이전 글에 탐욕 알고리즘을 정리해두었습니다. [99클럽 코테 스터디 17일차 TIL] 프로그래머스 | Greedy 구명보트Problem 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr Soluknow-ujum.tistory.com  해결 방법 👀 시소처럼 생각해서 L이라면 balance+=1, R이라면 balance..

Problem 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr Sollimit가 있는 보트에 최대 2명까지 태울때, 주어진 people을 모두 태우기 위해 필요한 최소한의 보트 수를 구하는 문제 Greedy Algorithm  전역적 최적해를 찾기 위해 각 단계에서 최선의 지역적 선택을 하는 알고리즘현재 상황에서 가장 최선의 선택을 반복적으로 하는 방식각 단계에서의 가장 좋은 선택 ➡ 전체 문제의 최적 해 탐욕 선택 속성 Greedy Choice Property미래 결과를 고려하지 않고 현재 이용 가능한 정보를 기반으로 결정 == 항상 가장 최적이 아닐수도!최..

Problemhttps://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  Sol상하좌우 조이스틱을 움직여서 주어진 알파벳 이름을 완성하기 위해 필요한 최소한의 조작 횟수를 구하는 문제위, 아래로 움직여서 알파벳을 변경하고, 좌, 우로 커서를 이동하여 완성 Greedy Algorithm      ✔ Answerdef solution(name): # 알파벳 리스트 alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' n = le..

Problemhttps://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/ Sol 완전 이진 트리(perfect binary tree) 의 홀수 레벨에 있는 노드의 값을 reverse하는 문제 👀 Perfect Binary Tree  " 모든 레벨이 꽉 차 있는 트리" 문제에서 주어진 완전 이진 트리는 모든 레벨의 노드가 꽉 차있는 Perfect한 트리였다. Full Binary Tree에서  + 모든 leaf node의  depth까지 같은 트리임을 말한다.문제에도 잘 설명이 되어 있어서 몰라도 풀이에 어려움은 없었다.  enumeratePython 내장 함수로, iterable(반복 가능한) 객체를 인덱스와 함께 순회할 수 ..

Problemhttps://leetcode.com/problems/all-paths-from-source-to-target/description/ Sol0부터 n-1번 노드까지 갈 수 있는 모든 경로를 알려주는 문제(Source ➡️ Target)✔ Answer[DFS] 모든 경로를 탐색해야하기 때문에 stack과 회귀를 사용하는 DFS 방식으로 문제를 해결했습니다. class Solution: def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: def dfs(node, path): # 목표 노드(n-1)도착하면 경로를 결과 리스트에 추가 if node == len(graph) - 1: result.append(path) ..

Problemhttps://leetcode.com/problems/deepest-leaves-sum/description/ Sol트리 가장 깊은 depth의 leaf node의 값을 더해주면 되는 문제✔ Answer[DFS]문제를 보고 노드의 수를 통해 트리의 깊이인 h를 구하고 해당 h에 해당하는  node들을 더하려고 DFS 관점에서 접근해보았습니다. 더 효율적으로 풀 수 있을 것 같습니다..# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.ri..