성댕쓰 똑똑한 생활

링크드 리스트는 값과 주소를 가진 노드로 이루어져있다. 탐색에 O(n) time complexity가 필요하다. 배열과 비교해보면 탐색에 필요한 time complexity는 같다. 그러나 random access에 필요한 값은 링크드 리스트 O(n) 배열 O(1)로 다르다. insertion과 deletion에 필요한 time complexity는 O(1)이다. 하나의 노드가 하나의 노드에 대한 정보를 가지고 있으면 singly linked list, 두 곳의 정보를 가지고 있으면 doubly linked list라고 부른다. 링크드 리스트는 tree나 graph의 기본 데이터 스트럭트가 된다. 링크드 리스트를 python으로 구현해 본 코드 # Title : Linked List Intro # 1. ..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 20. 20:48

N Queens 문제는 NxN 매트릭스에 N개의 queen을 서로 공격할 수 없는 위치에 놓는 모든 방법을 구하는 문제이다. 참고로 queen은 가로, 세로, 대각석으로 공격이 가능하다. basic solution 매트리스 모든 위치를 decision space로 생각하고 백트래킹 적용한다. 단, 중복 확인을 피하기 위해 현재 decision space 는 이전 위치의 다음 위치부터로 하는 제한을 둔다. queen은 각 행에 1개씩만 올 수 있다는 사실을 이용하여 1단계 더 최적화 가능하다. queen의 위치 위반 규칙을 이용하여 1단계 더 최적화 가능하다. hash set을 사용하여 칼럼과 대각선이 규칙을 위반하는지 체크가능하다. 로우는 위에서 한 작업 덕분에 체크하지 않아도 된다. # Title : ..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 19. 23:22

백트랙킹을 이용하여 스도쿠 퍼즐을 푸는 문제이다. # Title : Sudoku 풀이 # Chapter : Backtracking # Link : # ChapterLink : # 문제 : 주어진 sudoku를 풀어라 (inplace로서 input object에 답을 넣어라) # [['. ','5','1','3','. ','9','. ','. ','6'], # ['. ','2','. ','8','7','1','3','4','5'], # ['. ','. ','. ','2','. ','. ','. ','. ','. '], # ['2','1','9','7','6','4','. ','3','. '], # ['. ','. ','. ','1','3','. ','. ','. ','. '], # ['7','3','. '..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 17. 22:36

백트랙킹은 가능성을 탐색하는 방법으로 순열 문제를 풀 때 사용하기 좋다. 문제: nums로 주어진 숫자로 만들수 있는 모든 permutation들을 return 하여라 from typing import List class Perm: def Permute(self, nums: List[int]) -> List[List[int]]: self._nums = nums self._ret = [] self._BT([]) return self._ret def _BT(self, crntNums : List[int]) -> None: if len(crntNums) == len(self._nums): self._ret.append(crntNums.copy()) return for num in self._nums: if n..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 8. 22:55

문제: nums로 주어진 숫자로 만들수 있는 subsets들을 return하여라 이를 recursive 한 방법으로 풀면 아래 그림과 같다 주의 해야할 점 1. letters를 넘길 때 reference로 넘기면 쓸데없는 deep copy를 막을 수 있다. 2. reference로 넘기면 다음 bt전에 letters를 원복시켜야 한다. from typing import List class Subsets: def GetSubSets(self, nums:List[int]) -> List[List[int]]: self._nums = nums self._ret = [] self._BT(0, []) return self._ret def _BT(self, level:int, subsets:List[int]) -> ..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 7. 23:12

다이나믹 프로그래밍은 problem을 sub problem으로 나누고, 중복 되는 problem을 memoization하여 문제를 푸는 방식이다. 백트래킹은 decision space 공간을 정의하고 탐색한 뒤 다시, 정의한 공간으로 돌아오는 문제 풀이 방식이다. key pad 문제를 풀어보자. 각 번호에 해당하는 알파벳을 조합하여 모든 경우의 수를 찾는 문제다. from typing import List class LetterCombinations: def Solutions(self, digits: str) -> List[str]: self._keypad = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'] self._ret = [] self._di..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 7. 22:01

knapsack problem이란 무게 제한이 있는 가방에 value와 weight가 있는 물건을 넣을 때, 넣을 수 있는 최대 value는 몇? 과 같은 문제를 말함. problem과 sub problem을 잘못 나누면 다음과 같이 된다. sub problem 에서 problem에 빠진 물건을 항상 넣는 방식으로 나눈게 문제다. 각 물건이 없는 경우를 고려하여 문제를 나누면 아래와 같다. 이를 2차원의 array에 표현하면서 bottom up 방식으로 풀 수 있다. class ObjectVal: def __init__(self, weight : int, value: int) -> None: self.weight = weight self.value = value from typing import List..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 6. 22:25

문제: coins에 주어진 동전을 가지고 amount를 만들기 위한 최소한의 동전의 갯수는 몇개인가? from typing import List def CoinChange(coins : List[int], amount : int) -> int: dp_array = [-1] * (amount + 1) dp_array[0] = 0 MAXCNT = 9999999 for idxSum in range(1, amount + 1): minCnt = MAXCNT for coin in coins: if idxSum - coin < 0: continue if dp_array[idxSum - coin] == -1: continue minCnt = min(minCnt, dp_array[idxSum - coin] + 1) dp..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 6. 21:24

문제: 2d array로 길을 가기 위한 비용이 주어진다. 왼쪽 위에서 오른쪽 아래까지 도달하기 위한 최소 비용은 얼마인가? 이전 문제와 다른 점은 2d 라는 것 뿐이다. 다이나믹 프로그래밍(계단 오르기) (tistory.com) 다이나믹 프로그래밍(계단 오르기) 문제: n개의 계단을 오르고자 한다. 한번에 1개, 2개씩의 계단을 오를수 있을때 총 몇가지 방벙으로 계단을 오를 수 있는가? 피보나치 수열 문제와 똑같다. 시작 지점만 다름. 다이나믹 프로그래 dockdocklife.tistory.com from typing import List def minPathSum(grid:List[List[int]]) -> int: row = len(grid) col = len(grid[0]) costGrid = [..

카테고리 없음 2021. 7. 5. 23:27

문제: n개의 계단을 오르고자 한다. 한번에 1개, 2개씩의 계단을 오를수 있을때 총 몇가지 방벙으로 계단을 오를 수 있는가? 피보나치 수열 문제와 똑같다. 시작 지점만 다름. 다이나믹 프로그래밍(기초) (tistory.com) 다이나믹 프로그래밍(기초) 다이나믹 프로그래밍 적용 가능 조건 3가지 1. Problem이 Sub problem으로 나눠진다. 2. Sub problem으로 더 큰 규모의 sub problem 의 solution을 구할 수 있다. 3. Sub problem이 겹친다. -- memoization 이용.. dockdocklife.tistory.com def climbStairs(n : int) -> int: dp_array = [0, 1, 2] for i in range(3, n+1..

똑똑한 개발/Algorithm 과 Data Structure 2021. 7. 5. 22:36