August 13, 2022
2457번 공주님의 정원 백준 링크 문제 요약 그리디 알고리즘을 사용해서 꽃의 최소의 갯수를 구하는 문제이다. 과정 처음에는 꽃이 지는 시간을 기준으로 내림차순, 꽃이 피는 시간을 기준으로 오름차순으로 정렬해서 풀었다. 앞에서부터 탐색해서 끝나는 시간이 제일 긴 것을 골라서 갱신하는 방식이였다. 하지만 계속 앞에서부터 탐색하면서 불필요한 탐색이 많아졌고…
August 13, 2022
문제링크 문제 요약 크기가 10만개 이하인 정수로 이루어진 수열이 주어질 때, 연속된 숫자들의 합 중에 가장 큰 수를 구하는 문제 풀이 과정 풀면서 중요했던 점은 이전까지의 과정에서 구한 최대 연속합을 더했을 때 손해(더 작아짐)라면 버리고 새로 더하는 것이다. 예시 index 0 1 2 3 4 5 6 7 8 9 arrs 10 -4 3 1 5 6 -35…
August 13, 2022
Next Permutation 사전 설명 사전 순서로 다음 순열을 뽑는 알고리즘이다. 이를 이용해서 다음 순열이 없을 때까지 뽑으면서 순열을 뽑을 수 있는데 재귀를 사용하는 것보다 적은 호출로 순열을 뽑아 낼 수 있다. 단, 이를 활용해서 순열을 뽑을 경우에 전체 중에 특정 갯수만을 뽑는 순열에는 적용할 수 없다. 또한, , 이 들어있는 배열을 사용해서 …
August 16, 2022
LIS(최장 증가 부분 순열) 개념 어떠한 순열이 주어졌을 때, 그 수열에서 순서를 바꾸지 않고 일부 원소를 뽑아서 새로 만든 수열을 이라고 한다. 이 수열이 오름차순으로 되어 있으면 이 되는 것이다. 이렇게 만들어진 수열 중에 가장 긴 수열을 (촤장 증가 부분 순열) 이라고 한다. 예시 4 2 1 3 5 8 6 7 위와 같은 순열이 주어졌을 때,는 다음…