일지 & 개발

문제 요약알고리즘 분류:  그리디, 투 포인터난이도: Medium문제내용:초기 에너지(initial power)와 초기 점수(initial score) 0을 가지고 게임을 시작한다.수 배열 tokens가 주어지며, 이 배열의 tokens[i]는 각 토큰의 에너지 값을 나타낸다.각 토큰은 한 번만 사용할 수 있으며, 다음 두 가지 방법 중 하나로 사용할 수 있습니다앞면: 현재 에너지가 tokens[i] 이상인 경우, 토큰 tokens[i]를 사용하여 에너지를 tokens[i]만큼 잃고 점수를 1 증가시킬 수 있습니다.뒷면: 현재 점수가 1 이상인 경우, 토큰 tokens[i]를 사용하여 점수를 1 잃고 에너지를 tokens[i]만큼 얻을 수 있습니다.최대 점수를 반환 하여라사이트 주소: https://le..

문제 요약알고리즘 분류: 그리디난이도:  Silver5문제내용:2원, 5원 동전으로 거스름 돈을 줄수 있다.거스름돈이 N일때 최소 동전 개수를 구하여라(안되면 -1로 출력하여)사이트: https://www.acmicpc.net/problem/14916  문제풀이 이번 문제는 전체 경우의 수를 탐색하기에는 최대 거스름돈이 10만이라서 모든 경우의 수를 구하면 시간 초과가 나서 O(N) 탐색으로 푸는 방법을 찾아야 될것이다. 그래서 이번 문제는 그리디로 풀것이다. 그리디에 대한 설명은아래글로 확인 해보면 된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알..

문제 요약알고리즘 분류: 그리디난이도: Medium문제내용:2차원 배열 points, points[i] = [xi, yi] 와 정수 w가 주어진다. w는 사각형 가로 길이이다.사각형의 범위가 (x`, 0) , (x` + w, 0), (x`, y`), (x` + 2, y`)로 이루어 진게 몇개가 있습니다.각 points 사각형안에 포함이 되어 있습니다. 모든 점이 사각형 안에 포함 될때 최소 몇 개 사형이 필요한지 반환 하세요.사이트 주소: https://leetcode.com/problems/minimum-rectangles-to-cover-points/description/문제풀이  이번 문제는 모든 경우의 수로 구하면 시간초과가 날것이다. 그래서 최적의 시간내로 풀수 있는 그리디로 풀어야 통과가 되는..

문제 요약 알고리즘 분류: 그리디, 수학 난이도: Medium 문제내용: 각 자리수는 0과 1만 올수 있다. 숫자 N을 주어 줬을때 0, 1만 오는10진수 조합된 숫자로 최소 몇번 더하면 되는지 구하여라. 사이트 주소: https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/description/ 문제풀이 이번 문제에는 그리디 문제이다. 그리디 관련 자세한 내용은 아래 글에서 참고 하면된다. https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy) 이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알고리즘이다. 이 ..

문제 요약 알고리즘 분류: 그리디, 정렬, 힙 난이도:Gold2 문제내용: 문제 번호, 데드라인, 컵라면이 있다. 문제푸는 시간이 1이고 데드라인안에 풀어야 한다. 위 조건대로 컵라면 최대 받을수 있는 개수를 출력해라. 사이트: https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 문제풀이 이번 문제는 그리디와 힙 문제인데, 그리디 알고리즘은 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디와 힙에 대한 설명은 밑에 사이트에 참조하..

문제 요약 알고리즘 분류: 그리디, 정렬 난이도:Silver1 문제내용: T개의 테스트 케이스가 있고 각 테스트 케이스 마다 N개 응시자가 있다. 각 응시자는 필기, 면접 등수로 매긴다. 필기, 면접 둘중하나가 다른 응시자 보다 괜찮은 사람을 하나씩 출력해라. 사이트: https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제풀이 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. ..

문제 요약 알고리즘 분류: 그리디, 정렬 난이도:Gold5 문제내용: N개의 센서와 K개 집중국이 있다. K개의 기지국을 설치해서 송신할수 있도록 최소 거리를 구해라. 사이트: https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제풀이 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 여기에서 확인 해보면된다. 문제 접근 방법 예제 1번을 그림으로 나타낸 것..

문제 요약 알고리즘 분류: 그리디, 정렬 난이도:Gold5 문제내용: 크래인 N개와 박스 M개가 있다. 각 크레인은 최대 들수 있는 무게와 박스별 무개가 주어진다. 1분당 한 크래인은 한개만 옮길수있다. 모든 박스를 옮기는데 걸리는 시간을 구해라. 사이트: https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제풀이 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 밑..