이번 주에 한 공부 이번 주도 알고리즘 공부를 했다. BFS, 트리, 이진 탐색 트리, 이진 탐색 알고리즘, 힙, 정렬 알고리즘 ( bubble, insertion, selection ) 이번 주에 가장 기억에 남았던 문제 2023.12.22 - [TIL/[순간순간 알게된 짧은 지식] TIL] - 파이썬 입출력 시간 파이썬 입출력 시간 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 mingtian-chan.tistory.com 백준 1927, 최소 힙 문제. 문제를 풀면서 시간 복잡도의 중요성을 깨..

정렬? 정렬은 데이터를 순서대로 나열하는 방법! 이하로는 어떻게 데이터를 나열할 지에 대한 방법을 연습하고자 한다. Bubble Sort 버블 정렬 https://youtu.be/Iv3vgjM8Pv4?si=AAnMnxyka7DF5WtG&t=54 a[0]에서부터 a[9]까지 붙은 원소끼리 서로 자리를 바꾸어나가고, 그다음은 a[0]부터 a[8]까지, 계속해서 반복하고 a[0], a[1]의 자리를 서로 맞추어주면 정렬이 되게 됩니다. def bubblesort(lst): iters = len(lst) - 1 for iter in range(iters): wall = iters - iter for cur in range(wall): if lst[cur] > lst[cur + 1]: lst[cur], lst[c..

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 ..