나의 개발일지

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/142085🔑 우선순위 큐 (hqepq)먼저 무적권 횟수만큼 라운드를 클리어하고 큐에 적 정보를 저장한다. (heappush)무적권을 다 사용했으면 클리어 한 라운드 중 가장 적이 적었던 라운드를 무적권이 아닌 병사로 처리한다. (heappop)병사로 처리했으므로 무적권을 다시 사용할 수 있음위 방법으로 무적권을 효율적으로 사용해서 라운드를 최대한 클리어할 수 있다. from heapq import heappush, heappopdef solution(n, k, enemy): answer = 0 hq = [] for i in range(len(enemy)): ..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12905🔑 다이나믹 프로그래밍 (DP)점화식 : dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1board[i-1][j-1] == 1일 때 dp배열의 왼쪽, 위, 왼쪽 위 중 최솟값 + 1을 dp[i][j]에 기록한다.board리스트(위) dp리스트(밑) 결과 def solution(board): answer = 0 dp = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)] for i in range(1, len(board) + 1): for j i..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/159993🔑 두 번의 BFS시작 위치에서 레버까지 BFS레버 위치에서 탈출 위치까지 BFS하나의 BFS 함수에 레버 여부를 매개변수로 두고 레버를 찾는지, 탈출구를 찾는지 구분레버를 못 찾거나, 탈출구를 못 찾으면 -1을 리턴 from collections import dequedef solution(maps): answer = 0 def bfs(start, lever): visit = [[0] * len(maps[0]) for _ in range(len(maps))] dx, dy = [0, 0, 1, -1], [1, -1, 0, 0] ..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42861 🔑 프림 알고리즘 출발 위치는 상관없음 현재 섬에서 갈 수 있는 섬들을 큐에 넣고 비용이 가장 적은 길을 뽑아내 섬을 연결하는 방식 큐를 힙으로 구현했기 때문에 항상 최소 비용의 길을 뽑아내서 이동함 최소 비용의 길을 뽑아서 갔으면 또 갈 필요가 없기 때문에 방문 리스트를 통해 못 가게 막음 from collections import defaultdict from heapq import heappush, heappop def solution(n, costs): answer = 0 graph = defaultdict(list) for cost in costs: graph[cost[0]..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/154540 🔑 BFS로 연결된 무인도를 탐색 maps를 순회하면서 무인도를 만나면('X'가 아닌 부분) 현재 위치에서 BFS 탐색을 실시 BFS를 시작하는 위치와 연결된 무인도들을 모두 탐색하면서 식량 개수를 카운트하고 'X'로 바꾼다. BFS 종료 시 식량 개수를 리턴 또 maps를 순회하면서 무인도를 찾고 BFS 탐색 반복 from collections import deque def solution(maps): def bfs(x, y): mx, my = [0, 0, 1, -1], [1, -1, 0, 0] q = deque([(x, y)]) food = int(maps[x][y]) maps..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/77885 🔑 2진수로 변환해서 자리 바꾸기 짝수라면 그 숫자에 +1을 해서 정답에 추가한다. 홀수라면 숫자를 2진수로 바꾸고 50자리까지 남는 자리에 0을 채워준다. (10^15를 2진수로 바꾸면 50자리까지 나와서) 변환된 2진수를 역순으로 순회하면서 처음 0을 만나면 1로 바꿔주고, 바로 오른쪽 값은 0으로 바꿔준다. 7 일 때 2진수로 바꾸면 000...0111 처음 0으로 만났을 때 값을 바꿔주면 000...1011 이렇게 자리를 바꾼 2진수를 다시 10진수로 변환해서 정답에 추가하면 끝 ✨ def solution(numbers): answer = [] for n in numbers:..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42884 🔑 그리디, 정렬 나간 지점을 기준으로 오름차순 정렬 [[-20, -15], [-14, -5], [-18, -13], [-5, -3]] → [[-20, -15], [-18, -13], [-14, -5], [-5, -3]] 초기값(camera)을 -30000보다 작은 값으로 초기화한다. 현재 차량의 진입 지점이 카메라가 설치된 지점(camera) 보다 크면 나간 지점에 카메라 설치 밑에 그림으로 봤을 때 카메라를 설치한 지점과 겹치지 않는 경우에 해당 그림을 보면 이해하기 쉽다. 빨간 막대가 카메라가 설치된 자리 파란 막대는 차량이 이동한 거리 def solution(routes): ..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12987 🔑 정렬 A의 순서가 어떻든 간에 B의 순서를 내 마음대로 배치할 수 있으니까 둘 다 오름차순으로 정렬을 한다. (A의 순서가 주어진 대로 사용할 필요 없음) A보다 B[i]가 더 크면 정답 올리고 A의 다음 순서를 불러온다. 반복 한 번만 하면 끝 ✨ def solution(A, B): answer = 0 A.sort() B.sort() p = 0 for i in range(len(A)): if A[p] < B[i]: answer += 1 p += 1 return answer