나의 개발일지

문제 : 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/147354🔑 정렬, 비트연산 XOR먼저 이 문제에서 컬럼이나 튜플의 순서는 0이 아닌 1부터 시작한다.2단계 정렬 : col 번째 값을 기준으로 오름차순, col 번째 값 동일하면 기본키 첫 번째 값 기준 내림차순 정렬음수 기준으로 정렬하면 내림차순 정렬 가능 → -x[0]3단계 나머지들의 합 : 정렬된 리스트 순회하면서 row_begin ~ row_end까지 튜플에 대해 나머지 합 계산 후 리스트에 저장4단계 저장된 나머지 합들 XOR 연산 : 나머지 합 저장된 리스트 순회하면서 모두 XOR 연산answer ^= S[i]로 answer에 XOR 연산된 값 저장 def solution(da..

문제 : 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/42579 🔑 딕셔너리, 힙 music 딕셔너리 "장르" : [(-재생 횟수, 고유 번호), (-재생 횟수, 고유 번호)] value의 리스트는 힙이고 재생 횟수를 음수값으로 넣어 최대 힙 구현 play 딕셔너리 "장르" : 총 재생 횟수 앨범에 먼저 수록할 장르를 구하기 위한 딕셔너리 play 딕셔너리를 총 재생 횟수 기준으로 정렬 1번 조건 : 노래가 많이 재생된 장르를 먼저 수록합니다. 정렬한 play 리스트에서 pop() 2번 조건 : 장르 내에서 많이 재생된 노래를 먼저 수록합니다. music["장르"]에서 heappop() 장르 내에 속한 곡이 1개 일 때 처리를 try-except..

문제 : https://www.acmicpc.net/problem/1765 🔑 union, find 입력으로 친구가 들어오면 서로 union 원수가 들어오면 양방향 그래프로 원수 관계를 생성 생성된 원수 관계 그래프를 이용해 "내 원수의 원수도 내 친구이다." 조건을 해결한다. 나 → 내 원수 → 내 원수의 원수 이렇게 거쳐서 (나, 내 원수의 원수)를 union from collections import defaultdict n = int(input()) m = int(input()) def union(a, b): x = find(a) y = find(b) parent[y] = x def find(x): if parent[x] == x: return x parent[x] = find(parent[x])..