Algorithm/Greedy (40) 썸네일형 리스트형 (C++) - 백준(BOJ) 18234번 : 당근 훔쳐 먹기 https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net greedy 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 * 먹은 당근의 합을 구하는 과정에서 21억을 초과할 수 있으므로 long long으로 변수를 선언해줍니다. n만큼 w,p를 입력받아야하므로 vector pair long long 형태로 변수 carrot을 선언해줍니다. 📔 풀이과정 키워서 먹는다라는 말이 있습니다. 그 말은 p가 크면 클 수.. (C++) - 백준(BOJ) 6068번 : 시간 관리하기 https://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1 n; for(int i = 0,t,e; i > t >> e; v.push_back({t,e}); } sort(v.begin(),v.end(),cmp); for(int i = n-1; i >= 0; i--){ ans = min(ans, v[i].endTime); ans -= v[i].timeNeed; } if(ans < 0) cout (C++) - 백준(BOJ) 11608번 : Complexity https://www.acmicpc.net/problem/11608 11608번: Complexity Print, on a single line, the minimum number of times you need to use the eraser. www.acmicpc.net greedy문제였습니다. 📕 풀이방법 '최소'로 문자들을 지움으로써 알파벳의 종류가 2개 이하가 되게 하려면 말 그대로 빈도수가 많은 2종류를 제외한 나머지를 지우면 됩니다. 📔 입력 및 초기화 입력을 받습니다. 입력받은 문자열에 대해 나온 알파벳의 개수를 세줍니다. 📔 풀이과정 1. 나오지 않은 알파벳은 제외하고 나온 알파벳들의 빈도 수를 vector변수에 저장합니다. 그러면서 나온 알파벳의 종류 또한 세주어 변수 cnt에 저장합니.. (C++) - 프로그래머스(Summer/Winter Coding(~2018)) : 기지국 설치 https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 그리디 문제였습니다. 풀이방법 아파트의 개수가 최대 2억이기 때문에 배열로 체크하는 형식은 불가합니다. 따라서 회색 부분의 길이들을 모두 구해서 저장한 뒤 순차적으로 기지국을 설치해줘야합니다. 1. 영역 구하기 회색 부분의 영역은 3가지 형태로 존재합니다. 1-1. 가장 왼쪽 영역 : 이 경우에는 1번 아파트 부터 처음 설치된 기지국까지의 길.. (C++) - 백준(BOJ) 1343번 : 폴리오미노 www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net greedy 문제였습니다. 풀이방법 1. '.'이 있는 좌표, 끝에 도당했다면 끝의 좌표 + 1을 queue에 저장합니다. 2. queue가 빌 때까지 다음을 수행합니다. 2-1. piv를 4개씩 보고 옮겨주면서 queue front()까지 "AAAA"를 정답 변수 ans에 붙입니다. 2-2. piv를 2개씩 보고 옮겨주면서 queue front()까지 "BB"를 정답 변수 ans에 붙입니다. 2-3. '.'을 ans에 붙입니다. 2-4. piv를 queue의 front() + 1로 갱신해줍니다. 2-5. pop(.. (C++) - 백준(BOJ) 1138번 : 한 줄로 서기 www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net greedy 문제였습니다. 풀이방법 1. 가장 작은 키의 사림이 위치한 곳은 자기가 왼쪽으로부터 떨어진 거리입니다. 왜냐하면 무조건 자기 보다 큰 사람이 왼편에 서기 때문입니다. 이를 착안한다면 n^2의 시간복잡도로 문제를 해결할 수 있습니다. 2. 0의 개수를 세줍니다. 그래서 0의 개수가 i번째 사람의 키와 같고 비어있는 위치라면 바로 정답배열에 키의 값을 넣어줍니다. Code #include usi.. (C++) - 백준(BOJ) 1339번 : 단어 수학 www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 모든 단어를 확인합니다. 매 단어마다 각 글자의 자릿수를 확인해 1의 자리라면 나온 알파벳의 가중치는 1이고 10의 자리라면 10, 100의 자리라면 100을 부여합니다. 이렇게 모든 알파벳별로 부여된 가중치의 값은 cost배열에 저장됩니다. 2. 해당 가중치와 알파벳이 저장된 cost배열을 보며 pair형태의 vector변수 v에 push해준 뒤 가중치가 큰 순으로.. (C++) - 백준(BOJ) 14659번 : 한조서열정리하고옴ㅋㅋ www.acmicpc.net/problem/14659 14659번: 한조서열정리하고옴ㅋㅋ 첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 www.acmicpc.net greedy 문제였습니다. 풀이방법 1. i번째 봉우리에서 시작합니다. 그 다음 i+1봉우리부터 끝까지 loop를 돌며 i번째 봉우리의 높이보다 작은 j번째 봉우리들의 개수를 세줍니다. 조건에 만족할 때마다 ans에 세준 개수를 저장합니다. 만약 반대라면 구간을 건너뛰기 위해 i = j-1을 저장하고 break;해줍니다. 2. ans를 출력합니다. Code #include.. 이전 1 2 3 4 5 다음
