Python50 [프로그래머스] 기지국 설치 / level 3 / 파이썬 / python 💡 solutions 💬 문제에서 구해야 하는 답은 '증성해야 할 기지국 개수의 최솟값'이다. 따라서 이를 구하기 위해서는 설치된 기지국으로부터 전파가 전달되지 않는 아파트들을 먼저 찾아야 한다. 💬 설치된 기지국 리스트를 가지고 순차적으로 탐색한다. start, end값을 갱신하며 전파가 전달되지 않는 아파트의 개수(before)를 구간별로 찾는다. 💬 spread는 기지국 하나를 설치하면 결과적으로 전파를 전달 받는 아파트의 개수이다. (기지국의 위치 또한 포함) 예를 들어 w가 2이면 총 5개의 아파트가 전파를 전달 받을 수 있다. 💬 한 구간에서 전파가 전달되지 않은 아파트들의 개수를 spread로 나눈 몫을 올림한 값이 바로 증설해야 할 기지국 개수이다. 모든 구간을 탐색하여 증설해야 할 기지국.. 2022. 4. 16. [프로그래머스] 가장 먼 노드 / 파이썬 / python / BFS 💡 solutions 💬 최단 거리 로직을 위해 BFS 알고리즘으로 구현한다. -> deque 자료구조 사용 💬 visit 배열을 가지고 방문했는지 확인함과 동시에 1부터 해당 노드까지의 거리를 저장한다. 👨💻 code from collections import deque def solution(n, edge): adj = [[] for _ in range(n+1)] visit = [0] * (n+1) for a, b in edge: adj[a].append(b) adj[b].append(a) visit[1] = 1 q = deque([1]) while q: x = q.popleft() for next in adj[x]: if not visit[next]: visit[next] = visit[x] + .. 2021. 12. 27. [프로그래머스] 야근 지수 / 파이썬 / Python / heap 💡 solutions 💬 야근 피로도를 최소한으로 만들기 위해서는 주어진 N시간 동안 works 리스트 안의 작업량 요소들을 가장 큰 값부터 -1씩 줄여나가는 과정이 필요하다. 💬 works와 n의 크기를 고려했을 때, 효율성을 통과하기 위해서는 값을 비교하는 로직을 위해 heaq 자료 구조를 사용해야 한다. 💬 주어진 예제 중에 3번과 같이 주어진 N시간 동안에 모든 작업량을 모두 끝마칠 수 있는 경우에는 0을 바로 리턴할 수 있도록 조건을 추가해야 한다. 👨💻 code import heapq def solution(n, works): answer = 0 if sum(works) 2021. 12. 26. [백준] 케빈 베이컨의 6단계 법칙 / 파이썬 / python / BFS 알고리즘 💡solutions ) 💬 처음 adj라는 인접행렬을 만들어 각 유저 간의 연결 상태를 나타내고 -> 덱 자료구조를 사용해서 BFS 알고리즘으로 구현하면 문제를 쉽게 해결할 수 있다. 💬 첫 시도에서 스택 자료구조를 사용해서 DFS 알고리즘 구조로 풀었더니 채점결과 실패했다. 이유는 해당 문제에선 출발지에서 각 노드까지의 최단 거리를 찾는 개념이기 때문에 DFS로 찾게 되면 최단 거리가 아닐 수 있기 때문이다. BFS와 DFS로 거리 구할 때의 차이 해당 문제에서 테스트케이스가 아래처럼 주어지는 경우 DFS로 거리를 찾는다면 ->1에서 2까지의 거리가 1, 3까지의 거리가 2가 나온다. 이와 비교하여 BFS에서는 1에서 2까지 그리고 1에서 3까지 모두 거리가 1이 나오므로 최단거리가 된다. 3 3 1 .. 2021. 11. 5. [프로그래머스] 디스크 컨트롤러 / 파이썬 / Python / heapq 사용 💡solutions ) 💬 참고 : 디스크 컨트롤러 문제에서 요구하는 작업 처리 방식은 FIFO(First In First Out)가 아니라 SJF(Shortes Job First)방식이다. 즉, 요청된 작업들 중 가장 짧은 작업시간을 요구하는 작업부터 우선적으로 처리하는 방식이다. -> 이런 방식으로 진행하면 각각의 요청된 작업들의 대기 시간을 줄일 수 있다는 장점이 있다. (비선점형 스케줄링 방식에서 평균 대기 시간이 가장 짧다) 💬 heapq 모듈을 통해 최소 힙 사용하였음 -> heap에 작업의 소요시간, 작업이 요청되는 시점 순서로 값을 넣으면 (이번 예제에선 heap = [[3, 0], [6, 2], [9, 1]] 순으로 들어가는 셈) -> heappop할 때 작업의 소요시간을 기준으로 가장 .. 2021. 10. 29. [백준] 20055번 / 컨베이어 벨트 위의 로봇 / 파이썬 / Python 💡solutions ) 💬 시뮬레이션 유형으로 문제에서 주어진 조건들을 차례대로 구현하면 되는 문제 💬 deque 자료형과 rotate() 메소드 사용하여 컨베이어가 한칸씩 이동하는 것을 나타냄 👨💻code ) import sys from collections import deque input = sys.stdin.readline n, k = map(int, input().split()) conveyor_belt = deque(list(map(int, input().split()))) robot = deque([0]*n) answer = 0 while True: robot.rotate(1) conveyor_belt.rotate(1) robot[-1] = 0 for i in range(n-2, -1, -.. 2021. 10. 23. 이전 1 2 3 4 ··· 9 다음
