전체 글
[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...
[13일차] TIL - Back Tracking
알고리즘 주제 - 백트래킹 백트래킹에 대해 공부하고 leetcode 51번 문제를 예제로 풀어보고 다음 3문제를 풀었습니다. 백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전단계로 되돌아갑니다. (back-tracking) 백트래킹과 DFS를 혼동하기 쉬운데 엄밀히 말하면 서로 다른 개념이라고 할 수 있습니다. 백트래킹은 원하는 값과 경로가 다르면 더 이상 해당 경로는 탐색하지 않지만 DFS는 원하는 경우가 아니더라도 모든 경우의 수를 탐색합니다. 1. N - Queen https://www.acmicpc.net/problem/9663 다음과 같이 풀었지만 30초가 넘는 시간이 나오면서 어쩔 땐 정답판정을 받았지..