목록알고리즘 (17)

소피it블로그

[LeetCode] 739번 Daily Temperatures 문제 풀이 (파이썬) 그리고 enumerate에 대한 고찰

https://leetcode.com/problems/daily-temperatures/ Daily Temperatures - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 자체는 그렇게 어렵지는 않다. 인덱스 값들을 저장해둘 필요가 있다는 점만 파악하면 스택으로 쉽게 구현이 가능하다. 그런데 enumerate로 값과 함께 저장하려고 하니 시간 제한에 걸린 반면, 인덱스만 저장했을 때는 잘 풀렸는데 도대체 이유가 뭔지 아직도 잘 모르겠다. enumerate..
CS/알고리즘 문제풀이 2022. 10. 6. 09:24
[LeetCode] 104번 Maximum Depth of Binary Tree 문제 풀이 (파이썬)

https://leetcode.com/problems/maximum-depth-of-binary-tree/ Maximum Depth of Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 재귀적으로 풀 수 있었다. 다이나믹 프로그래밍의 원리를 이용해서, 특정 노드에서의 최대 깊이는 자식 노드의 최대 깊이에 1을 더한 것이라는 점에 착안하여 풀었다. 다만 재귀적으로 푸는 과정에서 바로 max값을 구해주었기 때문에 메모이제이션은 사용하지 않았다..
CS/알고리즘 문제풀이 2022. 10. 3. 19:17
[LeetCode] 70번 Climbing Stairs 문제 풀이 (파이썬)

https://leetcode.com/problems/climbing-stairs/ Climbing Stairs - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이거 DP일것 같다고 직접 그래프도 그려놓고선 왠지 자신이 없어서 다른 방법 고민하다가 시간 너무 많이 썼다. 뭔 itertools permutations 이런거 찾아보고 divmod로 고민해보고 증말........ 진짜 속쓰리다. 결론부터 말하면 너무나도 DP인 문제 맞다. n = 5라고 했을 때 (..
CS/알고리즘 문제풀이 2022. 10. 3. 17:55
[LeetCode] 3번 Longest Substring Without Repeating Characters 문제 풀이 (파이썬)

https://leetcode.com/problems/longest-substring-without-repeating-characters/ Longest Substring Without Repeating Characters - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com DP를 활용해야 하는 문제인 것 같기는 했는데, 아직 해당 유형을 많이 풀어본 적이 없는지라 어떻게 풀어야 할지 막막해서 계속 코드를 썼다 지웠다 하고 종이에 그림도 그렸다 포기도 했다 온갖 ..
CS/알고리즘 문제풀이 2022. 10. 3. 12:31
[알고리즘] 투 포인터 알고리즘, 구간 합 계산

자료 출처: https://youtu.be/cswJ1h-How0 1. 투 포인터 알고리즘 예시 문제: 특정한 합을 가지는 부분 연속 수열 찾기 start, end가 0번째 인덱스를 가리키도록 함 (start
CS/자료구조, 알고리즘 이론 2022. 10. 2. 22:17
[이코테] 효율적인 화폐 구성 문제 풀이 (파이썬)

문제 출처: https://youtu.be/5Lu34WIx2Us 이 문제가 다이나믹 프로그래밍 유형인 이유를 먼저 생각해보자. 2, 3원을 가지고 15원을 만들 수 있는지, 있다면 최소한의 화폐 개수는 몇 개인지 알기 위해서는 어떻게 해야 할까? 15원을 만들기 위한 최소한의 화폐 개수를 f(15)라고 하자. (15원에서 2원을 뺀) 13원과 (3원을 뺀) 12원을 만들 수 있다면, 각각 +2원 or +3원의 과정을 한 번만 더 하면 15원을 만들 수 있을 것이다. 즉, f(15)의 최솟값은 min(f(13), f(12)) + 1원이 된다. 13원일 때의 최소 화폐 개수와 12원일 때의 최소 화폐 개수를 비교하여 거기에 한 번의 연산만 더해준다면 f(15)를 구할 수 있다는 것. 그렇다면 f(13)과 f..
CS/알고리즘 문제풀이 2022. 10. 2. 18:48
이전 Prev 1 2 3 Next 다음