일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 그리디
- 백준
- java
- 문자열
- 플로이드-와샬
- 유니온 파인드
- Network
- 구현
- 프로그래머스
- 완전탐색
- Kotlin
- 스택
- 수학
- mst
- dfs
- CS
- 이분탐색
- 시뮬레이션
- 백트래킹
- BFS
- Effective Java
- 세그먼트 트리
- 후니의 쉽게 쓴 시스코 네트워킹
- 위상정렬
- swea
- 알고리즘
- JUnit 5
- 동적계획법
- 투 포인터
- 에라토스테네스의 체
목록그리디 (8)
반갑습니다!
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이 문제는 그리디하게 해결했다. 이 문제의 핵심 아이디어는 곱하는 수들 간의 차이가 가장 적게 하는 것이다. 만약 s가 9이고, n이 3이라고 가정해보자. 이 때는 3, 3, 3을 곱해야 가장 크다는 것을 직관적으로 알 수 있을 것이다. 이번엔 s가 24이고 n이 6을 생각해보자. 이 역시 4, 4, 4, 4, 4, 4를 곱해야 최대값이 된다는 것을 알 수 있다. 지금까지의 예시는 모두 s를 n으로 나눈 나머지가 0인 경우였다. 이번엔 s가 n으로 나누어떨어지지 않는 경우를 생각해보자. s가 11이고 n..
2012번: 등수 매기기 www.acmicpc.net 풀이 문제의 관건은 각 학생들이 본인이 희망하는 등수와 실제 등수의 차이가 적어야한다는 점이다. 아이러니하지만 5등을 희망하는 선수가 1등을 하면 불만도 4가 쌓인다. 5등을 희망하는 학생은 4등이나 5등, 6등 등을 받는 것이 훨씬 좋다는 얘기이다. 따라서 희망 등수를 오름차순으로 정렬한 뒤, 1등부터 차례로 순위를 부여해주면 된다. 코드 C++ #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; vector s; cin >> n; for (int i = 0; i < n; i++) { int..
1439번: 뒤집기 www.acmicpc.net 풀이 그리디로 해결할 수 있는 문제이다. 전체 문자열을 순회하면서 연속한 0의 개수와 연속한 1의 개수 중에서 더 작은 수가 정답이 된다. 코드 C++ #include using namespace std; int main() { string s; cin >> s; int zero = 0; int one = 0; if (s[0] == '0') zero++; else one++; for (int i = 0; i < s.length() - 1; i++) { if (s[i] != s[i + 1]) { if (s[i + 1] == '0') zero++; else one++; } } cout
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 그리디 알고리즘을 사용해서 풀 수 있다. 우선 routes를 오름차순으로 정렬하면 진입지점이 가장 빠른 순서대로 정렬된다. 그 상태에서 첫 번째 차량을 기준으로 잡고 다음 차량부터 비교해준다. 다음 차량이 기준점보다 먼저 고속도로를 빠져나가면 기준점의 위치를 변경한다. 다음 차량의 진입 지점이 기준점보다 나중이라면 기존의 CCTV로는 해당 차량을 감시할 수 없기 때문에 CCTV 개수를 늘리고 해당 차량의 진입점을 기준으로 한다. 코드 #include #include #include using namesp..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에는 동적계획법으로 해결해야한다고 생각했지만, 조금 더 생각해보니 그리디로 해결할 수 있는 문제임을 알 수 있었다. 순간이동을 하는 경우에는 건전지를 사용하지 않기 때문에 순간이동을 최대한 많이 해야한다는 것을 쉽게 알 수 있다. N에서부터 0으로 간다고 생각했을 때, 순간이동을 최대한 많이 하려면 현재위치가 짝수인 경우에는 2로 나눠주고, 현재 위치가 홀수인 경우에는 짝수로 만들어준다. 이 때 홀수에서 1을 빼면 짝수가 되므로 건전지 1만 사용하고도 짝수를 만들 수 있다. 코드 #include us..