옌의 로그

문제[프로그래머스] 숫자 게임(Summer/Winter Coding(~2018))사용 알고리즘- 투 포인터 (two pointer) / Greedy- 시간복잡도 O(N logN)해결방법A, B를 모두 오름차순 정렬A의 각 원소에 대해, B에서 A보다 큰 숫자를 찾아 이긴 횟수를 증가시킨다소스코드사용언어 : javaimport java.util.*;class Solution { public int solution(int[] A, int[] B) { int answer = 0; // A, B 오름차순 정렬 Arrays.sort(A); Arrays.sort(B); int j = 0; // B inde..

문제[프로그래머스] 야근 지수사용 알고리즘- Heap / Greedy- 우선순위 큐 (PriorityQueue)- 시간복잡도 O(n logN) (n: 남은 시간, N: 작업 수)해결방법주어진 works를 우선순위 큐에 작업량이 많은 순으로(내림차순) 넣는다남은 작업시간 n 동안 반복문을 돌면서, 가장 많은 작업량을 가진 일을 찾아서(조회) 1씩 줄이고 다시 큐에 넣는다이 동작을 효율적으로 처리하기 위해 힙 구조를 사용소스코드사용언어 : javaimport java.util.*;class Solution { public long solution(int n, int[] works) { long answer = 0; PriorityQueue pq = new PriorityQueu..

문제 [백준] 행복 유치원 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 사용 알고리즘 - 그리디 (Greedy) 해결방법 원생 사이의 키 차이가 비용일 때, 비용이 최소값이 되게 하려면 서로 인접한 원생들의 키 차이를 봤을 때, 비용이 가장 큰 사이부터 갈르면 된다. 예를 들어, 문제 예제 1번의 경우 원생의 키 : 1 3 5 6 10 키차이(거리) : (2)(2)(1)(4) 총 3그룹으로 만드로 싶다면, 원생 사이를 2번 가르면 되는데, 이 때 키차이가 큰 구간부터 가른다고 생각하면 된다. > 1 |..

문제 [백준] 주유소 (Olympiad > 한국정보올림피아드 > KOI 2016 > 중등부 2번) 사용 알고리즘 - 그리디 (Greedy) 해결방법 마을이 일직선 상에 있다는 것이 포인트 한 마을에서 다음 마을로 이동하기 전에 가장 저렴한 주유소를 저장해 두고 해당 주유소에서 주유한 뒤 이동한다 매 번 마을에 도착할 때마다 최소 주유비에 다음 이동 거리를 곱해서 경비를 구해야한다 예제 1의 경우 각 마을의 주유비가 [5, 2, 4, 1] 이다. 이 때 이동할 때마다 그리디 하게 주유비를 선택한다고 하면 다음과 같다. i 현재 주유비 최소 주유비 이동 거리 경비 0 5 5 2 10 1 2 2 3 6 2 4 2 1 2 소스코드 사용언어 : C++ #include #include using namespace..

문제 [프로그래머스] 호텔 대실 사용 알고리즘 - 그리디 (Greedy) 해결방법 키 포인트는 다음 2가지 시간 데이터를 분으로 변경 입실 시간을 기준으로 정렬 퇴실 시간을 담는 배열을 통해 필요한 방의 개수를 count 입실 시간을 기준으로 정렬한 배열 sortedT를 가지고 반복문을 돌며, 해당 순서 사람의 끝나는 시간을 finishT 배열에 담는다. finishT 배열은 항상 빠른 시간이 앞에 오도록 오름차순 정렬을 해주고, 반복문이 돌때마다 현재 순서 사람의 입실 시간과 finishT 배열의 가장 빠른 퇴실 시간을 비교해, 퇴실시간이 더 빠른 경우 그 방에 사람을 받을 수 있다는 뜻이므로 finishT 배열에서 해당 시간을 제거한다. finishT에 담기는 데이터를 순서대로 보면 다음과 같다. f..