레벨업 일지

문제 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://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 에 저장한다...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/172927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 잘 읽자 ! 처음에 아래 조건들을 하나같이 반대로 이해해서 잘못 구현했다. 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다 .한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다. 광물은 주어진 순서대로만 캘 수 있습니다. 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다. 완전 탐색으로 구현했다. 이유는 조건의 길이들이..

문제 3Sum - LeetCode 3Sum - LeetCode Can you solve this real interview question? 3Sum - Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain du leetcode.com 알아야 할 개념 투포인터 풀이 3가지의 합이 0 이되는 것을 찾는 문제. 접근법은 투포인터를 사용하여 문제 풀이 하였다. 풀이 알고리즘은 다음과 같다. 주어진 배열을 ..

문제 https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/description/ Count Unreachable Pairs of Nodes in an Undirected Graph - LeetCode Can you solve this real interview question? Count Unreachable Pairs of Nodes in an Undirected Graph - You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer arr..