leetcode7 [LeetCode] 3123. Find Edges in Shortest Paths (Python) 안녕하세요!오늘은 leetcode 3123번 Find Edges in Shortest paths 문제를 풀어보겠습니다. 0~n-1 로 넘버링되어있는 n개의 노드를 가진 그래프가 있습니다. 이 그래프는 2d 배열인 'edges'로 대표되는 m edges로 이루어져 있는데요, edges[i] = [ai, bi, wi] 로 표현될 수 있고, 이는 노드 ai, bi간의 가중치 wi를 의미합니다. 0에서 n-1 노드 까지의 모든 최단 경로 중에서, edges[i] 가 포함되면 True, 그렇지 않으면 False를 출력하는 함수를 작성하는 문제입니다. 모든 결과를 'answer' 배열에 저장하고 출력해주면 됩니다. 이 문제도 이전 시간에 풀었던 문제와 마찬가지로 Dijkstra 알고리즘을 활용해서 문제를 풀어보겠습.. 2024. 11. 17. [LeetCode] 743. Network Delay Time (Python) 안녕하세요!오늘은 Leet Code 743. Network Delay Time 문제를 풀어보겠습니다. 1~n 으로 라벨링 되어있는 n 개의 노드가 있습니다. times 라는 배열도 있는데, times[i] = (ui, vi, wi) 에서 ui는 source node, vi는 target node, wi는 source에서 target으로 신호를 보내는 데 걸리는 시간을 의미합니다. k라는 노드에서 신호를 보낼 때, 모든 n 노드가 신호를 받는 데 걸리는 최소 시간을 출력하는 함수를 만드는 문제입니다. 이때 모든 노드가 신호를 받는 것이 불가하다면 -1을 출력해주면 됩니다. 저는 Dijkstra 알고리즘으로 문제를 풀어보려고 합니다.다익스트라 알고리즘은 음의 가중치가 없는 그래프에서, 가중치 그래프의 한 노.. 2024. 11. 16. [LeetCode] 94. Binary Tree Inorder Traversal 안녕하세요 오늘은 리트코드 94번 Binary Tree Inorder Traversal 문제를 풀어보겠습니다. 주어진 바이너리 트리의 배열을 Inorder 로 출력하는 문제 입니다. Inorder Traversal은 이진 트리를 탐색하는 방법 중 하나로, 왼쪽 자식 노드 > 루트 노드 > 오른쪽 자식 노드 순으로 탐색하는 방법 입니다. 이후에 이진 트리와 다른 탐색 방법에 대해서도 정리해보겠습니다. 해당 문제는 재귀를 사용하여 푸는 방법과 스택을 사용하여 푸는 방법이 있습니다. 먼저 스택을 사용하여 풀어보겠습니다. 풀이 1.스택(stack)은 Last in First out (LIFO) 구조를 가지는 자료구조로, 마지막에 들어간 요소가 가장 먼저 나오는 방식입니다. 스택을 이용하면 재귀적으로 함수를 .. 2024. 10. 13. [LeetCode] 169. Majority Element 안녕하세요 오늘은 LeetCode의 169. Majority Element 문제를 풀어보겠습니다. 이 문제는 주어진 배열에서 과반수 이상의 빈도로 나타나는 요소를 찾는 문제였습니다. 문제 조건으로는 O(n) 의 시간 복잡도, O(1)의 공간 복잡도 안에서 문제를 해결해보는 것이었습니다. 제가 작성한 코드는 다음과 같습니다. 먼저 candidate는 정답이 될 수 있는 배열 내의 요소이고, count 는 해당 요소가 나타난 횟수 입니다. for 문을 통해 배열을 돌며 후보와 카운트를 업데이트했습니다. class Solution: def majorityElement(self, nums: List[int]) -> int: candidate = None # 후보 요소 .. 2024. 10. 2. [LeetCode] 215. Kth Largest Element in an Array 안녕하세요! 오늘은 LeetCode의 215. Kth Largest Element in an Array 문제를 풀어보겠습니다. 이 문제는 주어진 정수 배열에서 k번째로 큰 요소를 찾는 것입니다. 정렬을 하지 않고 찾는 것이 문제의 조건이었습니다. 저는 알고리즘 수업시간에 배운 k-select 알고리즘을 적용해서 풀어보고 싶었습니다. 처음 작성했던 코드는 다음과 같습니다. class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: while len(nums) >= 1: pivot_index = len(nums)//2 pivot = nums[pivot_inde.. 2024. 10. 1. [LeetCode] 83. Remove Duplicates from Sorted List 안녕하세요! 오늘은 83. Remove Duplicates from Sorted List 문제를 풀어보겠습니다. head는 이미 정렬된 linked list이고 head의 원소 중 중복된 원소가 없게 만드는 문제입니다. 제가 생각한 방법은 원소와 바로 다음 원소를 비교하며 같을 시 삭제해나가는 방법입니다. 사실 중복 제거를 보자마자 집합을 사용하는 방법을 먼저 떠올렸었는데요. 하지만 이 문제에서 head는 linked list이기 때문에 집합을 이용해 중복을 제거하기 위해서는 반복문을 통해 각 원소를 하나씩 순회하여 집합을 만들고 이를 다시 리스트로 만들어야하는데, 이 방법이 더 복잡하다고 합니다. 작성한 코드는 다음과 같습니다.# Definition for singly-linked list.# 연결 .. 2024. 9. 14. [LeetCode] 88. Merge Sorted Array 안녕하세요! 오늘부터는 LeetCode를 통해 알고리즘 문제를 풀어보려고 합니다. 오늘은 88번 Merge Sorted Array 문제를 풀어보겠습니다. 문제는 다음과 같습니다. 정수를 포함하고 있는 두 array를 합친 후 정수의 크기를 오름차순 sorting하는 문제였습니다. 정수 배열인 nums1, nums2가 있고, 각 배열의 원소의 개수는 m, n으로 표현하고 있습니다. nums1을 수정해서 답이 출력되도록 문제를 풀어야 했습니다. 제가 문제 풀이를 위해 접근한 방식은 먼저 nums1에 nums2의 원소를 모두 추가한 후, nums1의 원소를 오름차순 정렬하는 방법입니다. 코드는 다음과 같습니다. class Solution(object): def merge(self, nums1, m,.. 2024. 9. 13. 이전 1 다음
