easy67 [leetcode][594] Longest Harmonious Subsequence.cpp 문제 : leetcode.com/problems/longest-harmonious-subsequence/ 배열이 주어질 때, 최대값과 최소값이 정확히 1차이가 나는 subsequence들의 최대 길이를 구해라. 결국 길이가 1차이나는 요소들의 발생횟수들의 합의 최대값을 구하는 문제. 배열을 탐색하면서 요소 값을 key, 나온 횟수를 value로 가지는 map을 만들어 갱신한다. map을 모두 채웠으면 map을 모두 탐색하면서 탐색중인 map의 key값 + 1을 map에서 찾아서 만약 없으면 최대, 최소 차이가 1인 서브시퀀스를 만들수 없으므로 다음 map요소를 탐색한다. 만일 있다면 map[key] + map[key+1] 한 값들의 최대값을 구하면 정답이 된다. 시간복잡도는 O(N). N은 배열의 길이... 2021. 2. 4. [leetcode][191] Number of 1 Bits 문제 : leetcode.com/problems/number-of-1-bits/ 부호없는 정수 값이 input 값으로 주어질 때, 1비트 수를 구해라. brian kernighan's algorithm을 사용. n & (n-1) 연산을 n이 0이 될 때까지 반복한다. 연산 횟수가 1의 개수가된다. 시간복잡도는 O(logN). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/191.%20Number%20of%201%20Bits.cpp 2021. 2. 2. [leetcode][441] Arranging Coins 문제 : https://leetcode.com/problems/arranging-coins/ n 개의 동전이 있으면 이를 계단 모양으로 배열하려고 한다. i번째 계단에는 i개의 동전이 있어야 한다. n개의 동전으로 조건을 충족시키는 계단의 최대 행 수를 구하라. 1부터 1씩 증가시키면서 i번째 행의 계단을 만들 때 필요한 동전 수를 구해서 정답을 구할수도 있다. 이렇게 풀면 O(N)으로 문제를 해결할 수 있을 것이다. 더 빠른 방법을 알아보자. 계단은 등차 수열이니까 i개의 행을 가진 계단을 만들고자 할 때 등차수열의 합 공식( i * (i + 1) / 2 )을 이용하면 필요한 동전 수를 O(1)만에 구할 수 있다. 이를 이용해서 parametric search 방식으로 문제를 다시 생각해보자. i 행의.. 2020. 7. 2. [leetcode][1029] Two City Scheduling 문제 : https://leetcode.com/problems/two-city-scheduling/ 2N명을 도시 A, B에 각각 N명씩 이동시키려고 한다. 각각 A, B로 이동시키는 비용이 주어질 때 이동시키는 비용의 최소값을 구해라. A아니면 B로 이동시킨다. -> 둘 중 하나는 선택되어야 한다. 하나는 선택되어야 하므로 한 명의 A, B 이동 비용을 비교해야 되고 두 방법 중 이동 비용이 작은쪽으로 이동시켜야 이득이다. 각자 A로 이동시키는 비용 - B로 이동시키는 비용을 구해서 오름차순으로 정렬한다. (B가 A보다 크거나, A비용이 더 크지만 B와의 비용 차이가 별로 나지 않을 수록 앞에 정렬된다.) 앞에서부터 N명은 A로, 그 뒤 N명은 B로 이동시킨다. 시간복잡도는 O(NlogN). 소스코드 .. 2020. 6. 4. [leetcode][367] Valid Perfect Square 문제 : https://leetcode.com/problems/valid-perfect-square/ 양수 num이 주어졌을 때, num이 완벽한 제곱수면 true, 아닌경우 false를 반환한다. sqrt 함수를 사용하지 않고 풀어라. 변수 하나를 1로 초기화시킨 후 제곱 수가 num보다 크거나 커질때까지 1씩 증가한다. 제곱수가 num과 같은 경우 true를 반환하는 방식으로도 풀 수 있다. 그리고 이분탐색으로도 풀 수 있다. left = 1, right = num으로 두고 중간 값(m)의 제곱이 num이라면 true를 반환, 작다면 left = m+1, 크다면 right = m-1로 세팅하고 left가 right보다 작거나 큰 경우 이를 반복한다. left가 right보다 커질 때까지 true를 반.. 2020. 5. 9. [leetcode][122] Best Time to Buy and Sell Stock II 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ 주식 가격 배열이 주어진다. 어떤 주식을 샀을 때 해당 주식을 팔기 전까지는 주식을 구입할 수 없다고 하자. 주식을 사고 판다고 했을 때 얻을 수 있는 최대 이익은 얼마인가? 투 포인터로 해결했다. 처음에는 DP로 했었는데 이건 그렇게하면 TLE 난다. 다시 생각해보니 주식을 사고 나서 최대가를 찍었을 때 파는 거다. 주식가격이 상승 곡선이 시작하기 전 가장 최소값을 찍었을 때, 주식을 구입한다. 상승 곡선이 끝날 때, 주식의 가격이 최대가 됐을 때 주식을 판다. 주식을 판 다음 날부터 다시 위 과정을 반복한다. 이를 배열 끝날때까지 반복한다. 상승 곡선이 끝나기 전에 배열이 종.. 2020. 4. 6. 이전 1 ··· 3 4 5 6 7 8 9 ··· 12 다음