코딩 오름길

이진 탐색 트리 - 부모 기준 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가지는 이진트리. - 평균적으로 탐색의 시간 복잡도는 O(logN), 치우진 경우 O(n). 따라서 균형이 중요 - 자가 균형 이진 탐색 트리는 AVL, 레드블랙 트리 등이 있다. 이진 탐색 트리의 특징 - 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다.

https://leetcode.com/problems/maximum-depth-of-binary-tree Maximum Depth of Binary Tree - 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 이진트리 강의에 있는 코드다. 필수적인 이해가 필요하다. test_max_depth.py from collections import deque from binarytree.prac import make_tree_by def test_max_depth(lst)..

트리 - 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조이다. - 비선형 구조이다 선형구조 vs 비선형구조 - 앞서 보인 큐(Queue), 스택(Stack)은 자료구조에서 선형 구조라고 한다. - 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미한다 - 비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어 있다. - 선형구조와 비선형구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많다. - 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다. * 아래 폴더 구조가 대표적인 트리의 형태다. 트리에서 나오는 용어 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: ..

처음에 풀 때는 5까지 구해보고 풀어봤다. •n = 1 -> (1) 1개 •n = 2 -> (1 + 1) , (2) 2개 •n = 3 -> (1 + 1 + 1), (2 + 1) ,(1 + 2), (3) 4개 •n = 4 -> (1 + 1 + 1 + 1), (1 + 1 + 2), (1 + 2+ 1), (1 + 3), (2 + 1 + 1), (2 + 2), (3 + 1) 7개 • n = 5 -> (1 + 1 + 1 + 1 + 1), (1 + 1 + 1 + 2), (1 + 1 + 2 + 1), (1 + 1 + 3), (1 + 2 + 1 + 1), (2+ 1 + 1 + 1), (1 + 2 + 2), (2 + 1 + 2), (2 + 2 + 1), (1 + 3 + 1), (3 + 1 + 1), (2 + 3), (3..

https://leetcode.com/problems/subsets/ Subsets - 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 입력값이 [1,2,3]일 때 그림과 같은 간단한 트리를 구성한다면 이를 DFS하여 원하는 결과를 출력 할 수 있다. def dfs(index, path): ... for in range(index, len(nums)): dfs(i + 1, path + [nums[i]]) 경로 path를 만들어 나가면서 인덱스를 1씩 증가하는 형태..

그래프 순회 - 그래프 순회란 그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정 - 그래프의 각 정점을 방문하는 그래프 순회(Graph Traversals)에는 크기 깊이 우선 탐색(Depth-First Search)과 너비 우 선 탐색(Breadth-First Search)의 2가지 알고리즘이 있다. - 일반적으로 많이 쓰는 것은 DFS이다. DFS VS BFS - DFS는 주로 스택으로 구현하거나 재귀로 구현하며, 백트래킹을 통해 뛰어난 효용을 보임 - BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용된다. * DFS(깊이 우선 탐색) - 일반적으로 DFS는 스택으로 구현하며, 재귀를 이용하면 좀 더 간단하게 구현할 수 있다. - 코딩 테스트 시에는 재귀 구현이 더..

https://leetcode.com/problems/number-of-islands/ Number of Islands - 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 문제 1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을때, 섬의 개수를 계산해라(연결되어 있는 1의 덩어리 개수 를 구하라) 풀이 1) DFS로 그래프 탐색 from typing import List def numIslands(self, grid: List[List[str]]) -> i..

https://programmers.co.kr/learn/courses/30/lessons/42586?language=python3 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 내가 푼 코드 if 문 안에서는 뇌에 흐름대로 잘 적었는데 else if 에서 좀 생각을 했던 것 같다. def solution(progresses, speeds): answer = [] time = 0 # 시간변수 count = 0 # 카운팅변수 while len(progresses): if (progresses[0] + ..

풀이) 풀이를 보면 굉장히 쉬운 문제다. 정답률이 20%대라는게 믿기지 않는 문제고, 나는 기존에 input() 함수만 입력값을 넣는 줄 알았는데, 찾아보니까 sys.stdin.readline 이라는 게 있었다. from sys import stdin, stdout n = stdin.readline() N = stdin.readline().split() m = stdin.readline() M = stdin.readline().split() for l in M: stdout.write("0\n") if l not in N else stdout.write('1\n') input 대신 sys.stdin.readline 쓰는 이유 - 여러 줄을 입력 받아야 할 때는 input()으로 입력 받는다면 시간초과가 ..

문제 파악 상위 k번 이상 등장하는 요소를 추출해라 예를들어, k = 2 이면 output [1, 2]가 나오고, k = 3이면 [1 , 2 ,3] 이 나온다. 문제풀이 1) Counter를 이용한 음수 순 추출 - 요소의 값을 키로 하는 해시 테이블을 만들고 여기에 빈도 수를 저장한 다음, 우선순위 큐를 이용해 상위 k번 만큼 추출하면 k번 이상 등장하는 요소를 손쉽게 추출 할 수 있다. - 파이썬에서 우선순위 큐는 힙을 활용하는 heqpq 모듈을 사용한다. # 요소의 값을 키로 하는 해시 테이블을 만들고 여기에 빈도 수를 저장한 다음, # 우선순위 큐를 이용해 상위 k번만큼 추출하면 k번 이상 등장하는 요소를 손쉽게 추출할 수 있다. def topKFrequent(self, nums: List[int..