https://www.acmicpc.net/problem/14502 문제설명바이러스의 확산을 막기 위해서 연구소에 벽 세우기벽을 세운 뒤 바이러스가 퍼질 수 없는 안전 영역의 최댓값 구하기   문제해결조건연구소의 크기 : N x M 직사각형 (직사각형은 1 x 1 크기의 정사각형으로 나누어져 있다.)연구소의 구성 : 빈 칸(0), 벽(1), 상하좌우로 퍼지는 바이러스 (2)새로 세울 수 있는 벽은 무조건 3개로직현재 빈 칸들 중 3개를 선택해서 벽 세우기 (조합 이용)바이러스를 퍼뜨리는 역할을 하는 BFS 실행, board 모두를 확인해야 하므로 바깥 for문 필요확산 후 안전영역 개수 세고 최댓값 갱신벽 되돌리기row_len, col_len = map(int, input().split())board =..

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://school.programmers.co.kr/learn/courses/30/lessons/17680 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제설명DB 캐시를 적용할 때 캐시 크기에 따른 실행 시간 측정 프로그램 작성LRU(Least Recently Used) 방법 사용  문제해결현재 값이 캐시 리스트 안에 있으면현재 값 제거 후 맨 끝에 append, 실행시간+1현재 값이 캐시 리스트 안에 없으면꽉 찾으면 : popleft, append, 실행시간 + 5비었으면 : append, 실행시간 + 5def solution(cacheSize, cities): from collecti..

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://school.programmers.co.kr/learn/courses/30/lessons/118670 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr1. 문제설명행렬이 주어질 때 operations (Rotate, ShiftRow)를 순서대로 실행한 후 행렬의 결과 반환 2. 문제해결[첫번째 코드]def solution(rc, operations): from collections import deque new_rc = deque([]) for r in rc: new_rc.append(deque(r)) row_len = len(rc) for op..

https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 문제설명2진 트리 모양 초원에서 각 노드를 돌아다니며 양 모으기각 노드는 양과 늑대로 구성모은 양의 수보다 늑대의 수가 같거나 더 많아지면 모든 양 잡아먹힘중간에 양이 늑대에게 잡아먹히지 않으면서 다시 루트 노드로 돌아올 때, 최대 몇마리의 양을 모을 수 있는지 ? 2. 문제해결edges에서 하나의 edge는 부모-자식 노드의 연결을 의미한다.현재 노드에서 연결된 노드들을 방문할 수 있을 뿐만 아니라 이전 부모노드에 연결된 자식노드에도 방..

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, ‘)’]을..