LiJell's 성장기

최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미합니다. 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 다익스트라 알고리즘 동작 과정 출발 노드 설정 최단..

DFS(Depth-First Search) DFS는 깊이 우선탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS는 스택 자료구조(혹은 재귀 함수)를 이용 탐색 시작 노드를 스택에 삽입하고 방문 처리 (방문 기준에 따라) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 더 이상 위 과정을 수행할 수 없을 때까지 반복 #DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visi..

정렬 알고리즘 정렬(sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용 1. 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 탐색(선형 탐색) 범위는 반복할 때 마다 작아진다 array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index = i # 갖아 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array..

Binary index Tree 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조 다른 이름으로 fenwick tree라고도 함 정수에 따른 2진수 표기 정수 2진수 표기 7 00000000 00000000 00000000 00000111 -7 11111111 11111111 11111111 11111001 0이 아닌 마지막 미트를 찾는 방법 특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해선 K & -K 계산하면 됨 K & -K 계산 결과 예시 정수 K 2진수 표기 K & -K 0 00000000 00000000 00000000 00000000 0 1 00000000 00000000 00000000 00000001 1 2 00000000 00000000 000000..

트리(Tree) 자료구조 트리는 가계도와 같은 계층적인(hierarchy) 구조를 표현할 때 사용할 수 있는 자료구조 나무를 뒤집어 놓은 모양을 생각하면 됨 1. 트리 관련 용어 root node: 부모가 없는 최상위 노드 뒤집은 나무의 최상위는 나무의 뿌리. ROOT!! leaf node: 자식이 없는 노드 뒤집은 나무의 최하위는 나뭇잎. LEAF!! size: 트리에 포함된 모든 node의 개수 depth: root node부터의 거리 친척들 촌수 셀 때 생각하면 됨 depth of root node = 0 height: depth 중 최대값 degree: 각 노드의 (자식 방향) 간선 개수 몇개 자식이랑 연결 되어 있는지 자식 두개랑 연결되어 있으면 2 트리의 크기가 N일 떄, 전체 간선의 개수는 ..

알고리즘 1. 우선순위 큐(Priority Queue) 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용 예. 보석 데이터를 자료구조에 넣었다가 가치가 높은 보석부터 꺼내서 확인해야 하는 경우 자료구조 추출되는 데이터 stack 가장 나중에 삽입된 데이터 queue 가장 먼저 삽입된 데이터 priority queue 가장 우선순위가 높은 데이터 우선순위 큐를 구현하는 방법 1) 단순히 리스트를 이용하여 구현 가능 2) 힙(heap)을 이용하여 구현 가능 데이터의 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 아래 표와 같다 우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(H..

알고리즘 시간 복잡도 O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함. O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬. O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐. O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형) O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱. O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱. 1. 스택(stack) 자료구조 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 입구와 출구가 동일한 형태..