부트캠프
[알고리즘 3주차] WIL - 힙, 정렬(버블, 선택, 삽입, 퀵, 머지, 힙)
Heap 완전이진트리로서 부모노드가 자식노드보다 크거나 작은 순서로 정렬되어있는 자료구조를 말합니다. 부모노드가 자식노드보다 작으면 최소힙이라고 부르고, 크면 최대힙이라고 부릅니다. 여기서 완전이진트리란 트리의 왼쪽부터 봤을 때 노드가 비어있지 않은 구조를 말합니다. 힙은 배열로 표현이 가능한데 루트노드를 1인 인덱스로 가정합니다. 루트노드를 중심으로 왼쪽 자식노드는 2 * 부모인덱스, 오른쪽 자식노드는 (2 * 부모인덱스) + 1 가 됩니다. 힙의 삽입 및 삭제에 대해서 알아보겠습니다. 최소힙을 기준으로 알아보겠습니다. 맨 위 루트 노드는 모든 노드중 가장 작은 노드가 될 것입니다. 삽입 이 트리에 어떠한 값을 append합니다. 그리고 부모노드와 비교해 가면서 자신의 자리를 찾아갑니다. 삭제 삭제는 ..
[23일차] TIL 이진 탐색(Binary Search) - (1)
이진탐색이란 정렬되어있는 배열에서 절반씩 줄여가며 탐색하는 기법입니다. 정렬되어있다는 전제가 필요하며 수행했을 시 1억 개 목록을 탐색한다면 27번 안에 찾을 수 있다. 직접 구현하는 방법도 있지만, 파이썬 내장함수인 bisect_left 를 사용해도 됩니다. bisect_right도 있지만 가장 많이 사용되는 것이 bisect_left 입니다. bisect_left는 target값의 index를 반환하는 반면 bisect_right는 index + 1값을 반환하게 됩니다. 따라서 특별한 경우가 아니라면 bisect_left를 가장 많이 사용하게 될것입니다. 1. leetcode 704 https://leetcode.com/problems/binary-search/ leetcode 704번 문제입니다. ..
[22일차] TIL - Week3 Test
1. H-Index https://programmers.co.kr/learn/courses/30/lessons/42747 처음에 대부분의 테스트를 통과하지 못했었는데 문제를 잘못 이해하고 있었습니다. h의 값이 반드시 citations배열에 존재 하지 않아도 된다는 것을 간과했습니다. 다음은 정답 판정 받은 풀이입니다. def solution(citations): answer = 0 citations.sort(reverse=True) lst = [i for i in range(max(citations))] lst.sort(reverse=True) for h in lst: lg = 0 sm = 0 for num in citations: if h = h: answer = h break return answe..
[19일차] TIL (Quick Sort)
퀵정렬 맨 뒤의 값을 pivot값으로 정하고 pivot값보다 작은 값은 앞으로 보내고 큰값은 그대로 둔 후 pivot값을 그 사이에 위치시켜 두 부분으로 나누어 재귀적으로 정렬하는 방식입니다. 시간복잡도는 O(NlogN)이지만 최악의 경우 시간복잡도가 심각하게 늘어날 수 있습니다. 다음은 정렬과 관련된 문제들을 풀어본 후 회고해보겠습니다. 1. 리스트 정렬 https://leetcode.com/problems/sort-list/ 링크드 리스트 문제를 만나면 아직 접근이 힘든 부분이 있습니다. 연결리스트를 처음부터 구현하는것 부터 다시 복습해야할 것 같습니다. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0,..
![[알고리즘 2주차] WIL (Graph, DFS, BFS, Tree)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FPxOn7%2FbtrxwZnBBAj%2FwB6B0UnZELEyM7bzt4YXkk%2Fimg.png)
[알고리즘 2주차] WIL (Graph, DFS, BFS, Tree)
DFS와 BFS를 다뤄보고자 합니다. 여기서 DFS는 깊이 우선 탐색는 보통 재귀함수를 이용한 풀이가 주를 이루고, BFS는 너비 우선 탐색으로 큐를 이용한 풀이가 주를 이룹니다. 그림과 같이 dfs는 하나의 길을 우선적으로 파고 빠져나온 후 다음 경로로 이동하는 탐색방법입니다. 이와 다르게 bfs는 가장 가까운 노드부터 탐색합니다. 위 그림에서 보면 각 층별로 탐색하여 아래로 내려가는 구조일 것 입니다. 2. DFS DFS에 대한 개념은 그렇게 어렵지 않지만 이를 문제에 적용하는 것은 상당히 어려웠습니다. 두 가지 풀이방법에 대해서 배웁니다. 재귀함수를 이용한 풀이 그리고 스택을 이용한 풀이입니다. 스택으로 이용한 풀이는 코드를 보고 이해하기 편했지만 재귀함수를 이용한 풀이는 직접 손으로 그려보지 않으..
[17일차] TIL - Heap
힙이란? 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)입니다. 최대힙과 최소힙은 완전이진트리에서 부모가 자식노드보다 큰 값을 가지거나(최대힙), 작은 값을 가지는(최소힙) 자료구조입니다. 힙 삽입(최대힙) 리프노드에 추가하고자하는 원소를 넣은 후 부모노드와 크기 비교를 합니다. 최대힙을 예로 들자면 추가한 노드가 부모노드보다 크다면 부모노드와 자리를 바꿉니다. 완전이진트리의 최대높이는 O(log(N))입니다. 따라서 최악의 경우 맨 위 루트노드까지 올라갈 수 있으므로 삽입시 시간 복잡도 역시 O(log(N)) 입니다. 삽입과정 1. 리프노드에 삽입하고자하는 원소를 추가합니다. 2. 부모노드와 비교하여 자신의 값보다 작다면 부모노드와 추가된 노..
[16일차] TIL - Week2 Test
2주차 시험 1. 방문 기록 https://programmers.co.kr/learn/courses/30/lessons/49994 def solution(dirs): answer = 0 # 북 동 남 서 dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] d = { "U": 0, "R": 1, "D": 2, "L": 3 } visited = set() answer = 0 x, y = 0, 0 for dir in dirs: i = d[dir] nx = x + dx[i] ny = y + dy[i] if abs(nx) > 5 or abs(ny) > 5: continue if (x, y, nx, ny) not in visited: visited.add((x, y, nx, ny)) visited...