프로그래머스60 [프로그래머스] 이중우선순위큐 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 이전에 백준에서 풀이한 이중우선순위큐와 동일한 문제로 이번에도 최소힙과 최대힙을 이용하여 풀이하였습니다. 최소힙과 최대힙을 이용하여 입력으로 들어온 숫자들을 두곳에 모두 기록하였습니다. 삭제가 발생하였을때 삭제된 숫자와 해당 숫자가 삭제된 횟수를 딕셔너리에 기록하였습니다. 삭제된 숫자와 삭제된 횟수를 기록한 덕분에 두개의 힙에서 값을 서로 동기화가 가능하였습니다. 2) 알고리즘 최소힙, 최대힙 3) 풀이 코드 사용 언어 - Python import heapq def solution(operations): deleted = {} # 삭제된 숫자들 목록 => 삭제된 숫자 : 삭제된 횟수 min_heap = [] # 최소힙 max_heap = [] # 최대.. 2022. 4. 30. [프로그래머스] 다단계 칫솔 판매 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 수익을 벌어들인 노드(사람)에서 시작하여 부모 노드를 따라 올라가며 수익을 분배하는 문제였습니다. 수익을 벌어들인 노드를 시작으로 하여 최상위 노드까지 DFS 를 이용하여 탐색하였습니다. 2) 알고리즘 DFS 재귀 3) 풀이 코드 사용 언어 - Python import sys sys.setrecursionlimit(10000) def solution(enroll, referral, seller, amount): enroll_idx = {} # 사람 명단이 주어진 순서대로 출력이 필요하므로 '이름': '번호' 형태의 딕셔너리 필요 result = [0] * len(enroll) # 수익금 정답을 저장할 리스트 def setIdx(): # 사람들 번호를 .. 2022. 4. 27. [프로그래머스] 디스크 컨트롤러 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 작업의 평균 시간을 줄이기 위해서 현재 대기하는 작업들의 개수를 최대한 줄여주어야 합니다. 그래서 최소힙을 이용하여 작업이 시작되는 순서대로 작업을 가져왔습니다. 작업을 처리할 수 있는 경우에 대기 명단에 넣었고, 작업이 빨리 끝나는 순서대로 작업을 완료하였습니다. 2) 알고리즘 최소힙 3) 풀이 코드 사용 언어 - Python import heapq def solution(jobs): N = len(jobs) # 평균을 구하기 위한 작업의 개수 heapq.heapify(jobs) # 작업들을 최소힙으로 만듦 ms = 0 # 현재 작업의 시간 answer = 0 # 순수 작업한 시간 waiting = [] # 작업 대기 명단 while jobs or .. 2022. 4. 26. [프로그래머스] 가장 먼 노드 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 기준 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제였습니다. 다익스트라를 이용하여 가장 멀리 있는 노드의 거리를 구한 이후 해당 거리에 있는 노드의 개수를 확인하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import heapq def solution(n, edge): linked = [[] for _ in range(n+1)] # 노드의 연결 관계 distance = [0] * (n+1) # 노드들의 거리 for a, b in edge: # 노드 연결 관계 정리 (양방향) linked[a].append((1, b)) linked[b].append((1, a)) def dijkstra(start): # 다익스트.. 2022. 4. 25. [프로그래머스] 등굣길 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 2차원 배열의 각 칸별로 도착할 수 있는 경우의 수를 저장하였습니다. 2차원 배열의 누적합을 구하는 방법과 유사하게 접근하였습니다. 2) 알고리즘 DP 누적합 3) 풀이 코드 사용 언어 - Python def solution(m, n, puddles): dp = [[0] * (m+1) for _ in range(n+1)] # 2차원 배열 생성, 누적합과 유사하여 가장 왼쪽 열과 가장 위의 행을 0으로 모두 채움 dp[0][1] = 1 # 출발지 (1, 1) 에 도착 가능한 경우의 수를 1개로 만들기 위함 for i in range(1, n+1): # 2차원 배열 반복 for j in range(1, m+1): if [j ,i] in puddles: #.. 2022. 3. 27. [프로그래머스] 정수삼각형 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 삼각형의 각 층별로 나올 수 있는 최댓값들을 기록하였습니다. 다음 층을 계산할때 이전층의 최댓값에서 현재 더할 수 있는 값들을 더하고 더 큰 값들을 저장하였습니다. 2) 알고리즘 DP 3) 풀이 코드 사용 언어 - Python def solution(triangle): N = len(triangle) # 삼각형의 높이 dp = [] # 삼각형의 높이별 나올 수 있는 값 dp.append(triangle[0]) # 가장 위에층 설정 n = 1 # 현재 높이 while n < N: # 현재 높이가 삼각형의 높이 보다 작으면 반복 tmp = [] # 현재 층의 정답 경우의 수 tmp.append(dp[-1][0] + triangle[n][0]) # 현재 층.. 2022. 3. 26. [프로그래머스] 여행경로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 항공편을 모두 이용하여 이동 가능한 여행경로를 탐색해야 하므로 DFS 탐색을 이용하였습니다. 2) 알고리즘 DFS 재귀 3) 풀이 코드 사용 언어 - Python def solution(tickets: list): answer = [] # 정답 리스트 def make_linked(tickets: list): # 연결 관계 변수 만드는 함수 linked = {} # 연결 관계 visited = {} # 항공편 이용 여부 for a, b in tickets: linked[a] = linked.get(a, []) + [b] # a -> b 연결 추가 visited[a] = visited.get(a, []) + [0] # 항공편 방문여부 0으로 초기화 for.. 2022. 3. 21. [프로그래머스] 네트워크 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 컴퓨터들을 연결하여 네트워크가 만들어지고, 서로 다른 네트워크가 몇개인지 확인이 필요하므로 서로소 집합 알고리즘을 이용하여 네트워크 개수를 확인하였습니다. 2) 알고리즘 서로소 집합 3) 풀이 코드 사용 언어 - Python def solution(n, computers): network = list(range(n)) # 컴퓨터들 서로간 연결 정보 def union(x, y): # 컴퓨터 두대 연결 network[find(y)] = find(x) # 각 연결된 컴퓨터의 대표 컴퓨터를 연결 def find(x): # 해당 컴퓨터 네트워크의 대표 컴퓨터 검색 if x != network[x]: # 현재 컴퓨터가 대표 컴퓨터가 아니라면 network[x] .. 2022. 3. 20. [프로그래머스] 삼각 달팽이 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 2차원 배열에서 대각선으로 반을 채운다고 생각하였습니다. 그리하여 가장 왼쪽위의 좌표에서 시작하여 아래, 오른쪽, 왼쪽위 의 세가지 방향으로만 나아갔습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.setrecursionlimit(10000) dr = [1, 0, -1] # 아래, 오른쪽, 왼쪽위 dc = [0, 1, -1] def solution(n): answer = [] # 정답 리스트 pyramid = [[0] * n for _ in range(n)] # 2차원 배열 direction = 0 # 진행 방향, 초기 아래 방향 def make_py.. 2022. 3. 16. [프로그래머스] 구명보트 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 탑승 가능한 인원이 최대 2명이므로, 무게가 가장 작은 사람과 가장 큰 사람이 함께 탐승하게 하는 방법이 최선의 방법입니다. 2) 알고리즘 탐욕법 3) 풀이 코드 사용 언어 - Python from collections import deque def solution(people, limit): answer = 0 q = deque(sorted(people, reverse=True)) # 사람의 무게를 내림차순으로 정렬 while q: # 사람이 남아있으면 answer += 1 # 보트 한개 추가 if len(q) < 2: # 한명만 남았으면, 혼자 사용 q.pop() elif q[0] + q[-1] 2022. 3. 16. [프로그래머스] 캐시 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 문제에서 제시한 LRU 알고리즘을 이용하여 풀이하였습니다. 2) 알고리즘 LRU (Least Recently Used) 3) 풀이 코드 사용 언어 - Python from collections import deque def solution(cacheSize, cities): answer = 0 # 정답 변수 q = deque() # 캐시 공간 if not cacheSize: # 캐시 사이즈가 0인 경우, 입력마다 항상 5초가 소요 됨 return len(cities) * 5 for city in cities: city = str(city).lower() # 대소문자 구분을 안함 if city not in q: # 현재 도시가 캐시 공간에 저장되어 있지.. 2022. 3. 15. [프로그래머스] 양궁대회 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 재귀로 높은 점수부터 시작하여 탐색하였습니다. 각 점수는 이길때는 딱 한발만 더 쏘도록 하였고, 질때는 한발도 쏘지 않도록 하였습니다. 2) 알고리즘 재귀 3) 풀이 코드 사용 언어 - Python def solution(n, info): answer = [] # 점수 받는 정답 리스트 max_difference = 0 # 가장 많이 차이 나는 점수차 def sol(idx, remain, apeach, ryan, ans): # 인덱스, 남은 화살 수, 어피치 점수, 라이언 점수, 점수별 라이언이 쏜 화살 수 nonlocal answer, max_difference if idx > 10 and remain >= 0: # 모두 반복했고, 화살이 남거나 다.. 2022. 3. 14. 이전 1 2 3 4 5 다음
