helloahram

다익스트라 Dijkstra최단 경로 Shortest Path 탐색 알고리즘 가중 방향 그래프 G = (V, E) 에서 모든 간선의 가중치가 음이 아닌 경우에 단일 출발점 최단 경로 문제를 푼다  다익스트라 특징1. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다 2. 가중치가 음수인 경우는 적용이 될 수도 있고 안 될 수도 있다3. 무방향 그래프, 방향 그래프 모두 사용 가능하다  다익스트라 동작 과정1. 시작 정점 설정 - 시작 정점을 설정하고, 그 정점에서 다른 모든 정점으로 가는 최단 거리를 계산한다                 처음에는 시작 정점의 거리를 0으로, 나머지 모든 정점의 거리는 무한대로 설정2. 미방문 정점 중 최단 거리 선택 - 아직 방문하지 않은 ..

위상 정렬 Topology Sort순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘 사이클이 없는 DAG 에만 적용이 가능하다  DAG Directed Acyclic Graph 방향이 있는, 비순환적인 그래프대학교의 선후수 과목에 비유할 수 있다전자회로 과목은 회로이론과 기초전자회로실험 과목을 이수해야 수강이 가능하다 여기에서 회로이론과 기초전자회로실험의 수강 순서는 중요하지 않다  진입 차수와 진출 차수위상 정렬 동작 과정을 보기 전에 진입 차수와 진출 차수에 대한 개념을 먼저 알아 두어야 한다 진입 차수 Indegree 는 노드로 들어오는 간선의 개수이고진출 차수 Outdegree 는 노드에서 나가는 간선의 개수이다 위상 정렬 동작 과정1. 진입 차수가..

그래프를 탐색하는 방법에는DFS 깊이 우선 탐색과 BFS 너비 우선 탐색이 있다 그래프에 대한 설명은 그래프 종류와 표현 방식에 정리해 놨다 1. DFSDepth-First Search, 깊이 우선 탐색 최대한 깊이 내려가고, 더 이상 깊이 내려갈 곳이 없을 경우 옆으로 이동모든 노드를 방문하는 경우에 사용한다 * 스택 또는 재귀를 이용해서 구현 시간 복잡도 - 인접 리스트 O(V+E), 인접 행렬 O(V^2)   DFS 기본 원칙"앞으로 찾아 가야할 노드" 와 "이미 방문한 노드" 를 기준으로 데이터 탐색한다경로 찾기, 탐색 문제, 백트래킹, 사이클 탐지 등에 유용하다 DFS 코드 구현탐색 순서1 - 2 - 4 - 5 - 3 - 6 4 방문 후 2로 백트래킹하여 5를 방문하고, 다시 2 - 1로 백트래..

그래프연결되어 있는 객체 간의 관계를 표현하는 비선형 자료 구조그래프의 정의그래프 G 는 (V, E) 로 표시한다 추가로 알아보니, 코드에서는 E (간선의 집합)을 직접적으로 사용하지 않고, 코드에서는주로 V (정점의 집합)과 그래프의 인접 리스트나 인접 행렬을 통해 간선을 간접적으로 표현한다고 한다다시 정리하면, (V, E) 는 그래프에서 V 라는 이름의 정점들이 있고, 그 정점을 사이를 연결하는 E 라는 이름의 간선들이 있다는 것을 의미한다따라서 (V, E) 표기는 그래프의 구조를 간단하고 명확하게 나타낼 수 있기 때문에알고리즘을 설계하거나 설명할 때 주로 사용한다고 한다  V - Vertex 정점, 여러 가지 특성을 가질 수 있는 객체, Node E - Edge 간선, 정점들 간의 관계, Link..

클래스 Class객체를 만들기 위한 설계도 (템플릿 역할)객체 Instance클래스를 기반으로 만들어진 구체적인 실체각 인스턴스는 클래스에서 정의한 속성과 메서드를 가진다 node_a = Node('A') # node_a 는 Node 클래스의 객체 self 의 역할1. 자기 참조 클래스 내에 메서드가 호출될 때, 그 메서드가 소속된 객체 자신을 참조한다 즉, 클래스의 인스턴스 (객체) 자신을 가리킨다 2. 객체의 속성과 메서드 접근self 를 통해 각 객체의 속성이나 메서드에 접근할 수 있다그래서 각 객체가 독립적으로 데이터를 저장하고 동작할 수 있다 class Node: def __init__(self, value): self.value = value # self.value 는 현재 객체의 va..

