알고리즘

가장 먼저 생각 날 수 있는 자연스러운 정렬 알고리즘리스트에서 가장 작은 수를 찾아서 0번 인덱스에 있는 수와 자리를 바꿈그 다음으로 작은 수를 쭉 찾아서 1번 인덱스에 있는 수와 자리를 바꿈...(끝날때까지)각 값이 어떤 위치로 가야할지 찾는 것리스트 0개, 1개,

0️⃣ 알고리즘 패러다임 자주 나타나는 알고리즘 접근법 한 문제에도 다양한 솔루션이 존재하고, 여러 알고리즘 패러다임으로 문제를 풀 수 있다. 1️⃣ Brute Force (무차별 대입 공격) 무차별적으로 가능한 모든 대안(경우의 수)을 시도해 보는 가장 순진한 알고

미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식장점 : 구현하기 쉽고 빠르다.단점 : 최적의 답이 보장되지 않는다.언제 그리디 알고리즘을 사용할까?문제를 해결하는 다른 알고리즘들이 너무 느릴 때완벽한 최적의 답까지 필요하지 않을 때그리디 알고리즘은

'최적 부분 구조가 있다'는 건 "부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것"을 의미한다.다섯번째 피보나치 수를 구하기 위해서는 네 번째 피보나치 수와 세 번째 피보나치 수를 구하는 부분문제를 먼저 해결해야 한다. 이 두 부분문제의

자료구조데이터의 효율적인 접근 및 조작을 가능하게 해주는 저장 및 관리 방식단순히 0에서 1,000,000까지 있는 list와 set에서 원하는 수 하나를 찾는 데에 걸리는 시간이 set이 더 짧다. 그러나, 항상 set이 빠른 건 아니다. 상황별로 어떤 자료구조가 빠

파이썬의 리스트와 C의 배열에는 차이가 있다.파이썬 리스트계속해서 요소 추가 가능여러 타입의 요소 가능C 배열크기가 고정각 요소를 수정할 순 있지만 삭제는 불가능같은 타입의 데이터만 담을 수 있음C 배열 : int numArray\[4];C배열은 크기를 정해놓고 시작

링크드 리스트(Linked List) 데이터를 순서대로 저장 요소를 계속 추가할 수 있다 상황에 따라 링크드 리스트, 동적배열을 사용한다. 노드라는 단위의 데이터를 저장하고, 데이터가 저장된 각 노드들을 순서대로 연결시켜 만든 자료구조다. 각 노드에 이름을 붙여주

노드가 전 노드의 레퍼런스까지 저장하고 있는 더블리 링크드 리스트를 알아보자. 더블리 링크드리스트는 앞 노드와 뒤 노드에 대한 레퍼런스를 모두 갖는다. 각 노드가 바로 다음 노드에 대한 레퍼런스만 갖는 경우를 싱글리 링크드 리스트라고 한다. 더블리 링크드리스트는

트리란? 트리란, 데이터의 상-하 관계(계층적 관계)를 저장하는 자료구조이다. 트리에서 상위는 부모, 하위는 자식으로 부른다. 그중 가장 위에 해당하는 노드를 root 노드라고 부른다. 트리의 활용 계층적 관계가 있는 데이터를 컴퓨터에서 사용 컴퓨터 과학의 다

힙은 두 개의 조건을 만족하는 트리이다.힙은 완전 이진트리이다.완전 이진트리의 중요한 특징으로 노드 개수가 n일 때 높이는 O(logn)이라는 점이다.모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같다.힙을 활용하여 정렬문제, 우선순위 큐를 구현해보자.정렬 알고

이진 탐색 트리 Binary Search Tree 딕셔너리나 세트라는 추상자료형을 구현하는 데에 사용할 수 있다. 이진탐색트리는 조건이 있는데, > 1. 우선 이진트리여야 하고 왼쪽 부분트리에 있는 모든 노드는 그 노드의 데이터보다 작아야 한다. 오른쪽 부분 트리에

그래프란? 1. 그래프의 기본개념 그래프 : 그래프란 연결 데이터를 저장할 수 있는 자료구조이다. 우리에게 가장 익숙한 연결관계는 위치 데이터이다. 아래처럼 위치들이 연결된 것을 볼 수 있다. 아래는 사회연결망 그래프이다. 엣지 : 노드를 잇는 선은 엣지라고 한다

0️⃣ 그래프 탐색 그래프 탐색이란, 하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것을 의미한다. 시작점 노드는 정하기 나름이며 이 시작점으로부터 다른 노드들을 찾아가는 것이다. 그래프탐색 활용 주어진 두 노드가 경로를 통해 연결됐는지, 안 됐는지를 알아낼

📕 불균형 이진트리의 문제 📗 Red-Black Tree란? 📘 RB tree의 삽입연산 📙 RB tree의 삭제연산

앞서 본 BST 와 Red-Black Tree는 이진트리다.이번에 볼 B-Tree는 다중 분류 트리로, Depth를 줄일 수 있다.B-tree는 언제 사용할까?메모리 접근에서 이 B트리를 사용한다. 메모리 접근시, 하나의 Depth를 내려가는 데에 디스크 블록을 새롭게

각 문제는 (1) 재귀적 해법, (2) DP의 Top-Down(memoization)형식, (3) Bottom-up(tabulation) 세 가지 형식으로 문제를 푼다. 모두 파이썬을 사용한다. 문제1) 조약돌 문제 풀이 1) 재귀적 해법 2) DP : Bo

그래프는 가중치가 있는지, 방향이 있는지에 따라 다르게 표현한다.가중치 여부에 따라가충치 그래프가중치가 없는 그래프방향 여부에 따라유향 그래프무향 그래프각 그래프를 '인접행렬'로는 어떻게 표현하는지 보자무향 그래프인접행렬은 대칭행렬가중치가 있는 무향 그래프인접행렬은 대

frozenset을 쓰는 이유 아래처럼 key는 간선, value는 가중치로 표현하는 dictionary를 만들고 싶다. 근데 아래처럼 set을 key로 쓰게 되면 오류가 난다. 그래서 frozenset을 key로 쓰는 것이다.

이번 글에서는 최단경로 알고리즘 중 BFS로 최단경로 만드는 방법과 Dijkstra 알고리즘을 이해하고, 수도코드를 살펴보고자 한다.파이썬 코드는 다음번 글에서!!최단경로란? 두 노드 사이 경로 중 가장 거리가 짧은 경로그래프의 특성에 따라 최단 거리 알고리즘이 다르다

위상정렬(Topological Sorting)이란 아래처럼 사이클이 없는 유향그래프를 일열로 나열하는 문제이다. 각 노드가 생산과정에서 하나의 Task라고 보면, e를 하기 위해서는 b와 d가 선행되어야 하고, b를 하기 위해서는 a가 선행되어야 한다. 이런 순서를 정