https://leetcode.com/problems/count-the-number-of-complete-components/description/?envType=daily-question&envId=2025-03-22 2685. Count the Number of Complete Components   그래프를 순회하면서, 연결된 그래프인 경우에만 결과값을 더해주는 문제였다.나름 쉽다고 생각해서 접근했지만, 생각보다 벽에 막혔다. 처음에 사이클을 판별하는 DFS를 통해서 문제 접근을 했지만, 3-4나 5와 같은 그래프 형태도 연결된 그래프로 가정했기 때문에 틀렸다. 다른 사람의 풀이를 참고해서야 힌트를 얻을 수 있었는데, 매번 DFS를 순회할 때 마다 각 노드 번호를 리스트에 삽입해준다.예를 들어서 0..

https://www.acmicpc.net/problem/17485 접근법DFS기존에 접근했던 방식은 DFS, 백트래킹을 사용하여 문제를 풀이했다. 하지만, 문제에서 주어진 방향은 3개고, N과 M의 최댓값이 1,000이기 때문에 최악의 케이스엔 3^(1000*1000)이 나오기 때문에 당연히 시간초과가 발생한다. 엠로 코테에서도 3^(200*200)이 나왔기 때문에 시초가 발생할 것이다. DP다른 사람들의 풀이를 보면, DP를 사용하여 풀이하였다.DP[i][j][n]: (i,j)위치에서 n방향으로 도달했을 때의 최소 비용n = 0 (왼쪽 아래 방향)n = 1 (바로 위)n = 2 (오른쪽 아래 방향)  이 그림을 보면, 5로 도달하는데 3가지 케이스가 있음을 알 수 있다.그리고 중요한 조건이 우주선은 ..

https://leetcode.com/problems/most-profitable-path-in-a-tree/description/  문제 이해문제에서 요구하는 바는 이렇다.Alice는 노드 0에서 출발해서, 리프 노드까지 도달한다.Bob은 주어진 노드에서 출발해서, 노드 0까지 도달한다.이 과정 속에서, Alice가 가질 수 있는 최대 보상 값을 구하는 문제였다. 우선, 보상 값을 구할 때 세가지 다른 케이스가 존재했다.Alice가 해당 노드에 먼저 도착한 경우: 해당 보상을 그대로 얻는다.Bob이 먼저 해당 노드에 도착한 경우: 보상을 획득하지 못한다.둘이 동시에 도착한 경우: 현재 보상 / 2를 얻는다.이러한 문제 흐름을 먼저 해결하기 위해선, Bob이 각 노드에 도착하는 시간을 먼저 계산해줘야 했..

https://school.programmers.co.kr/learn/courses/30/lessons/388353 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 설명A 회사의 물류창고에는 알파벳 대문자로 종류를 구분하는 컨테이너가 세로로 n 줄, 가로로 m줄 총 n x m개 놓여 있습니다. 특정 종류 컨테이너의 출고 요청이 들어올 때마다 지게차로 창고에서 접근이 가능한 해당 종류의 컨테이너를 모두 꺼냅니다. 접근이 가능한 컨테이너란 4면 중 적어도 1면이 창고 외부와 연결된 컨테이너를 말합니다.최근 이 물류 창고에서 창고 외부와 연결되지 않은 컨테이너도 꺼낼 수 있도록 크레인을 도입했습니다. 크..

https://leetcode.com/problems/remove-all-occurrences-of-a-substring/description/?envType=daily-question&envId=2025-02-11 Given two strings s and part, perform the following operation on s until all occurrences of the substring part are removed:Find the leftmost occurrence of the substring part and remove it from s.Return s after removing all occurrences of part.A substring is a contiguous sequen..

https://leetcode.com/problems/single-threaded-cpu/

https://leetcode.com/problems/shifting-letters-ii/description/?envType=daily-question&envId=2025-01-05     shift = [0, 0, 0]이 주어질 때, shift[0]과 shift[1]은 시작 인덱스와 끝 인덱스고, shift[2]는 움직이는 방향을 정해준다.1인 경우엔, 'a' -> 'b'와 같이 옮겨주고0인 경우엔 'b' -> 'a'와 같이 뒤로 한칸 이동한다. 이 문제 역시도 constraints 조건으로 인해서 시간복잡도를 O(N^2) 미만으로 줄여야했다. 그래서 이전 문제와 비슷하게 누적합, 차분 배열을 사용한 방식으로 해결했다. 이전 문제와 살짝 다른 부분은 1인 경우엔 시작점++, 끝점-- 라면,0인 경우엔..

We have an array of integers, nums, and an array of requests where requests[i] = [starti, endi]. The ith request asks for the sum of nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi]. Both starti and endi are 0-indexed.Return the maximum total sum of all requests among all permutations of nums.Since the answer may be too large, return it modulo 109 + 7. Example 1:Input: nums = ..

https://leetcode.com/problems/first-completely-painted-row-or-column/description/?envType=daily-question&envId=2025-01-20 You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n].Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i].Return the smallest ind..

79. Word Search https://leetcode.com/problems/word-search/description/?envType=problem-list-v2&envId=backtracking 2차원 배열을 순회하면서 word로 주어진 값을 만들 수 있는지 판단하는 문제였다.현재 좌표에서 동서남북, 4방향으로 이동하는 것도 염두에 둬야 했던 문제였다. 39. Combination Sumhttps://leetcode.com/problems/combination-sum/description/ Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 =..