본문 바로가기
반응형

알고리즘80

[Java] 프로그래머스 - 야근 지수 프로그래머스 야근 지수 문제는 퇴근까지 N시간 남은 회사원 Demi의 야근 피로도를 최소화하는 문제다. 난이도는 레벨3이며 우선순위큐를 활용해 해결할 수 있다. 프로그래머스 - 야근 지수 문제 정보 알고리즘 분류 - 그리디 알고리즘 난이도 - Level 3 문제 요약 (야근 피로도) = sum( (남은 작업량) ^ 2 ) 1시간에 작업량이 1이며, 퇴근까지 N시간 남았다. 가능한 야근 피로도의 최소값은? 문제 풀이 과정 1 핵심 아이디어 제곱들의 합을 최소화시키기 위해서는 숫자들간의 편차를 최소화해야 한다. 따라서 매번 제일 큰 수를 줄여나간다. 작업량 배열을 내림차순으로 정렬 후 앞에서부터 단계별로 줄이기 [4,3,3] → [3,3,3] → [2,2,2] 코드 public static long solu.. 2023. 11. 9.
[Python] 프로그래머스 - 최고의 집합 프로그래머스 최고의 집합 문제는 자연수 n개로 이루어진 중복 집합 중에서 각 원소의 합이 S가 되고 각 원소의 곱이 최대가 되는 집합을 구하는 문제다. 난이도는 레벨3이며 그리디한 방식으로 해결할 수 있다. 프로그래머스 - 최고의 집합 문제 정보 알고리즘 분류 - 그리디 난이도 - Level 3 문제 요약 자연수 n개로 이루어진 중복 집합 중에서 각 원소의 합이 S가 되고 각 원소의 곱이 최대가 되는 집합을 최고의 집합이라고 한다. n, S가 주어졌을 때 최고의 집합을 구하라. 문제 풀이 과정 집합 내의 두 숫자의 차의 최댓값이 1인 경우에 곱이 최대가 된다. ex) n=3, S=8 → {2,3,3} S를 n으로 나누었을 때의 몫과 나머지를 이용하여 최고의 집합을 구할 수 있다. 몫이 0이면 최고의 집합.. 2023. 3. 29.
[Python] 프로그래머스 - 광물 캐기 프로그래머스 광물 캐기 문제는 주어진 곡괭이를 사용해 광물을 캐는 방법 중 피로도가 최소가 되는 경우를 구하는 문제다. 난이도는 레벨2이며 백트래킹, 그리디를 통해 해결할 수 있다. 프로그래머스 - 광물 캐기 문제 정보 알고리즘 분류 - 백트래킹, 그래프 탐색 - 그리디 난이도 - level 2 문제 요약 곡괭이 종류는 다이아, 철, 돌이 있으며 각각 0~5개 주어진다. 곡괭이 1개 당 5개의 광물까지 캘 수 있다. 곡괭이를 선택하면 그 곡괭이를 5번 사용하고 나서 다음 곡괭이를 사용할 수 있다. 광물을 캐는 피로도는 곡괭이 종류와 광물 종류에 따라 다르다. (TC와 관계없이 고정되어있음) 광물은 주어진 순서대로만 캘 수 있다. 모든 광물을 캐거나, 곡괭이를 모두 사용할 때까지 광물을 캔다. 문제 풀이 .. 2023. 3. 29.
[Python] 프로그래머스 - 미로 탈출 프로그래머스 미로 탈출 문제는 출발점에서 레버를 당기고 출구로 나가기까지의 최단거리를 구하는 문제다. 난이도는 레벨2이며 BFS를 통해 해결할 수 있다. 프로그래머스 - 미로 탈출 문제 정보 알고리즘 분류 - Graph - BFS 난이도 - level 2 문제 요약 HxW 크기의 격자가 주어진다. S: 시작 지점, E: 출구, L: 레버, O: 통로, X: 벽 출구로 나가기 위해서는 반드시 레버를 동작시켜야 한다. 출구로 나가기위한 최단 이동 거리를 구하라. 문제 풀이 과정 가중치가 없고 단순히 최단거리를 구하는 문제이므로 BFS를 사용한다. 시작점~레버까지의 최단 거리 + 레버~출구까지의 최단거리 코드 import collections # 같은 maps 배열을 여러번 사용하기 위해 방문한 곳을 표시하는.. 2023. 3. 28.
반응형

티스토리툴바