알고리즘
-
파이썬 combinations 사용법 [python, 파이썬]알고리즘 2022. 5. 6. 18:55
조합을 만들어주는 combinations 함수 사용법 (파이썬) combination 함수는 조합을 만들어주는 함수이다. 예를들어 [1,2,3,4] 가 있을 때 2 개를 뽑는 경우의 수를 만들어보면 [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] 총 6가지가 존재한다. [4C2] 이러한 모든 경우를 dfs 를 사용해 직접 구할수도 있지만, 굳이 고생하지 말고 간편하게 combinations 을 사용할 수 있다. 사용법 1. 먼저 itertools 에서 combinations 를 임포트 해준다. from itertools import combinations 2. combinations 함수를 사용한다 (!! 콤비네이션 함수의 반환값은 튜플이다) from itertools impor..
-
A star 알고리즘 (python) 설명알고리즘 2022. 5. 6. 15:20
A star 알고리즘은 시작 노드부터 목표 노드까지 최단거리를 효율적으로 탐색 할 수 있는 알고리즘이다. A Star 알고리즘의 작동은 아래 그림과 같다. 시작점 (0,0) 에서 도착점 (n-1, m-1) 까지 최단거리를 탐색을 하는데 BFS 와는 다르게 모든 노드를 탐색하지 않고 거리가 가까운 노드를 중심으로 탐색을 한다. 반면 BFS 는 모든 노드를 탐색하면서 최단거리를 알아낸다. A star 알고리즘을 활용해 아래 그림과 같이 출발점이 0 인 노드에서 도착점이 6 인 노드까지의 최단거리를 구해보자. A star 알고리즘을 사용하기 위해서 휴리스틱 추정값을 사용해야 한다. 휴리스틱 추정값이란, 간단히 말해서 현재 위치의 노드에서 도착점 까지의 대강의 거리를 말한다. 위 그림을 보면 O 와 C 배열이 ..
-
[LeetCode] Shortest Path in Binary Matrix 풀이 (Python)알고리즘 2022. 5. 6. 14:59
[LeetCode] Shortest Path in Binary Matrix 풀이 (Python) https://leetcode.com/problems/shortest-path-in-binary-matrix/ Shortest Path in Binary Matrix - 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 문제 해설 (0,0) 지점부터 (n-1, m-1) 지점까지 가는데 지나는 칸 수를 구하는 문제이다. 각 칸은 0 이나 1 로 구성되어 있으며 0 으로 구..
-
[LeetCode] Backspace String Compare알고리즘 2022. 5. 4. 23:10
844.Backspace String Compare class Solution: def backspaceCompare(self, s: str, t: str) -> bool: def Makestring(myString): ss = "" for char in myString: if (char != "#"): ss += char else: if (len(ss) == 0): continue ss = ss[0:-1] return ss return Makestring(s) == Makestring(t)
-
[LeetCode] Remove Duplicates from Sorted List II알고리즘 2022. 5. 4. 19:16
82.Remove Duplicates from Sorted List II 각 노드가 나오는 갯수와, 각 노드를 dictionary 에 넣은 뒤에 key 값을 사용하여 비교하는 방법이다. 하지만, dictionary 는 파이썬에서는 key 가 들어간 순서가 보장되긴 하지만, 원래는 순서가 보장되지 않는 자료구조이기때문에, 이와같이 링크드 리스트에 사용하기에는 어울리지 않는다. time O(2 * N) space O(2 * N) # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def deleteD..
-
[LeetCode] Search in Rotated Sorted Array알고리즘 2022. 5. 4. 01:55
문제설명 오름차순으로 정렬된 배열 Nums 가 있다. 이 배열 nums 의 k 번째 인덱스를 기준으로 자른다음에 두 도막의 위치를 맞바꾼다. k 는 임의의 숫자이며, 문제에서는 이렇게 변환된 nums 배열이 input 으로 주어진다. 이때 nums 배열안에 target 이 몇번째 인덱스에 위치하고 있는지 알아내야한다. 단순히 반복문으로 O(N) 의 시간으로 해결할 수 있다. 하지만, 문제에서는 O(logN) 의 시간으로 해결하는 조건이 있다. 먼저 O(logN) 으로 해결하기 위해서는 이분탐색을 사용해야한다. 왜냐하면 내가 아는 탐색 알고리즘 중에 O(logN) 의 시간을 가지는 알고리즘은 이분탐색이 전부이기 때문이다. 하지만 문제는 이분탐색을 사용하기 위해서는 배열이 오름차순으로 정렬되어 있어야 하는데..