HTML, CSS, JavaScript Web에서 돌아가는 큰 분류의 3가지 언어 Q. 왜 3가지로 나누어져 있나? A. 각각의 역할이 다름 HTML (Hyper Text Markup Language) 제목, 문단, 표, 이미지를 정의하고 구조화 하는 정적 언어 튼튼한 구조(Semantic)를 만드는 것에 집중 CSS (Cascading Style Sheet) 마크업 언어(HTML, XML 등)가 실제 출력되는 모양을 만듦 ex) 색상, 크기, 폰트, 레이아웃 ... 컨텐츠 구조를 꾸미는 정적 언어로 웹의 시각적 표현 담당 예쁘게 웹을 만드는 용도 JS (JavaScript) 페이지를 동적으로 꾸며주는 역할(웹의 동적처리) HTML, CSS의 업무를 할 수도 있지만 성능적으로 떨어짐 웹 페이지를 제작할 ..

최소 신장 트리의 이해 1. 신장트리란? Spanning Tree, 또는 신장 트리라고 불러옴(Spanning Tree가 보다 자연스러움) 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성(Cycle이 없는 구조)을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴(사이클이 존재하지 않음) 2. 최소 신장 트리 Minimum Spanning Tree, MST라고 불리움 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함 3. 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함 대표적인 최소 신장 트리 알고리즘 Kruskal's algorith..

1. 최단 경로 문제(Shortest Path Problem)란? 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 단일 출발 및 단일 도착(single-source and single-destination shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u에서 출발, 또다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발(single-source shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 예를 들어 A, B, C, D..

1. 탐욕 알고리즘(Greedy algorithm)이란? 최적의 해에 가까운 값을 구하기 위해 사용됨(완벽하게 최적의 해는 아님) 여러 경우 중 하나를 결정해야 할 때마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제 1 : 동전 문제 지불해야 하는 값이 4720원일 때 1원 50원 100원 500원 동전으로 지불하는 경우 중 동전의 수가 가장 적은 경우를 구하시오 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 생각하면 됨 def min_coin_count(value, coin_list): #value는 지불값 total_count = 0 details =..

문제 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 숫자가 쓰인 카드들이 N x M의 형태로 놓여있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 형태를 선택한다. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다 내 풀이 def card_game(height, width, card_list): min = 0 for i in..

1. 깊이 우선 탐색(Depth-First Search : DFS) (방향 상관없이) 자신과 연결된 노드의 가장 아래 레벨까지 내려가 탐색하고 그 노드가 리프 노드이면 상위 노드의 다른 리프 노드를 먼저 탐색하고 올라가는 방식 BFS와 탐색의 순서가 다르다 2. DFS 알고리즘 구현 자료구조 스택과 큐를 활용함 need_visit 스택과 visited 큐, 두 개의 자료구조를 생성 스택이기 때문에 pop_back()으로 앞이 아니라 뒤에 있는 데이터를 먼저 가져옴 BFS 자료구조는 두 개의 큐를 활용하고 DFS는 스택과 큐를 활용한다는 차이가 있음을 인지해야 한다 def dfs(graph, start_node): need_visit, visited = list(), list() need_visit.app..

1. BFS와 DFS 란? 대표적인 그래프 탐색 알고리즘(트리 - 사이클이 없는 그래프) 너비 우선 탐색(Breadth-First Search) : 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색(Depth-First Search) : 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 BFS 방식 : A - B - C - D - G - H - I - E - F - J 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회함 DFS 방식 : A - B - D - E - F - C - G - H - I - J 한 노드의 자식을 타고(왼쪽으로) 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회..

1. 그래프(Graph) 란? 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용 2. 그래프(Graph) 관련 용어 노드(Node) : 위치를 말함, 정점(Vertex)라고도 함 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨(link 또는 branch라고도 함) 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) 참고 용어 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (ex. 2차) 진입 차수(In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수 ..