LeetCode - April 30-Day LeetCoding Challenge - Week 1

오랜만에 알고리즘을 공부

감을 찾기 위해 Leet Code 30 챌린지 문제들을 풀어보고 복기 해보자

 

 - Maximum Subarray 문제

 

 

문제 요약 -

주어진 배열에서 값을 더해서 가장 큰 합이 되도록 만드는 문제다

다이나믹 프로그래밍 문제라 할 수 있겠다

 

문제 풀이 - 

임시 저장할 배열을 생성, 

0 부터 시작해서 다음 숫자로 갈때마다 각 숫자까지 왔을때 최대의 합이 나오는 숫자를 

새로 생성한 배열에 저장을 한다 .

 1. 이 전 자리까지 더해서 나올 수 있는 가장 큰 값과 + 현재 자리수 

 2. 현재 자리수

저 2개를 비교해서 가장 큰 수를 배열에 저장

 

문제 정답

https://github.com/kwonhyucknae/algorithm_study/commit/a57ebcc092f54e10d933afa05920b01b72069724

 

 

-Best Time to Buy and Sell Stock 문제

 

 

문제 요약 - 

이 문제는 주어진 배열에서 

싼 날에 물건을 사서 비싼날에 팔수 있는데 , 여러번 거래를 할 수 있다고 가정했을때

거래 profit 총 합이 가장 크게 나올 수 있는 방법을 찾는 문제

 

문제 풀이 - 

Brute force 식으로 풀었다

모든 경우의 수를 다 돌아보는 형태로

 

한 자리의 값에서 이전 값들을 for 문으로 돌면서 , 

자기 보다 낮은 가격이 있으면 다 빼보면서 최적의 값을 찾았다.

 

문제 정답 - 

https://github.com/kwonhyucknae/algorithm_study/commit/a9e98fdf009ad299f93ac3f6489a68836cf03c03

 

 

Group Anagrams 문제

 

 

문제 요약 - 

총 쓰인 알파뱃이 같은 문자열을 묶어서 

List 에 추가하는 문제

 

문제 풀이 -

String 을 한 글자씩 쪼갠 후

sort 시켜 준다. 그럼 이 sort 된 String 값을

HashTable 에 key값으로 저장한 후 

꺼내올때도 key값으로 꺼내서 List 에 저장

 

문제 정답-

https://github.com/kwonhyucknae/algorithm_study/commit/3b1d78961f087cba4740a247ffc43532de78f6c6