알고리즘/그리디17

• 

  [프로그래머스] 광물 캐기 - java 나의 풀이 import java.util.*; class Solution { public int solution(int[] picks, String[] minerals) { int[][] weights = {{1,1,1},{5,1,1},{25,5,1}}; int answer = 0; int pickCnt = Arrays.stream(picks).sum(); // 광물을 5개씩 묶은 그룹들을 각 그룹의 광물의 가중치 합의 내림차순에 따라 정렬한 큐 // 다이아몬드->1 철->5 돌->25 PriorityQueue groups = new PriorityQueue(Collections.reverseOrder()); for(int i=0; i 0){ // 다이아몬드 곡괭이 사용 picks[0]--; pick =.. 알고리즘/그리디 2023. 8. 6.

• 

  [백준] 2812번: 크게 만들기 - java 나의 풀이 - deque import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayDeque; import java.util.StringTokenizer; public class Main { static BufferedReader br; static BufferedWriter bw; static StringBuilder sb; static StringTokenizer st; static int n, k; static ArrayDeque deq.. 알고리즘/그리디 2023. 3. 5.

• [백준] 1439번: 뒤집기 - 파이썬(python) 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. 문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오. 입력 첫째 줄에 문자열 .. 알고리즘/그리디 2022. 9. 29.

• [이것이 코딩테스트다] 곱하기 혹은 더하기 - 파이썬(python) 문제 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'X' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 X를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다. 예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 (((( 0 + 2 ) x 9) x 8) x 4) = 576 입니다. 또한, 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다. 입력 조건 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1 알고리즘/그리디 2022. 9. 29.

• [이것이 코딩테스트다] 모험가 길드 - 파이썬(python) 문제 한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다. 동빈이는 최대 몇개의 모험가 그룹을 만들 수 있는지 궁금합니다. 동빈이를 위해 N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요. 예를 들어 N=5이고, 각 모험가의 공포도가 다음과 같다고 가정합시다. 2 3 1 2 2 이때 그룹 1에 공포도가 1, 2, 3인 모험가를 한 명.. 알고리즘/그리디 2022. 9. 29.

• 

  [프로그래머스] 단속카메라 - 파이썬(python) 나의 풀이 def solution(routes): routes.sort(key = lambda item : item[1]) camera = 0 min_spot = -30001 for start, finish in routes : if start = min_spot : continue else : min_spot = finish camera += 1 return camera 차량이 고속도로에서 나간 지점을 오름차순으로 정렬한다. 이전 차량이 만난 카메라의 지점을 min_spot 으로 지정하고, 만약 현재 차량이 min_spot 을 만날 수 있다면 반복문을 넘어간다. -> if start = min_spot : continue 그렇지 않다면 내 차량이 마지막으로 빠져나가는 지점을 min_spot 으로 지정하.. 알고리즘/그리디 2022. 9. 17.

• 

  [프로그래머스] 섬 연결하기 - 파이썬(python) 나의 풀이 def find_parent(parent, x) : if parent[x] != x : # 자기 자신이 아닌 경우, 재귀적으로 부모를 찾으러 감 parent[x] = find_parent(parent, parent[x]) return parent[x] def union_node(parent, a,b) : a_parent = find_parent(parent, a) b_parent = find_parent(parent, b) if a_parent == b_parent : # 같은 부모인 경우, 싸이클 생성됨 return False elif a_parent < b_parent : parent[b_parent] = a_parent # 부모의 부모를 변경 else : parent[a_parent] =.. 알고리즘/그리디 2022. 9. 17.

• 

  [프로그래머스] 구명보트 - 파이썬(python) 나의 풀이 def solution(people, limit): people.sort() answer = 0 min_index = 0 max_index = len(people)-1 while max_index - min_index >= 1 : if people[max_index] + people[min_index] 알고리즘/그리디 2022. 9. 16.

• 

  [프로그래머스] 큰 수 만들기 - 파이썬(pytyon) 나의 풀이 def solution(number, k): length = len(number) - k answer = "" i = 0 index = length #가장 높은 자리 while len(answer) != length : if index == 0 : break max_index = i for x in range(i, len(number)-index+1) : if number[x] == '9' : max_index = x break elif number[x] > number[max_index] : max_index = x answer += str(number[max_index]) i = max_index+1 index -= 1 return answer 으아... 구현 아이디어를 떠올리는데 시간이 .. 알고리즘/그리디 2022. 9. 16.

• 

  [프로그래머스] 조이스틱 틀린 풀이 def solution(name): answer = list("A" * len(name)) count = 0 i = 0 # 현재 인덱스 while True : print("i: ",i) # 알파벳 변경하기 if name[i] != "A" : count += min(ord(name[i]) - ord("A"), ord("Z") - ord(name[i]) + 1) answer[i] = name[i] # 다 만들었으면 반복문 탈출 if ''.join(s for s in answer) == name : break left = right = 0 # 왼쪽으로 이동하기 while True : if name[i-left-1] != "A" and answer[i-left-1] == "A" : left += 1 .. 알고리즘/그리디 2022. 9. 16.

• 

  [프로그래머스] 체육복 나의 풀이 def solution(n, lost, reserve): lost.sort() reserve.sort() for i in lost[:] : if i in reserve : reserve.remove(i) lost.remove(i) for i in lost[:] : if i-1 in reserve : reserve.remove(i-1) lost.remove(i) elif i+1 in reserve : reserve.remove(i+1) lost.remove(i) return n - len(lost) 먼저 lost, reserve 리스트를 오름차순으로 정렬한다. 만약 reserve 에 있는 학생이 lost 에도 있다면, 해당 학생을 두개의 리스트에서 각각 제거한다. 만약 lost 에 있는 학생 번.. 알고리즘/그리디 2022. 9. 14.

• 

  [Python] 백준 1783: 병든 나이트 n, m = map(int, input().split()) if n==1 : ans = 1 elif n==2 : ans = min(4, (m-1)//2 + 1) elif m =3 and m>=7 ans = m - 2 print(ans) 총 4가지의 케이스로 나누어 풀었다. 1) 세로 길이가 1인 경우 : 위 아래로 움직일 수 없으므로, 방문한 칸의 개수는 무조건 1개이다. 2) 세로 길이가 2인 경우 : 위 아래로 1칸 씩 밖에 움직이지 못하기 때문에, 최대 방문 개수는 4개일 것이다. 따라서 m 에 따라 최대 4개의 칸을 방문한다. (m-1)//2 + 1 이란 식은 직접 m에 따른 개수를 구함으로써 도출해냈다. m = 1,2 -> 1개 m = .. 알고리즘/그리디 2021. 9. 23.