728x90 반응형 그리디알고리즘4 백준 16953번 A -> B 파이썬 풀이 A → B 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 39711 16395 13073 39.908% 문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. 출력 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 예제 입력 1 복사 2 162 예제 출력 1 복사 5 2 → 4 → 8 → 81 → 162 예제 입력 2 복사 4 42 예제 출력 2 복사 -1 예제 입력 3 복사 100 40021 예제 출력 3 복사 5 100 →.. 2023. 8. 1. 백준 1946 신입사원 파이썬 그리디 알고리즘 신입 사원 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 44646 14764 10772 32.041% 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서.. 2022. 12. 27. 1026번 보물 파이썬 그리디 알고리즘 https://www.acmicpc.net/problem/1026 보물 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 44768 28903 24586 67.032% 문제 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다. S의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에.. 2022. 12. 26. (1) 그리디 알고리즘, 탐욕적인 알고리즘 "이것이 코딩테스트다 with 파이썬" 책을 공부하며 작성하는 글입니다. 3챕터 그리디 알고리즘 그리디 알고리즘 Greedy algorithm이란 현재 상황에서 당장 좋은 것만을 선택하는 것이다. 대부분의 문제에서는 최적의 해를 찾을 수 없을 가능성이 높으나, 탐욕적인 접근이 필요한 문제에서는 효과적이며 직관적이다. 문제가 어렵다면 먼저 그리디로 접근 -> 다른 알고리즘 해보기 다익스트라 알고리즘은 그리디 알고리즘에 속하나 암기가 필요하다. -유명한 거스름돈 문제 1260원을 500원, 100원, 50원, 10원으로 최소 동전갯수로 하기 -> n=1260을 큰 수의 동전부터 나누고, 나머지를 n으로 갱신하여 반복한다. *큰 단위가 항상 작은 단위의 배수여야한다. ex) n= 800일 때 500, 400,.. 2022. 12. 22. 이전 1 다음 728x90 반응형
