본문 바로가기

Problem Solving

 (26)
[프로그래머스] 가장 먼 노드 | 파이썬 (💡 최단 경로 알고리즘) 문제 설명 문제 풀이 가장 멀리 떨어지 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드를 의미한다는 부분에서 다익스트라 최단 경로 알고리즘을 사용해야겠다고 생각했다. 전체 코드 import heapq def dijkstra(start): q = [] # 시작 노드로 가는 최단경로는 0 heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] < dist: continue for i in graph[now]: cost = dist + i[1] if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (co..
[BOJ/백준] 4386번 별자리 만들기 | 최소 신장 트리 | 파이썬 문제 설명 문제 풀이 모든 별은 서로 직/간접적으로 이어져 있어야 하고, 별자리를 만드는 최소 비용을 구해야 한다고 해서 그래프 문제, 그중 최소 신장 트리 알고리즘을 사용하는 문제라고 생각했다. * 신장 트리(Spanning Tree): 하나의 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프. 최소 신장 트리는 신장 트리 중에서도 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘이다. 최근에 이코테에서 크루스칼 알고리즘에 대해 공부했기 때문에 이를 적용해보기로 했다! 크루스칼 알고리즘(Kruskal Algorithm)의 과정은 다음과 같다. 1) 간선 데이터 오름차순으로 정렬하기 2) 간선을 확인하며 2-1) 사이클이 만들어지면 pass 2-2) 사이클이 만들어지지 않으면 최..
[프로그래머스] 디스크 컨트롤러 | 파이썬 (💡 SJF 스케줄링 구현하기) 문제 설명 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제 풀이 작업의 요청부터 종료까지 걸린 시간의 평균을 최소로 만들어야하는, 즉 SJF(Shortest-Job-First) 스케줄링을 비선점형 방식으로 구현하는 문제였다. 마침 운영체제에서 스케줄링 기법을 공부하고 있었던 터라 반가웠던 문제❕ 스케줄링에 관한 내용은 아래에서 확인 [운영체제] 4. CPU 스케줄링 | KOCW 2017 이화여대 반효경 교수님 * 강의를 듣고 복습하며 정리한 내용입니다. CPU 프로그램의 기계어 명령을 수행하는 컴퓨..
[BOJ/백준] 5014번 스타트링크 | BFS | 파이썬 문제 풀이 from collections import deque F, S, G, U, D = map(int, input().split()) visited = [0] * (F + 1) def bfs(visited, v): queue = deque([v]) dx = [U, - D] while queue: x = queue.popleft() if x == G: break for i in range(len(dx)): # 해당하는 층이 없을 때 움직이지 않는다 if dx[i] == 0: continue nx = x + dx[i] if 0 역시 엘리베이터 버튼을 누르지 않아도 된다(반복문에서 continue) 5014번: 스타트링크 첫째..
[프로그래머스] Level 2 k진수에서 소수 개수 구하기 | 파이썬 (👀10진수 변환하기) 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우 P처럼 소수 양쪽에 아무것도 없는 경우 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다. 예를 들어, 101은 P가 될 수 없습니다. 예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진..
[프로그래머스] Level 1 모의고사 | 파이썬 | 완전탐색 (🌟 itertools.cycle 사용하기) 문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작..
[BOJ/백준] 10799번 쇠막대기 | 스택 | 파이썬 문제 풀이 import sys def cutIron(bar): stack = [] cnt = 0 for i in range(len(bar)): if bar[i] == '(': stack.append('(') elif bar[i] == ')': if bar[i-1] == '(': stack.pop() cnt += len(stack) else: stack.pop() cnt += 1 return cnt bar = list(sys.stdin.readline()) print(cutIron(bar)) 스택 자료구조를 사용한 문제. 입력으로 받은 문자열을 리스트 bar로 바꿔 쇠막대기 개수를 세는 함수 cutIron에 넣었다. bar의 길이만큼 반복문을 수행한다. 1) bar[i] 값이 '('이면 쇠막대기의 시작을 ..
[BOJ/백준] 2630번 색종이 만들기 | 분할정복 | 파이썬 문제 풀이 import sys def cutPaper(x, y, n): # x,y좌표와 색종이 크기 global cnt_white, cnt_blue print(x, y, n) for i in range(x, x+n): for j in range(y, y+n): if paper[x][y] != paper[i][j]: cutPaper(x, y, n//2) cutPaper(x, y+n//2, n//2) cutPaper(x+n//2, y, n//2) cutPaper(x+n//2, y+n//2, n//2) return # 호출한 함수는 중복되지 않도록 종료시킴 if paper[x][y] == 1: cnt_blue += 1 else: cnt_white += 1 n = int(input()) paper = [list..

티스토리툴바