알고리즘

[프로그래머스] 야근지수 (힙)

https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 남은 피로도를 최소화 하기 위해서 works 배열 내 모든 원소들의 제곱값의 합을 최소로 만듦 최대힙 사용 풀이 from heapq import heapify, heappush, heappop def solution(n, works): answer = 0 if sum(works) 0: maxval = heappop(works) heappush(works, maxval+1) n -= 1 for..

[프로그래머스] 매출 하락 최소화 (DP, 트리)

https://school.programmers.co.kr/learn/courses/30/lessons/72416 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 워크숍에 참석할 직원들을 선발 모든 팀은 최소 1명 이상의 직원을 워크숍에 참석 워크숍에 참석하는 직원들의 하루평균 매출액의 합이 최소 10번 직원은 C팀과 D팀 모두에 속해 있으므로, 두 팀에서 모두 참석한 것으로 인정 참석하는 직원들의 하루평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합 리턴 d[i][j] : i는 노드번호, j는 워크샵 참여/불참 하는 경우 현재 ..

점 찍기 (피타고라스)

https://school.programmers.co.kr/learn/courses/30/lessons/140107 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 원점 (0,0)으로부터 반원에 들어가는 점 1 ≤ k ≤ 1,000,000이므로 완전 탐색하면 시간 초과 x축을 기준으로 y값 구하기 d² + x² = y² 풀이 import math def solution(k, d): answer = 0 for x in range(0, d+1, k): y= math.sqrt(d*d - x*x) # 피타고라스 answer += y//k + 1 return ..

배달 (플로이드 워셜)

https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 https://karla.tistory.com/29 [11404번] 가장 빠른 버스 노선 구하기(그래프, 최단거리 , 플로이드) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 karla.tistory.com 풀이 import sys def..

무인도 여행 (BFS)

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 섬나라 아일랜드(BFS) 분석 [2667] 단지번호붙이기(BFS) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단 karla.tistory.com 더보기 [2667] 단지번호붙이기(BFS) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를..

[11729] 하노이 탑 이동 순서 (재귀)

11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 분석 1) 재귀 원반이 두 개 이상이면 원반의 개수를 n 이라 할 때, 가장 아래에 있는 원반 n을 도착 기둥에 옮기기 위해 그 위에 놓여 있는 n-1개의 원반을 보조 기둥에 옮긴다. 원반 n을 도착 기둥에 옮긴다. 보조 기둥에 있는 n-1개의 원반을 도착 기둥에 옮긴다. 2) 점화식 먼저 "수열 An​= n개의 원판을 이동하는 횟수" 라고 정의하자. n개의 원판을 이동시키기 위해서는 그 위의 n-1개의 원판을 다른 막대로 이동하고 맨 아래쪽 원판을 ..