트리 Tree 노드들이 나무 가지처럼 연결된 비선형 계측적 자료 구조 트리 구조를 왜 사용하는가?선형 데이터 구조로는 계층형 구조를 나타낼 수 없기 때문에 트리의 구조는 '데이터 저장'의 의미보다는'저장된 데이터를 더 효과적으로 탐색'하기 위해 사용한다  트리의 구조 노드 Node트리를 구성하고 있는 기본 요소노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있다 간선 Edge노드와 노드 간의 연결선루트 노트 Root Node트리 구조에서 부모가 없는 최상위 노드부모 노드 Parent Node자식 노드를 가진 노드자식 노드 Child Node부모 노드의 하위 노드 형제 노드 Sibling Node같은 부모를 가지는 노드깊이 Depth루트에서 어떤 노드까지의 간선 Edge 수높이 Height어떤 노..

18258 큐2 시간 초과 떠서 해결 방안을 찾아보다가 deque 를 공부해 보기로 했다 덱 dequeDouble-Ended Queue, 양쪽에서 요소를 추가하거나 제거할 수 있는 자료 구조 Python 에서는 collections 모듈에서 제공되며, 스택과 큐의 기능을 모두 가지고 있다from collections import dequequeue = deque('Hello')print(queue)# 실행 결과# deque(['H', 'e', 'l', 'l', 'o']) list.pop() 과 deque.popleft() 의 차이  pop() - list 에서 제일 마지막을 제외한 특정 인덱스의 원소를 삭제하기 위해서는그 원소 뒤의 모든 원소들을 한 칸씩 앞으로 옮겨야 하기 때문에 시간 복잡도 O(n) ..

2805 나무 자르기 문제에서 매개 변수 탐색을 이용해서 풀었기에 정리해본다 매개 변수 탐색 Parametric Search최적화 문제를 결정 문제로 풀 수 있는 알고리즘으로,조건을 만족하는 최소값 또는 최대값을 찾는 방법  * 최적화 문제 - 어떤 알고리즘의 최적 솔루션을 찾는 문제 * 결정 문제 - 답이 이미 결정되어 있다고 보고 문제를 푸는 방식  이분 탐색과의 차이점이분 탐색 공부 자료 이분 탐색은 배열에서 Target 과 일치하는 값을 찾으면 바로 함수를 종료한다반면, 매개 변수 탐색은 함수를 종료하지 않고 모든 배열을 탐색하며조건을 만족하는 가장 크거나 작은 값을 찾는다 1. 어떤 시점까지 조건을 만족하지만 그 후로 만족하지 않는 경우, 조건을 만족하는 최대값 찾기 2. 어떤 시점까지 조건을 ..

1920 수 찾기 문제를 풀다가 이분 탐색이 분류에 있길래 정리해본다 이분 탐색 Binary Search 정렬되어 있는 리스트 또는 배열에서 탐색 범위를 절반씩 좁혀가며원하는 값 Target 의 존재 위치/ 존재 여부를 찾는 알고리즘  이분 탐색 특징 단계마다 탐색 범위를 반으로 나누기 때문에 시간 복잡도는 O(logN) 이다 단, 배열이 정렬되어 있어야만 사용 가능하다는 단점이 있다  Quick Sort 와 유사한 접근 방법을 사용해서, Pivot 대신 mid 값을 계산하여left 로 탐색 범위의 왼쪽 경계, right 로 탐색 범위의 오른쪽 경계를 설정하고찾는 대상과 mid 값을 비교하여 left, right, mid 값을 변경하며 범위를 줄인다 * Quick Sort 공부 자료 이분 탐색 코드백준 ..

9663 N-Queen 을 풀다가 알고리즘 분류에 백트래킹이 있길래 한 번 개념을 정리해 본다 백트래킹 BackTracking재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드 (상태) 가제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외 (포기) 하고 다음 단계로 나아가는 방식 쉽게 말해, 현재 상태에서 가능한 모든 다음 상태를 탐색하다가조건에 맞지 않는 상태를 발견하면 그 상태를 배제하고,이전의 상태로 돌아가서 다른 가능한 경우를 탐색하는 방식이다  백트래킹 문제는 DFS (Depth-First Search 깊이 우선 탐색) 로 접근할 수 있다 DFS 는 그래프나 트리의 모든 노드를 깊이 있게 탐색하며조건에 맞지 않으면 바로 이전 상태로 ..