https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 알고리즘 문제를 풀다보면 시간초과가 나는 경우가 더러 있다. 오늘 내 모습이다. 아무리 바꿔봐도 시간초과가 계속 나길래 뭐가 문제일까 하고 고찰을 시작했다. 제일 초기 코드 import heapq heap = [] n = int(input()) for _ in range(n): i = int(input()) if i == 0: if heap: print(heapq.heappop..

힙? 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 입니다 - 출처 위키백과 힙구조를 한번 봅시다. 힙은 기본적으로 완전이진트리 입니다. 자식노드는 왼쪽노드부터 차곡차곡 빠진 노드 없이 쌓아간다는게 특징이지요. 그렇지만 이진탐색트리와는 차이가 있습니다. 힙은 부모노드가 자식노드보다 크거나 (max heap), 작아야한다(min heap)라는 규칙이 있지만, 왼쪽 자식과 오른쪽 자식간의 차이는 없습니다. 그러나 이진 탐색트리는 부모노드의 값보다 작은 값을 가지면 왼쪽 자식, 큰 값을 가지면 오른쪽 자식으로 가기 떄문에 힙과는 사용에서 차이가 있습니다. 힙의 삽입 힙의 삽입은 간단합니다. 맨 마지막 노드 다음에 값을 넣으면 되거든요. 그 뒤에, 넣은 노..

이진 탐색 트리? 부모노드 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가지는 이진트리. 탐색의 시간 복잡도는 O(logN), 치우친 경우에는 O(n) 그래서 트리가 균형잡혀있는게 중요하다! 어떤 값을 탐색한다면, 현재 노드 기준으로 작으면 왼쪽 자식으로 가고, 크면 오른쪽 자식으로 가서 탐색을 진행한다. 두 이진트리의 병합 https://leetcode.com/problems/merge-two-binary-trees/ Merge Two Binary Trees - LeetCode Can you solve this real interview question? Merge Two Binary Trees - You are given two binary trees root1 and root2. Imagine ..

트리 ? 트리는 나무를 거꾸로 세워놓은 것처럼 보이는 계층형 비선형 자료구조 입니다. 트리에서 나오는 용어 노드 : 트리에서 데이터를 저장하는 기본 요소 루트 : 트리 맨 위에 있는 노드 레벨 : 최상위 노드를 레벨 0으로 하였을 때, 하위 branch로 연결된 노드의 깊이를 나타냄 부모 : 어떤 노드의 상위 레벨에 연결된 노드 자식 : 어떤 노드의 하위 레벨에 연결된 노드 리프 : 자식노드가 하나도 없는 노드 형제 : 동일한 부모를 가진 노드 깊이 : 트리에서 노드가 가질 수 있는 최대 레벨 완전 이진 트리 이진 트리 : 각 노드가 최대 두개의 자식을 가지는 트리 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례로 삽입되어있음! 힙이랑 다른 점은 완전 이진트리는 배열은 안 되어있다! 라는..

BFS? BFS란 Breath First Search의 준말로, 한국말로는 너비 우선 탐색이라고 합니다. 너우탐 이라고 하면 아는 척을 할 수 있습니다. DFS에서는 그래프의 한쪽 끝까지 간 다음에 옆쪽을 탐색했는데, BFS에서는 계속해서 옆 노드를 다 보고, 옆 노드들이 끝나면 아래 노드를 보는 식으로 탐색을 진행합니다. 구현 from collections import deque graph = { 1: [2, 3, 4], 2: [5], 3: [5], 4: [], 5: [6, 7], 6: [], 7: [3], } def bfs_queue(start): visited = [start] q = deque([start]) while q: node = q.popleft() for adj in graph[node..

이번 주에 한 일 본격적인 기술공부 하기 전에, 알고리즘 공부를 했다. 스택, 큐, 힙, 그래프, DFS를 공부하면서 기업 코딩테스트 준비를 했다. 이번 주에 제일 기억에 남았던 문제 DFS 에서 단지번호 붙이기 문제가 제일 기억에 많이 남았는데, https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 강의에서 알려준 DFS 스택 스켈레톤 코드에서 변수만 넣으면 작동하겠지 라는 생각으로 다가가서 문제를 풀었으나, 스켈레톤 코드에서 문제가 있었다. 문제 ..

DFS? Depth First Search 깊이 우선 탐색의 줄임말입니다. 우리말로 하자면 깊우탐 이라고 하면 유식해보임.. 먼저 깊이 우선 탐색에 대해서 알기 위해서는 그래프에 대한 간단한 이해가 필요한데, 그래프는 정점과 정점간의 관계를 표현할 수 있는 자료구조! 입니다. 각 A B C D 는 정점이라고 하고 ( 영어로 Node또는 Vertex ) A-B, B-C, B-D가 이어져있는 걸 보면 이 이어진 점을 간선 이라고 합니다. ( 영어로 Edge ) 그래프의 표현 그래프의 표현 방식은 인접행렬 방식, 인접 그래프 방식으로 두 가지가 있는데, 인접행렬 방식 인접행렬방식은 2차원 행렬을 이용해서 표현하는 방식입니다 # 만약에 b에서 나가는 단방향 그래프라면 0 a b c d a x x x x b o ..

HashTable hash 함수 임의크기 데이터를 고정크기 값으로 매핑하는데 사용 해싱은 가능한 빠르게 저장하고 검색하기위해 사용하는 기법 중 하나. 파이썬의 set 이나 딕셔너리가 이를 활용한 자료구조. 그래서 시간복잡도가 O(1)임!!

https://www.youtube.com/watch?v=CswyI-RK7qk&t=170s&ab_channel=%EA%B3%B5%ED%95%AD%EC%B2%A0%EB%8F%84%5BAREX%5D잠깐 시간을 내어 창문 밖을 바라봐 주시겠습니까?저는 서울의 아름다운 야경도 좋지만 저는 한강 양 끝을 따라 달리는 수많은 자동차들의 불빛을 보곤 합니다아마 운전하고 있는 사람들은 자신의 차에서 빛나는 불빛이 이렇게 아름다운 줄 모르고 있겠죠? 이것은 아마 우리의 모습인 것 같습니다. 멀리서 보는 사람은 우리의 빛을 느껴도 정작 우리는 모르고있다는 것이죠여러분 또한 저 빛나고 있는 차량들의 불빛처럼 언제 어디서나 늘 반짝이고 있는 존재라는 것, 잊지 마시고요.오늘 하루도 대단히 고생 많으셨습니다.집에 돌아가셔서 내..