본문 바로가기

알고리즘 문제풀이153

[프로그래머스] 더 맵게 - 자바(java), 우선순위큐(PriorityQeueue) 문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 scovil.. 2021. 7. 9.
[프로그래머스] 폰켓몬 - Java(자바), Set 문제 링크 코딩테스트 연습 - 폰켓몬 | 프로그래머스 (programmers.co.kr) 문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다. 첫 번째(.. 2021. 7. 5.
카카오 프렌즈 컬러링북 - Java(자바), BFS(너비 우선 탐색) 카카오 프렌즈 컬러링북 출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.) 그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자. 위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다. 입력 형식 입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와.. 2021. 7. 4.
[알고리즘] 9-7 원더랜드 - 프림 알고리즘, 최소 신장 트리, Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-07 프림 알고리즘(Prim Algorithm) 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법 동작 과정 시작 정점을 최소 신장 트리 집합에 포함한다. 집합에 포함된 정점과 연결된 정점들 중에 최소 비용으로 연결된 정점을 선택하여 연결하여 집합을 확장한다. (단, 회로를 형성하는 이미 집합에 포함된 정점끼리 연결하는 것은 제외) 2번 과정을 최소 신장 트리가 완성될 때까지 반복한다. 신장 트리 : 그래프의 모든 정점이 연결되어있고, 회로가.. 2021. 6. 30.
[알고리즘] 9-7 원더랜드 - 크루스칼 알고리즘, 최소 신장 트리, Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-07 크루스칼 알고리즘(Kruskal Algorithm) 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘 Greedy를 이용하여 가중치 그래프의 모든 정점을 최소 비용을 연결하는 방법을 찾는 것 최소 신장 트리 : 가중치 그래프에서 간선의 가중치 값의 합이 최소가 되고, 회로가 없이 모든 정점이 연결되어있는 트리를 뽑아내는 것 신장 트리 : 그래프의 모든 정점이 연결되어있고, 회로가 없는 그래프 동작 과정 그래프의 간선들을 가중치.. 2021. 6. 30.
[알고리즘] 9-3 결혼식 - Greedy (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 복습할 때 개인적으로 참고하기위해 풀이 코드를 정리하고 있습니다. 문제 링크 : https://cote.inflearn.com/contest/10/problem/09-03 풀이 친구들 5명의 (도착시간, 떠나는시간)이 다음과 같을 때, (14, 18), (12 ,15), (15, 20), (20, 30), (5, 14) 시간의 흐름을 그림으로 나타내면 다음과 같다. class Time implements Comparable{ int time; char status;//S: 도착시간, E: 떠나는 시간 public Time(int time, char status) { this.time = time; this.status = st.. 2021. 6. 26.

티스토리툴바