https://leetcode.com/problems/maximal-square/description/?envType=problem-list-v2&envId=array Maximal Square - LeetCodeCan you solve this real interview question? Maximal Square - Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. Example 1: [https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg]leetcode.com Description:..
https://leetcode.com/problems/gas-station/?envType=problem-list-v2&envId=dglcn6pr Gas Station - LeetCodeCan you solve this real interview question? Gas Station - There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith stleetcode.com Description:There are n g..
https://leetcode.com/problems/word-break/description/?envType=problem-list-v2&envId=array Word Break - LeetCodeCan you solve this real interview question? Word Break - Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary mayleetcode.com Source Codeclass S..
두 수 XOR 합과 유사한 문제이다. 숫자를 이진수로 변경하여 트라이에 넣어주고, 숫자 중 i번째까지 XOR한 값을 prefix에 저장해서 답을 구한다. 같은 수를 XOR 연산하면 항상 0이 된다. 따라서 S[i] = A[1] ~ A[i]를 XOR 연산한 결과라고 한다면, A[i] ~ A[j]까지 XOR 연산한 결과를 S[j] - S[i - 1] 이라고 할 수 있다. 따라서 수를 트라이에 넣으면서 연산을 누적해나가며 S[i]와 S[j]를 XOR한 값이 가장 큰 것으로 찾는 것으로 변형할 수 있다. #include #include using namespace std; struct Node { int children[2]; bool valid; Node() { children[0] = children[1] ..
👻 문제 설명 BFS문제이지만, 인접한 칸으로 이동하는 기존 문제와 다르게 90도로 이동해야 하는 점 + 거울을 설치할 수 있는 곳까지 연속으로 쭉 이동해야하는 점이 달랐습니다. 이 점을 유의해서 BFS 코드를 조금 고쳐서 풀어보았습니다 : ) 😔 해결 과정 편의 상, 시작점 (#)에서 도착점(#) 까지 '빛이 이동한다'라고 표현하겠습니다. BFS를 수행하는 목적은, 빛이 시작점에서 도착점까지 이동하였을 때 '거울이 최소 몇 번 사용되느냐' 입니다. 이 말은 즉, '빛이 최소 몇 번 꺾이느냐'를 의미합니다. 따라서 거울을 놓을 수 있는 모든 위치에 대해서, 빛이 꺾일 수 있는 다음 위치를 모두 찾아 이동하는 것을 시뮬레이션하고 도착점(#)에 도달하였을 때 사용한 거울의 최솟값을 구하면 됩니다. 이 때 유..
🥲 문제 설명 https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net 🐹 문제 해설 이 문제는 아래 두 가지로 나뉜다. (1) 돌을 2개 놓는 부분 (경우의 수 : 400 * 400 = 160,000) (2) 죽일 수 있는 상대 돌의 개수를 구하는 부분 (경우의 수 : (400 * 400) ^ 3 = 64000000) 방문하지 않은 돌을 찾는다. 그 돌에 속한 그룹을 찾는다. 그룹은 최대 3개씩 속하므로, 4..
https://school.programmers.co.kr/learn/courses/30/lessons/60057# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👻 문제 설명 😔 해결 과정 문자열을 자를 수 있는 단위는 최소 1에서 최대 s의 길이의 절반이다. 모든 경우를 탐색하면서, 문자열 압축을 하였을 때 가장 짧은 길이를 찾는 방식으로 문제를 풀었다. "abcabcabcdede" 의 문자열이 주어졌을 때, x = 3 즉 3개 단위로 자르는 경우를 예제를 들어보겠다. string target = s.substr(i, x); int k = 0; whi..
😙 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/150369# [프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/150369#) 🌸 해결 과정 deliveries와 pickups 배열의 마지막 부분부터 접근하여, cap 만큼의 짐을 배달하고 수거하는 것을 반복하였다. 이 때 무작정 cap 크기의 짐을 실고 가게 되면, 다 배달하지 못하여 돌아올 때 회수할 수 있는 택배의 개수가 줄어들..
🐹 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 😊 해결 과정 1. 주문된 모든 메뉴 조합 orders에 대해서, 코스요리 메뉴로 선정 가능한 후보를 모두 뽑는다. void findCombination(string order, int index, string& result, set& combinations) { if (index == order.size()) { if (result.size() >= 2){ set s; for(ch..
