지식을 나누는 공간

문제 https://programmers.co.kr/learn/courses/30/lessons/42587?language=python3 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 코드 from collections import deque def solution(priorities, location): temp=[] queue=deque() for i in range(len(priorities)): queue.append((priorities[i],i)) while queue: pri,index=queue...

문제 https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 코드 def solution(progresses, speeds): result=[] # progresses의 배열의 빌 때 까지 while문을 반복 while 1: count = 0 # 배열의 첫번 째 요소가 100미만이면 while progresses[0]=100: count+=1 else: break del progresses[:count] de..

문제 https://programmers.co.kr/learn/courses/30/lessons/42579?language=python3 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 코드 def solution(genres, plays): dict={} result=[] for i in range(len(genres)): if not genres[i] in dict: dict[genres[i]]=plays[i] else: dict[genres[i]]+=plays[i] #{'classic': 1450, '..

문제 https://programmers.co.kr/learn/courses/30/lessons/42578?language=python3 코딩테스트 연습 - 위장 programmers.co.kr 코드 def solution(clothes): dicts={} for i in clothes: if not i[1] in dicts: dicts[i[1]]=1 else: dicts[i[1]]+=1 result=1 for i in dicts.values(): #각 종류별 +1(안입은 경우) result*=(i+1) #전체 -1(전부 안입은 경우) return result-1

문제 https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 코드 def solution(phone_book): phone_book.sort() for i in range(len(phone_book)-1): next=phone_book[i+1] if phone_book[i]==next[:len(phone_book[i])]: return False return True 생각 정리 어떤..

문제 https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 코드 def solution(participant, completion): participant.sort() completion.sort() for i in range(len(completion)): if participant[i] != completion[i]: return participant[i] return participant[..

문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 코드 import sys input=sys.stdin.readline INF=sys.maxsize def bf(start): distance[start]=0 for i in range(1,n+1): for j in range(m): node=array[j][0] next=array[j][1] cost=array[j][2] if di..

벨먼-포드 최단경로 알고리즘 : 음수 간선이 포함된 경우에서 한 노드에서 다른 노드로 가는 각각의 최단경로 구하기 특징 가중치가 음수여도 계산 가능 다익스트라의 가중치는 양수여야함 음수 간선의 순환 또한 감지 가능 시간복잡도 : O(VE) → V는 노드의 개수, E는 간선의 개수 음수 간선의 최단 경로 모든 간선이 양수인 경우 음수 간선이 있는 경우 2.1 음수 간선의 순환이 없는 경우 2.2 음수 간선의 순환이 있는 경우 2->3, 2->5 등의 경우 -> 최단 거리가 음의 무한이 될 수 있음 동작 원리 출발 노드 설정, 최단 거리 테이블 무한으로 초기화 N-1번 아래 과정 반복 2.1 전체 간선 E개 확인 2.2 각 간선을 거쳐 다른 노드로 가는 비용 계산 -> 최단 거리 테이블 갱신 N번째 반복했을..

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다. ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인하는 경우 구현방법 리스트 힙(Heap) 시간복잡도 (구현방법에 따라) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일합니다. (힙 정렬) 이 경우 시간 복잡도는 O(NlogN)입니다. 힙(Heap)의 특징 힙은 완전 이진 트리 자료구조의 일종입니다. 힙에서는 항상 루트 노드(root node)를 제거합니다. 최소 힙(min heap) 1. 루트 노드가 가장 작은 값을 가집니다. 2. 따라서 값이 작은 데이터가 우선적으로 제거됩니다. 최대 힙(max heap) 1. 루트..

문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 코드 n,s=map(int, input().split()) array=list(map(int, input().split())) end=0 comp=array[0] count=float('inf') for i in range(n): while comp