그리디

📖 문제 https://www.acmicpc.net/problem/1417   💡  풀이 방식•  그리디 - 우선순위 큐. 사람 수를 내림차순으로 정렬하는 우선순위 큐를 만들고, 득표 숫자들을 입력받는다.. 우선순위 큐를 돌면서 해당 후보의 득표 수가 다솜이 득표 수보다 크거나 같다면, 해당 후보의 득표 수를 1 감소시킨 후 큐에 새롭게 값을 추가한다. 그리고 다솜이의 득표 수를 +1하고, 정답도 +1한다.  🔺 코드1234567891011121314151617181920212223242526import java.util.*;import java.io.*; public class Main{    public static void main(String[] args) throws IOException ..

📖 문제 https://www.acmicpc.net/problem/11501   💡  풀이 방식• 그리디1. 주식 시세 정보를 저장한다.2. 주식 정보를 역방향으로 탐색하며 최대 이익 값을 갱신한다.   - Why? 오늘 이후 최대 이익을 낼 수 있는 날에 판매하기 위해   - 시간 복잡도 : O(N)3. 구한 최대 이익 값을 결과로 출력한다.  💥 유의사항- 앞에서부터 순방향으로 순회하며 구한다면, 시간 복잡도는 O(N^2)이고 시간 초과가 뜬다..   🔺 코드123456789101112131415161718192021222324252627282930313233343536373839import java.util.*;import java.io.*; public class Main {    publ..

📖 문제https://www.acmicpc.net/problem/20310   💡  풀이 방식• 그리디1. 입력받은 문자열 s에서 0과 1의 갯수를 세며 StringBuilder 객체로 문자열을 민든다.2. 0과 1의 갯수를 각각 절반값으로 교체한다.3. 앞에서부터 1을 없애며, 1의 갯수가 0일 때 종료한다.  0은 뒤에서부터 없애며, 0의 갯수가 0일 때 종료한다. ⇒ 그리디.  가능한 문자열 중 사전순으로 가장 빠른 것을 구한다.5. 문자열에서 남은 0과 1만을 출력한다.  💥 유의사항사전순으로 가장 빠른 것 출력하기  🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051..

📖 문제  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   💡  풀이 방식• 그리디1. 커서를 상하로 이동하며 알파벳을 변경할 수 있는 최솟값을 구한다.answer += Math.min(ch - 'A', 'Z' - ch + 1);  2. 연속된 알파벳 'A'가 끝나는 지점을 찾는다.int idx = i+1; while(idx   3. 좌우 이동 최소 횟수를 구한다.- (i*2) + len - idx ⇒ 오른쪽으로 갔다가 왼쪽으로 움직여 바꾸고 시작점으로 돌아간 후, 왼쪽으로 움직여 마지막 위치로 이동해서 바꾸는 경우   ㄴ (i*2)..

📖 문제 https://www.acmicpc.net/problem/2138   💡  풀이 방식• 그리디- 스위치의 성격 상(on/off) 매 순간의 선택이 최적의 선택이 될 수 있으므로 그리디 사용 가능. 1. 첫 번째 전구의 스위치를 [켜는 / 끄는] 경우를 모두 고려해야 한다.2. 2~N번째 전구까지 반복하며, i-1번째 인덱스의 현재값 != i-1번째 인덱스의 기댓값이면 스위치를 켠다.3. 1번의 2가지 경우 모두 불가능하다면 -1을 출력하고, 아니라면 2개 중 최솟값을 출력한다.  🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758import j..

📖 문제 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 💡 풀이 방식 • 그리디 + 정렬 필요 자료구조 - (보내는 마을, 받는 마을, 박스 개수) 정보를 갖는 객체 - 각 마을 별 받는 박스 개수를 기록하는 1차원 int형 배열 1. M개의 보내는 박스 정보를 입력받아 객체 배열에 저장한다. info = new Info[M + 1]; for(int i = 1 ; i = now.box) { for(int j = now.from ; j < now.to ; j++) { capacities[j..

📖 문제 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 💡 풀이 방식 • 정렬 + 그리디 + 중간값 우체국 위치와, 마을 거주 인원을 저장하는 마을 객체를 만든다.마을 객체 배열에 값을 입력받고, 모든 마을의 인원 수를 저장한다. 입력받은 마을 객체 배열을 정렬한다. - 서로 거리가 같은 경우, 마을 인원 수 기준 오름차순 정렬 - 서로 거리가 다르다면, 거리 기준 오름차순 정렬 그리고 완전탐색을 통해 하나씩 인구 수를 계산하..

📖 문제 1455번: 뒤집기 II 세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다. 동전의 앞면을 0이라고 하고 뒷면을 1이라고 www.acmicpc.net 💡 풀이 방식 • 그리디 (i,j) 위치에서 뒤집는 경우, 해당 칸의 왼쪽 칸과 위쪽 칸이 뒤집힌다 그러므로 오른쪽 아래 점부터 위로 올라가면서 1을 발견할 때마다 뒤집는다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import java.util.*..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 그리디 한 번에 2개의 기지국을 설치할 수 있다. 두 지점 사이에 2w + 1이 몇 개가 들어갈 수 있는지를 계산하면 된다. (2w+1인 이유 : 양쪽으로 w가 퍼지고, 기지국 1개 포함) 현재 위치를 1부터 시작해서 - 현재 위치가 기지국 범위 밖에 있으면, 현재 위치를 포함한 가장 먼 곳에 기지국을 설치하고, 설치한 기지국 밖으로 이동한다. - 현재 위치가 기지국 범위 안에 있으면, 해당 기지국 범위 밖으로 이동한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13..