레벨업 일지

문제 https://leetcode.com/problems/range-sum-query-mutable/ Range Sum Query - Mutable - LeetCode Can you solve this real interview question? Range Sum Query - Mutable - Given an integer array nums, handle multiple queries of the following types: 1. Update the value of an element in nums. 2. Calculate the sum of the elements of nums between indices lef leetcode.com 알아야 할 개념 세그먼트 트리 풀이 풀이 알고리즘은 다음과 ..

문제 https://leetcode.com/problems/maximum-width-of-binary-tree/description/ Maximum Width of Binary Tree - LeetCode Can you solve this real interview question? Maximum Width of Binary Tree - Given the root of a binary tree, return the maximum width of the given tree. The maximum width of a tree is the maximum width among all levels. The width of one level is defined as leetcode.com 알아야 할 개념 BFS 탐..

문제 https://leetcode.com/problems/validate-stack-sequences/description/ Validate Stack Sequences - LeetCode Can you solve this real interview question? Validate Stack Sequences - Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack leetcode.com 스택의 push , pop 연산이 주어..

문제 https://leetcode.com/problems/most-frequent-subtree-sum/description/ Most Frequent Subtree Sum - LeetCode Can you solve this real interview question? Most Frequent Subtree Sum - Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order. The subtree sum of a node is de leetcode.com 가장 많은 Subtree Sum 빈..

https://zero-base.co.kr/event/BE_promotion_cordingtest2303 백엔드 스쿨 미니 코딩테스트 대회 | zero-base 코딩테스트 한 문제 풀면 에어팟 맥스 당첨 기회가! zero-base.co.kr 문제 개수는 한 문제였다. 난이도는 골드 4 로 완전탐색 구현 하는 문제였다. 대회는 5등으로 수상했다. 1년 전만 해도 백준 브론즈 구현도 어려워 했는데 , 알고리즘 문제 풀이를 꾸준히 하여 대회 수상도 하고 짧은 시간에 알고리즘 풀이 실력이 많이 늘어서 좋았다. 앞으로도 블로그에 문제 풀이 포스팅을 계속 해야겠다고 다짐한 수요일 저녁이다. 문제 https://www.acmicpc.net/problem/27958 27958번: 사격 연습 N×N 크기의 보드 판이 존..

문제 https://leetcode.com/problems/removing-stars-from-a-string/description/ Removing Stars From a String - LeetCode Can you solve this real interview question? Removing Stars From a String - You are given a string s, which contains stars *. In one operation, you can: * Choose a star in s. * Remove the closest non-star character to its left, as well as remove the star it leetcode.com 알아야 할 개념 Stri..

문제 https://leetcode.com/problems/edit-distance/submissions/931398157/ 알아야 할 개념 다이나믹 프로그래밍 풀이 문제에서 문자를 삭제, 추가, 교체 하는 작업을 하나의 단위로 주어졌다. 풀이는 다음과 같다. 주어진 문자열 2개를 문자 배열로 만든다. 선형 탐색으로 0행과 0열을 초기화 한다. 2중 for문을 돌면서 다음을 수행한다. 문자열 1 의 i 번째 문자와, 문자열 2 의 j번째 문자가 같으면 [i-1][j-1] 의 값을 가져온다. 다르면, 현재 위치 (i 행 j 열) 에서 [i-1][j] , [i-1][j-1] , [i][j-1] 3개의 값의 최솟값에 1 을 더한 값을 할당한다. 정답을 리턴한다. 문자열 연산 수의 최솟값 구하기 는 잘 알려진 ..

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알아야 할 개념 Dynamic Programming 풀이 나이브하게 모든 경우를 완전탐색한다고 하면, 경우의 수는 3^N 이다. 점화식을 사용해 최적화를 한다. 구하고 싶은 단계가 k 라면, k-1 번째에 빨강, 파랑, 초록 으로 칠했을 때 최솟값을 안다면 k번째에 최솟값을 쉽게 구할수 있다. 풀이 알고리즘은 다음과 같다. 주어진 입력을 2차원 배열 map 에 저장한다...