본문 바로가기

알고리즘 문제408

[Leetcode] 847. Shortest Path Visiting All Nodes 문제 : https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/ 우선 플로이드 워셜 알고리즘으로 모든 정점간 최단거리(dist)를 구한다. 구한 dist 배열로 플로이드 워셜 알고리즘이랑 비슷하게 정답을 구한다. 기본 알고리즘은 다음과 같다. 여기서 상태란 node들이 포함된 상태를 의미한다. (참고) 즉, 플로이드 워셜 알고리즘 처럼 3중 for문을 돌린다. 중간 지점을 중간에 거치는 상태로 두고 시작 노드에서 종료 노드로 갈 때 거치는 최소 간선의 수를 구한다. 조건문에 시작노드가 포함되고 종료노드는 포함되지 않은 상태가 중간상태가 되야 하는 이유는 중간상태에 시작노드가 있어야만 시작 상태가 될 수 있고, 중간상태에 종료.. 2022. 2. 26.
[Leetcode] 1781. Sum of Beauty of All Substrings 문제 : https://leetcode.com/problems/sum-of-beauty-of-all-substrings/ 문자열의 beauty는 가장 자주 사용되는 문자와 가장 자주 사용되지 않는 문자 사이의 빈도 차이이다. 문자열 s가 주어졌을 때 모든 하위 문자열의 beauty 합을 구해라. s.length가 500 이므로 완탐을 돌린다. 2차원 반복문을 돌려서 s[start~end]에서 문자의 등장횟수를 갱신하며 탐색당시의 beauty 값을 구해 정답에 더해나간다. for start = [0, |s|) 문자의 등장횟수를 저장하는 map 갱신 for end = [start, |s|) s[end] 횟수 + 1 등장횟수 map을 탐색하며 최대등장횟수, 최소등장횟수를 구해서 차이를 정답에 더한다. 시간복잡.. 2022. 2. 24.
[Leetcode] 127. Word Ladder 문제 : https://leetcode.com/problems/word-ladder/ 문자들 리스트인 wordList가 주어질 때, beginWord에서 한 글자씩만 바꿔서 wordList에 있는 문자열로 변환해가면서 endWord로 변환가능한 최소 변환시퀀스 길이를 구하라. 만일 변환 불가능하다면 0을 반환하라. 126. Word Ladder2 와 비슷하게 풀었다. 126번과 이번문제와의 차이점은 반환값이 변환시퀀스 리스트인지, 변환시퀀스 길이인지이다. ex) // input beginWord = "hit", endWord = "cog", wordList = ["hit", "hot","dot","dog","lot","log","cog"] 126번 문제와 비슷하게 BFS로 풀고, 이를 위해 먼저 그래프 .. 2022. 2. 12.
[Leetcode] 121. Best Time to Buy and Sell Stock 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ i번째 날의 주식가격이 저장된 price 배열이 주어진다. 한 번의 매수, 매도를 할 수 있을 때 얻을 수 있는 최대 이익을 구하라. 만일 이익을 얻을 수 없으면 0을 반환하라. 배열을 앞에서부터 탐색하면서 최소 가격을 저장하고 탐색 중인 주식가격과 현재까지의 최소 가격의 차이들 중 최대값이 정답이 된다. 시간복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorithm-python/blob/main/leetcode/easy/121.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock.py 2022. 2. 4.
[Leetcode] 454. 4Sum II 문제 : https://leetcode.com/problems/4sum-ii/ 크기가 n인 4개의 정수 배열 nums1, nums2, nums3, nums4가 있다. nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 을 만족하는 튜플(i,j,k,l)의 수를 구하라. map을 이용하여 nums1 + nums2 값을 key, 개수를 value에 저장한다. nums3 + nums4 요소들을 구하면서 map 에 -1 x (nums3 + nums4)를 key 값으로 하는 요소가 있는지 확인하고 있다면 value를 정답에 더해준다. 시간 복잡도는 O(N^2) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medi.. 2022. 2. 3.
[Leetcode] 1305. All Elements in Two Binary Search Trees 문제 : https://leetcode.com/problems/all-elements-in-two-binary-search-trees/ 두 개의 bst 트리의 루트 노드들이 입력으로 주어질 때, 두 개의 트리들이 가지는 요소들의 오름차순 정렬된 리스트를 구해라. 중위순회 로 두 개의 bst를 각각 탐색하여 정렬된 2개의 리스트를 만든다. 두 개의 리스트를 앞에서부터 탐색하면서 탐색 중인 요소들 중 작은 값을 먼저 정답 배열에 추가하는 식으로 정답 배열을 만들어나간다. 시간복잡도는 두 개의 bst의 노드 개수를 각각 N, M 이라 한다면 O(N + M). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1305.%20All%2.. 2022. 1. 26.

티스토리툴바