본문 바로가기
반응형

전체 글571

[자료구조] 이진트리 주요 알고리즘 응용 문제를 잘 풀기 위해 기본을 탄탄하게 만들어야 한다. 이진트리 문제 중 기본에 해당하는 문제들을 익히면서 나만의 접근법을 완성시키자! 1. 이진트리 최대 깊이 탐색(dfs 사용하였다.) leetcode.com/problems/maximum-depth-of-binary-tree # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: max_dep =0 def maxDepth(self, root: TreeNode) -> int: def df.. 2021. 4. 10.
[자료구조] 트리 정의와 종류(그래프와의 차이점, 이진트리 유형) 트리 : 계층형 트리구조를 시뮬레이션하는 추상자료형으로, 루트값과 부모-자식 관계의 서브 트리로 구성되며, 서로 연결된 노드의 집합이다. 가장 큰 차이점은 트리는 순환 구조를 갖지 않는다는 것! 그래프는 단방향, 양방향을 모두 가리킬 수 있는 반면 트리는 단방향(부모->자식)뿐. 또한 트리는 하나의 부모만을 가지고 루트 또한 하나다. 위의 세 경우는 모두 트리가 아닌 경우의 예시다. 첫번째 - C의 부모가 둘이라 트리가 될 수 없음 두번째 - (A-B)와 (D-C-E)가 연결되어 있지 않고 루트가 둘이라 트리가 될 수 없음 세번째 - 순환구조라서 트리가 될 수 없음 이진 트리(Binary Tree) 트리 중 특히 모든 노드의 차수가 2 이하일 때를 이진 트리(Binary Tree)라고 부른다. 유형 3가.. 2021. 4. 9.
[알고리즘 algorithm] 다익스트라 알고리즘- 파이썬 코드와 예제 최단 경로 문제를 푸는 알고리즘으로 가장 잘 알려진 다익스트라 알고리즘을 파이썬 코드로 작성하면 다음과 같다. 기본 문제 : leetcode.com/problems/network-delay-time/ Network Delay Time - 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 class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: graph = co.. 2021. 4. 9.
[python] 파이썬 - 리스트의 객체 복사 개념 - 예시 파이썬은 모든 것이 객체다. 숫자, 문자까지도 객체다. 숫자, 문자가 리스트, 딕셔너리 같은 객체와의 차이점이라면 불변 객체라는 차이뿐이다. 그러다 보니 별도로 값을 복사하지 않는 한, 변수에 값을 할당하는 모든 행위는 값 객체에 대한 참조가 된다. 즉, 참조가 가리키는 원래의 값을 변경하면 모든 참조, 즉 모든 변수의 값 또한 함께 변경된다. 다음 예시를 보면 쉽게 이해가 간다. b는 a를 참조하고 있기 때문에 a가 변경되면 b도 같이 변경된다. 반면 값 자체만을 복사하는 방법으로 [:] 또는 copy()를 사용하게 되면, a가 변경되어도 c와 d는 변경되지 않는다. >> a = [1,2,3] >> b = a >> c = a[:] >> d = a.copy() >> a += [4] >>print(a, b.. 2021. 4. 5.
[python] 파이썬 - 순열과 조합(itertools 활용 또는 dfs 활용 코드) 예제 itertools을 활용하면 순열과 조합을 쉽게 작성할 수 있다. 튜플의 형태로 결과를 리턴한다. >> import itertools >> a= [1,2,3] >> # permutations >> list(itertools.permutations(a)) [(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)] >> list(itertools.permutations(a,2)) [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)] >> # combinations >> list(itertools.combinations(a,2)) ## 'combinations()' requires r-value. [(1,2),(1,3),(2,3)] #첫번째 인자로 리스트가 아닌 튜.. 2021. 4. 5.
[자료구조] DFS 정복을 위한 재귀 연구 프로젝트 재귀함수를 빠르게, 쉽게 작성하려면 어떻게 해야 할까?? 문제마다 재귀함수로 접근을 하려고 하면 항상 머릿 속이 하얘지고 머리가 아파오기 때문에 많은 분석을 통하여 나름의 작성 법칙을 만들어 보기로 했다. 여러 dfs 문제 코드를 보면서 그 속에서 공통점을 찾아보자. 재귀를 작성할 때 헷갈리는 것들 - while을 쓸지 if를 쓸지 - while을 쓸지 for를 쓸지 - return을 쓸지, return으로 무엇을 넘겨줄지 - 재귀함수로 무슨 인자를 넘겨줄 것인가 - 백트래킹을 어떻게 할것인가? 즉 말단 노드에서 어떻게 처리할 것인가 연구(계속 업데이트 중) - 재귀함수에서 while을 쓰면 엄청 복잡해짐 - 재귀함수는 보통 while 보다는 for/if 안에 들어있음 / 아님 아예 밖에 있거나 - 백트.. 2021. 4. 4.
반응형