빵똥

오늘의 과제리트코드 Medeum으로 분류된 Partition Array for Maximum Sum입니다. 문제의 유형은 어제에 이어 DP(Dynamic Programing)입니다.문제https://leetcode.com/problems/partition-array-for-maximum-sum/description/  먼저 문제 요구사항 요약입니다. 정수 배열 arr과 정수 k가 주어질 때 arr을 최대 k 길이의 하위 배열로 분할 후각 하위 배열에서 가장 큰 숫자만 남긴 후 더한 값 중 최대값을 반환하면 됩니다. 먼저 초기식을 구해봅니다. dp[i]가 있을 때 안에 들어갈 값은 처음 값부터 i까지의 숫자를 돌렸을 때의 최대합을 저장합니다. 즉, dp[0]일 때에는 숫자가 하나만 있으니 해당 숫자 자체가..

오늘의 과제리트코드 Medeum으로 분류된 Count Sorted Vowel Strings입니다. 문제의 유형은 어제에 이어 DP(Dynamic Programing)입니다.문제https://leetcode.com/problems/count-sorted-vowel-strings/description/  먼저 문제 요구사항 요약입니다. n이 주어질 때 모음으로만 구성되고 사전순으로 정렬된 문자열의 개수를 반환하면 됩니다. DP 문제에서는 이전 값을 이용할 수 있는 점화식을 찾아내는게 전부입니다. 아직 다른 방법은 모르고 메모지나 노트패드를 실행시켜 최소 n이 3일 때 까지 직접 구해봅니다.(사실 이해를 못하거나 특수한 문제일 경우 패턴을 좀 더 쉽게 찾기위해 n을 그 이상까지 구하기도 합니다) 문제에서 알려..

오늘의 과제리트코드 Medeum으로 분류된 All Possible Full Binary Trees입니다. 처음으로 등장한 유형인 DP(Dynamic Programing)입니다.문제https://leetcode.com/problems/all-possible-full-binary-trees/description/  먼저 문제 요구사항 요약입니다. n이 주어질 때 말단 노드를 제외한 모든 노드가 양쪽 노드를 갖고 있는완전 이진 트리를 만들어 List에 담아 반환하면 됩니다. 문제의 유형처럼 DP를 활용하는 문제로 이전 결과값을 캐싱해이후 계산에 사용하는 방식입니다. 완전 이진트리 여부를 확인하는 방법은 여러가지가 있겠지만이전에 lt, rt를 활용한 이분탐색과 비슷하게 트리를 반으로 나누어 진행했습니다. 즉, ..

오늘의 과제프로그래머스 Lv.2로 분류된 구명보트입니다. 이번 문제 유형은 어제에 이어 순차적으로 최선의 선택을 이어나가는 탐욕법(Greedy)입니다.문제https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  먼저 문제 요구사항 요약입니다. 각 사람의 무게와 구명 보트의 한계 중량이 주어집니다. 최대한 잘 분배하여 최소한의 구명 보트로 모든 사람을 구하는 문제입니다. 그리디라는 문제 분류에 걸맞게 계산하기 쉬운 무거운 사람들부터 구명 보트에 태웠습니다...

오늘의 과제프로그래머스 Lv.2로 분류된 조이스틱입니다. 이번 문제 유형은 순차적으로 최선의 선택을 이어나가는 탐욕법(Greedy)입니다.문제https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  먼저 문제 요구사항 요약입니다. 글자의 길이와 똑같은 길이로 A로 초기화 되어 있는 문자열이 있다고 가정하고주어진 글자로 바꾸는 최소한의 조작 수를 구하면 됩니다. 문자를 바꿀 때에는 위, 아래로 조작할 수 있고 만약 A,Z와 같이 알파벳의 끝이라면 A => ..

오늘의 과제리트코드 Medium으로 분류된 Reverse Odd Levels of Binary Tree입니다. 어제에 이어 문제의 유형은 깊이/너비 우선 탐색(DFS/BFS) 입니다.문제https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/ 먼저 문제 요구사항 요약입니다. 완전한 이진트리(완전 이진트리 아님)가 주어질 때, 홀수 레벨에 있는 노드들의값을 역순으로 바꿔 반환하면 됩니다. 기존 DFS처럼 끝까지 순회하되, 홀수 레벨인지 판별만 해주면 됩니다. 사실 값을 서로 바꾸기위해 이전 노드의 값만 기억할 뿐홀수 여부 체크하는 로직 외에 특별한 코드는 없습니다. 단순히 DFS 순회할 때 이전 노드의 Left, Right 값..

오늘의 과제리트코드 Medium으로 분류된 All Paths From Source to Target입니다. 어제에 이어 문제의 유형은 깊이/너비 우선 탐색(DFS/BFS) 입니다.문제https://leetcode.com/problems/all-paths-from-source-to-target/description/ 먼저 문제 요구사항 요약입니다. 입력으로 방향성 비순환 그래프가 주어지면 0번 노드에서 n-1 노드까지 이동할 수 있는모든 경로를 반환하면 됩니다. 0번부터 n-1번까지의 경로만 탐색하면 되니 DFS를 이용하여 풀었습니다. 이전까지의 DFS 문제 풀이와 같은 방식으로 진행해주면 됩니다. 대략적인 문제 풀이 방식입니다. 1. 현재 방문 경로 추가2. 현재 노드에서 갈 수 있는 노드 탐색3. 재귀..

오늘의 과제리트코드 Medium으로 분류된 Deepest Leaves Sum입니다. 어제에 이어 문제의 유형은 깊이/너비 우선 탐색(DFS/BFS) 입니다.문제https://leetcode.com/problems/deepest-leaves-sum/description/ 먼저 문제 요구사항 요약입니다. 입력으로 아래와 같은 TreeNode 객체가 주어집니다./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * Tre..

오늘의 과제프로그래머스 Lv.2에 정렬로 분류된 게임 맵 최단거리입니다. 어제에 이어 문제의 유형은 깊이/너비 우선 탐색(DFS/BFS) 입니다.문제https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  먼저 문제 요구사항 요약입니다. 0과 1로 이루어진 2차원 배열이 주어집니다. 0은 벽이 있어 이동할 수 없는 자리이고, 1은 벽이 없어 이동할 수 있는 자리입니다. 게임 캐릭터의 시작점은 (0, 0) 고정이고, 도착지 또한 (n, m) 고정입니다. 이동..

오늘의 과제프로그래머스 Lv.2에 정렬로 분류된 타겟 넘버입니다. 어제에 이어 문제의 유형은 깊이/너비 우선 탐색(DFS/BFS) 입니다.문제https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  먼저 문제 요구사항 요약입니다. n개의 음이 아닌 정수들이 주어질 때, 이 수들을 적절히 더하거나 빼서 타겟 넘버를 만들 수 있는경우의 수를 return 해주면 됩니다. 문제의 주제처럼 어제 활용한 DFS를 활용하면 되는데 간단하게 설명하면주어진 배열을 탐색하..