Self-Obj85 [Coding Test][Python] Exhaustive Search(완전 탐색)(Backtracking)개념 및 예제(순열, 조합, 부분집합) ※ Exhaustive Search(완전 탐색) 란?Exhaustive Search(완전 탐색)는 가능한 모든 경우의 수를 탐색하여 정답을 찾는 알고리즘 기법이다.특징완전성(Completeness) : 가능한 모든 경우를 확인하므로, 반드시 정답을 찾을 수 있다.비효율성(Inefficiency) : 최악의 경우 계산량이 급격히 증가하여 실행시간이 길어질 수 있다.단순성(Simplicity) : 구현이 쉽고 직관적이다.적용방법Iterative Approach : 단순 반복문을 통해 확인한다.Recursive Approach : Backtracking 기법과 함께 사용되어 불필요한 탐색을 줄일 수 있다.Bitmasking : 이진수 표현을 이용해 모든 경우의 수를 탐색할 수 있다.1. Backtracking.. 2025. 2. 4. [Coding Test][Python][Shortest Path] Dijkstra Algorithm(다익스트라) 개념 및 예제 1. Dijkstra Algorithm 이란?Dijkstra 알고리즘이란 Weighted Graph에서 시작점과 도착점이 주어졌을 때 최단 경로(Shortest Path)를 찾는 알고리즘이다.시작 Node에서 출발하여 각 Node 까지의 최단 거리를 점진적으로 갱신하며 계산한다. 탐색은 "이미 방문한 Node"와 "방문하지 않은 Node"를 구분하여 진행되며, 방문한 Node로 가는 경로 중에서 가장 짧은 경로를 선택해 나간다. 알고리즘 동작 과정1) Adjance List & Priority Queue 사용Priority Queue에 시작 Node 추가우선 순위가 가장 높은(Distrance가 가작 작은) Node 추출방문 여부 확인Distance Update현재 Node에 연결된 Node를 Prio.. 2025. 1. 30. [Coding Test][Python] Heap(Min Heap / Max Heap) Priority Queue 개념 및 예제(백준 2075번 N번째 큰 수) ※ Heap 이란? Complete Binary Tree(완전 이진 트리)로 구성된 특수한 자료구조이다. Heap은 Priority Queue를 구현하기 위해 사용된다.Heap 종류 Max Heap(최대 힙)부모 노드의 값이 자식 노드의 값보다 크거나 같은 TreeMin Heap(최소 힙)부모 노드의 값이 자식 노드의 값보다 작거나 같은 TreeMin - Max HeapMin Heap과 Max Heap을 동시에 만족하는 자료구조짝수 Level은 Min Heap을 따르고, 홀수 Level은 Max Heap을 따른다.Root Node는 최솟값을 제공하고, 그 자식 노드들은 최대값을 제공한다.Min Max Heap을 통해 최상위 레벨에서 최소값과 최대값을 빠르게 추출할 수 있는 장점이 있다.Sibling 간의.. 2025. 1. 30. [Coding Test][Python] Dynamic Programming(DP) 개념 및 예제 ※ Dynamic Programming(DP, 동적 프로그래밍) 란?DP는 큰 문제를 작은 문제로 나누고, 작은 문제의 결과를 재사용하여 큰 문제를 해결하는 알고리즘이다. 즉, 동일한 하위 문제가 반복되는 문제에서 효율적이다. DP 주요 개념Optimal Substructure(최적 부분 구조)문제를 작은 하위 문제들로 나눌 수 있으며, 하위 문제의 최적 해를 사용하여 전체 문제의 최적 해를 구할 수 있어야한다.ex) 피보나치 수열 : $F(n) = F(n-1) + F(n-2)$Overlapping Subproblems(중복 부분 문제)동일한 하위 문제가 여러번 반복해서 나타나는 경우, 이를 저장해 재사용하면 계산량을 줄일 수 있다.ex) 피보나치 수열의 $F(5)$를 계산할 때 $F(4), F(3)$을.. 2025. 1. 27. [Coding Test][Python] Graph 개념 및 Graph 순회 예제 ※ Grapn 란?그래프 $G(V, E)$는 객체와 객체 간의 관계를 표현하기위한 자료구조이다. Graph는 객체를 표현하는 Vextex의 집합 V와 이들을 연결하는 Edge의 집합으로 구성된다. 그래프의 기본 구성요소Vertex(Node)그래프를 구성하는 기본 요소데이터의 단위를 표현한다Vertex의 집합은 일반적으로 V로 표시한다Edge두 Vertex를 연결하는 선 또는 관계를 의미한다방향성, 가중치 등에 따라 다양한 특성을 가질 수 있다Edge의 집합은 일반적으로 E로 표시한다그래프의 종류Undirected Graph(무방향 그래프)Edge에 방향이 없다. 즉, Vertex $u$와 $v$가 연결되어있다면, 서로 연결된 상태이다.Directed Graph(방향 그래프)Edge에 방향이 있다. 즉,.. 2025. 1. 27. [Coding Test][Python]Tree 개념 및 Tree 순회(Inorder, Preorder Postorder) 구현 ※ Tree 란?데이터를 계층적으로 구성하고 관리하는 자료구조이다.서로 연결된 Node들로 구성되며 Cycle이 없는 Graph이다. Tree 용어 정리Node : Tree는 보통 node로 구현Edge : Node 간에 연결된 선Root Node : Tree는 항상 Root Node에서 시작Leef Node : 더이상 뻗어나갈 수 없는 마지막 노드Parent Node : 다른 노드와 연결되어 Child Node를 가진 NodeChild Node : Parent Node에서 파생된 NodeSibling Node : 같은 Level에 있는 NodeDegree : 각 노드가 갖는 Child Node의 수, 모든 Node의 Degree가 n개 이하인 Tree를 n진 Tree라고 한다Ancestor(조상) : .. 2025. 1. 27. [Coding Test][Python] Hash Table(Dictionary) 개념 및 예제 ※ Hash Table 이란?효율적인 탐색을 위한 자료구조로써 key-value 쌍의 데이터를 입력받는다. Hash Function $h$의 key값을 입력으로 얻은 해시값 $h(k)$를 위치로 지정하여 저장한다. 저장, 삭제, 검색의 시간복잡도는 모두 O(1)이다. Direct Access AddressDirect Access Address는 특정 Key 값을 주소로 직접 사용하여 데이터를 저장하는 방식이다.위 2가지 단점이 존재하기 때문에 Key 값에 Hash Function을 적용하여 사용한다.불필요한 메모리 공간 낭비ex) Key 값이 1, 1000 => 2개의 데이터를 위해 1000개의 공간이 필요Key 값으로 문자열이 올 수 없다Collision서로 다른 Key의 Hash.. 2025. 1. 27. [DL][CNN] LeNet-5 1. LeNet-5 란?LeNet-5는 합성곱 신경망이라는 개념을 최초로 Yann LeCun이 개발한 구조이다. 수표에 쓴 손글씨 숫자를 인식하는 Deep Learning 구조 LeNet-5fmf 1955년 발표하였는데, 이것이 현재 CNN의 초석이 되었다. LeNet-5는 합성곱(Convolutional)과 다운 샘플링(Down - Sampling 혹은 Pooling)을 반복적으로 거치면서 마지막에 완전 연결층에서 분류를 수행한다. Input : 32 x 32 x 1Convolution Layer 1(C1) : 5x5 합성곱 => 28 x 28의 Feature Map 6개 생성in_channels=1, out_channels=6, kernel_size=5, stride=1$W = H = \frac{3.. 2025. 1. 15. [DL][CNN] 설명 가능한 AI (Explainable Artificial Intelligence, XAI)와 Feature Map 시각화, PyTorch 예제 1. Explainable Artificial Intelligence(XAI) 란?Explainable AI란 Deep Learning 처리 결과를 사람이 이해할 수 있는 방식으로 제시하는 기술이다. Deep Learning에서 Model 내부는 Black Box 같아 내부에서 어떻게 동작하는지 설명하기 어렵다.따라서 Deep Learning을 통해 얻은 결과는 신뢰하기 어려운데 처리 과정을 시각화해야 할 필요성이 있다. Model을 구성하는 각 중간 게층부터 최종 분류기까지 입력된 이미지에 대해 Feature map이 어떻게 추출되고 학습하는지를 시각적으로 설명할 수 있어야만 결과에 대한 신뢰성을 얻을 수 있다. 이제부터 CNN 내부 과정에 대한 시각화를 진행하는데 시각화 방법에는 Filter에 대한 .. 2025. 1. 15. 이전 1 2 3 4 5 6 7 ··· 10 다음