그래프란? 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열 자료를 저장하고 꺼내는 것에 초점 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성 표현에 초점 그래프 : 연결 관계에 초점 노드(Node): 연결 관계를 가진 각 데이터, 정점(Vertex) 간선(Edge): 노드 간의 관계를 표시한 선 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) 유방향 그래프 (Directed Graph) 방향이 있는 간선 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행 가능 무방향 그래프 (Undirected Graph) 방향이 없는 간선 그래프의 표현 방법 인접 행렬(Adjacency Matrix): 2차원 배열로 그래..
최대 힙 - 삽입 힙이란? 힙? 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Tree)(Complete Binary Tree) 최대/최소의 값들이 필요한 연산에 사용 Max 힙 : 최댓값이 맨 위 Min 힙 : 최솟값이 맨 위 8 Level 0 6 3 Level 1 2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아님 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 4 2 1 Level 2 # 모든 부모 노드의 값이 자식 노드보다 크므로 힙O 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 4 2 5 Level 2 # 모든 부모 노드의 값이자식 노드보다 크지 않으므로 힙이 아님..
트리란? 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열 / 자료를 저장하고 꺼내는 것에 초점 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성 / 표현에 초점 트리 용어 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하위 레벨에 연결된 노드 Leaf Node(Terminal Node): Child Node가 하나도 없는 노드 (제일 끝) Sibling: 동일한 Parent Node를 가진 노드 Depth:..
해시테이블이란? 해시테이블이란 해시함수를 이용해 키를 값에 매핑하는 자료구조 구현 충돌 아무리 좋은 해시 함수라도 충돌을 피하기는 어렵다. 예측 가능한 범위 내에서 해시값이 나오고, 데이터와 짝지어지는 것이기 때문에 해시값이 중복될 수 있다. 👉 입력값이 달라도 똑같은 결과가 나오면 충돌 이를 다루는 방식은 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 이 있다. 오픈 어드레싱은 탐사를 통해 ‘빈 공간을 찾아나서는’ 방식 체이닝은 충돌 발생 시 ‘연결’해가는 것 오픈 어드레싱 O(1) 체이닝 O(n) 오픈 어드레싱은 값이 뭉치는 클러스터링 이 발생할 수 있고, 체이닝은 메모리 오버헤드와 길어질 경우 탐색이 느려진다는 단점 C++, Java, Go는 체이닝을 택하고 Python, ..
스택(Stack)스택(Stack)이란?후입선출의 원칙을 따르는 자료구조로 차곡차곡 쌓아올리는(Stack) 것삽입과 삭제시에 O(1), 탐색에는 O(n)의 시간 복잡도사용 예브라우저의 뒤로가기실행 취소 (Ctrl + z)재귀 함수역순 문자열 (문자열 거꾸로 뒤집기)구현# structures.py'''연결리스트를 응용해서, 대신 제일 앞이 아니라 제일 위여야 하므로 가장 처음 걸 top으로 한다.O↓O↓O↓O↓O형태가 된다.'''class Node: def __init__(self, val = 0, next = None): self.val = val #상자 self.next = nextclass Stack: def __init__(self): self.top ..
배열(Array) 배열이란? 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 순서대로 저장하는 자료구조 데이터 조회에서 O(1)의 [[시간 복잡도]]를 가진다. 장점 연속된 메모리 공간을 사용하므로 처음 데이터의 주소를 알면 나머지도 쉽게 찾을 수 있다. 단점 크기가 고정되어 추가/삭제에 제약이 있다. 연결리스트 (Linked List) 연결리스트란? 각각의 데이터가 메모리 공간 상에 고유한 노드로 존재하며, 해당 노드에 앞과 뒤의 메모리 주소를 기억하고 있는 형태 즉, 노드들이 서로 연결되어 있는 구조 데이터 조회 시 순차적으로 탐색하기 때문에 O(N)의 시간 복잡도 데이터 추가와 삭제에는 O(1)의 시간 복잡도 Array vs Linked List 배열 (Array): 파이썬의 리스트. 접근 쉬움..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제설명매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)Leo는 모든 음식의 스코빌 ..
