https://leetcode.com/problems/shortest-path-in-binary-matrix/description/ 문제설명nxn으로 구성된 행렬 grid가 주어질 때, (0,0)에서 (n-1,n-1)로 가는 가장 짧은 길의 길이를 구해라. 갈 수 없으면 -1. 0으로 구성된 칸에만 갈 수 있다.  문제해결가장 짧은 길이를 구하는 거니까 BFS 사용방향 주의하자 ! 4방향이 아니라 8방향으로 주어짐현재 위치 뿐만 아니라 현재 길이도 같이 저장하자. 현재 위치가 n-1이면 다온거니까 여기에 저장되어 있던 길이를 반환하면 된다. (BFS를 사용했으므로 가장 먼저 조건에 만족된 값이 가장 짧은 값!)(n-1, n-1) 위치에 도착하지 않았는데 더 이상 갈 곳이 없을 수도 있다. bfs 함수 마..

https://leetcode.com/problems/number-of-islands/description/ 문제설명grid가 땅(1)과 물(0)으로 구성되어 있을 때, 섬(물로 둘러싸져 있고 땅으로 구성된)은 몇 개 만들 수 있는지 ?  문제해결grid 전체를 탐색해봐야 하는데 하나로 연결되어 있지 않을 수 있으니까 전체적인 visit 필요만약 방문하지 않았고 해당 값이 “1”이면 -> bfs/dfs 실행 -> 끝나면 +1개class Solution: def numIslands(self, grid: List[List[str]]) -> int: def dfs(cur_r, cur_c): visit[cur_r][cur_c] = True dr = [0,..

https://leetcode.com/problems/two-sum/description/ 문제설명정수로 구성된 리스트가 주어질 때, 두개의 숫자를 더해 target이 되는 인덱스를 반환  문제해결2중 for문class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)-1): for j in range(i+1, len(nums)): if nums[i]+nums[j] == target: return [i, j]   백트래킹class Solution: def twoSum(self, nu..

https://leetcode.com/problems/coin-change/description/ 1. 문제설명coins에 들어있는 coin을 이용해서 amount 만들 때, 필요한 최소 개수만들 수 없으면 -1를 반환하고 각 coin의 개수는 무한개로 가정 2. 문제해결최소 개수를 구하는 거니까 BFS 이용단, 그냥 BFS로 구현하면 메모리 초과 에러 발생가지를 뻗기 전에 cur_v와 coin을 더한 값을 방문했는지 visit을 통해 확인class Solution: def coinChange(self, coins: List[int], amount: int) -> int: from collections import deque def bfs(): q = d..

https://leetcode.com/problems/is-graph-bipartite/ 1. 문제설명주어진 그래프가 Bipartite인지 아닌지 반환 2. 문제이해하나의 노드가 A라면 엣지로 연결된 노드들이 모두 B이어야 한다.만약 하나의 노드가 B로 저장되어 있고, 이와 연결된 노드도 B로 저장되어 있으면 Bipartite 불가 3-1. 문제해결 (BFS)만약 next_v가 방문처리 되어 있지 않을 경우 connect 확인 connect에 저장되어 있지 않을 경우 : 반대로 저장 (A-B)connect에 저장되어 있을 경우 : 반대로 되어 있는지 확인 (똑같으면 False 반환) 그래프의 노드들이 모두 하나로 연결되어 있지 않고, 여러개의 그래프가 나올 수도 있으니까 전체적인 visit을 만들어서 방..

https://leetcode.com/problems/longest-valid-parentheses/description/ 1. 문제설명“(”와 “)”로 구성된 문자열이 주어질 때, 유효한 괄호 문자열의 가장 긴 길이를 반환 2. 문제해결괄호 짝 맞추기 문제는 stack, 길이를 구하는 문제는 index가 많이 활용되므로 이를 이용해서 해결 시도(인덱스 길이 계산 후 pop) : ‘()(())’에서 길이가 각각 2, 4로 따로 구해져 연속된 부분 반영이 안된다.(pop 후 인덱스 길이 계산) : pop을 먼저 해 준 다음 stack[-1] 부분의 인덱스와 현재 인덱스의 차를 구해주면 연속되는 길이가 자연스럽게 구해진다.단, stack이 비어 있으면 안되니까 맨 처음에 짝이 절대 안맞는 [-1, ‘)’]을..

https://leetcode.com/problems/trapping-rain-water/description/ 1. 문제설명각 높이를 나타내는 지도가 주어졌을 때, 얼만큼 물이 담길 수 있는지 계산 2. 문제해결[stack 이용]class Solution: def trap(self, height: List[int]) -> int: stack = [] water = height.copy() for i, h in enumerate(height): if stack and stack[-1][1] 현재 높이랑 마지막에 저장된 높이랑 비교하는 과정이 필요하므로 stack 이용stack이 들어 있고 현재 높이가 stack의 맨 끝 높이보다 크거나 같으면..