본문 바로가기

Algorithm/Greedy

 (43)
(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..
(C++) - 백준(BOJ) 1080번 : 행렬 www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net greedy문제였습니다. 풀이방법 1. 왼쪽 상단부터 a가 b와 다르다면 a의 해당 위치에 연산함수를 실행합니다. 이렇게 b와 같도록 결정하게 되면 다시 살펴볼 필요가 없습니다. 실행과 함께 ans변수를 ++해줍니다. 2. 행렬 크기만큼 loop를 돌며 만약 a와 b가 서로 다르면 만들 수 없으므로 -1을 출력합니다. Code #include using namespace std; int a[51][51],b[51][51],n..
(C++) - 백준(BOJ) 1946번 : 신입 사원 www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 매 테스트 케이스마다 n개의 서류심사, 면접심사 성적 순위를 pair로 한 data를 vector에 입력합니다. 2. 그 후 서류심사 성적 순위를 기준으로 오름차순으로 정렬합니다. 이렇게 되면 0번째 지원자를 제외한 나머지 인원들은 무조건 성적이 0번째보다 더 낮으므로 두번째 면접점수만 비교하면 됩니다. i번째 지원자의 면접성적이 i-1번째 지원자의 ..
(C++) - 백준(BOJ) 1049번 : 기타줄 www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 패키지로 구입할 때의 최소 금액과 낱개로 구입할 때의 최소 금액을 각자 저장합니다. 2. 구입 방식을 3가지로 나누어 각자 방식에 따라 금액을 구합니다. 2-1. n개 이상으로 줄을 패키지로 구입할 때 2-2. n개 만큼 줄을 낱개로 살 때 2-3. n개 미만으로 최대한 패키지로 산 후 나머지를 낱개로 살 때 3. 이들 중 최소값을 출력합니다. Code #include..
(C++) - 프로그래머스(고득점 kit - Greedy) : 단속카메라 programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 회의실 배정 문제와 같은 방식의 문제였습니다. 풀이방법 1. 고속도로에서 나가는 지점이 빠른 순으로 routes를 정렬해줍니다. 2. 고속도로의 전체 길이를 빠르게 탐색하기 위해서는 나가는 지점만 비교하는 것입니다. O(n)으로 routes의 원소를 나가는 지점만 비교해 지나가는 자동차의 수 가장 많이 겹치는 지점마다 answer변수를 더합니다. 어떤 자동차를 골랐을 때 그 자동차가 나가는 지점이 가장 빠르다면 그 지점보다 작은 지점에서 출발하는 모든 자동차를 단속할 수 있습니다...
(C++) - 프로그래머스(고득점 kit - Greedy) : 섬 연결하기 programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 크루스칼 문제였습니다. 풀이방법 1. 간선을 가중치의 오름차순으로 정렬합니다. 2. 사이클이 생기지 않는다면 n-1개의 간선을 union해준 후 뽑아줍니다. Code #include #include #include #include using namespace std; int parent[100001]; int find(int a){ if(a == parent[a]) return a; return a = find(parent[a]); } int unionParent(int a..

티스토리툴바