알루 코딩

차근차근 문제에서 주어진 로직을 풀어보면, 그다지 어렵지 않은 문제였다. 문제의 로직은 따로 설명하게 없을 정도로, 문제에서 주어진 대로 그대로 구현하면 다들 풀 수 있을 것이다. 처음 입력받는 N과 M은 각각 '주차장 공간의 수'와 '차량의 수'이다. 모든 차량은 한 번씩 주차장에 들어갔다가 나오므로 (차량의 수 *2) 만큼의 출입 순서를 입력받아야 했다. 우선 index오류를 막기 위해, '요금을 나타내는 리스트'와 '각 차량의 무게를 나타내는 리스트'를 빈 리스트 [] 가 아닌 [0]으로 시작했다. 들어오는 출입 순서를 덱으로 큐화 시켰다. popleft()를 쓰기 위함이다. 이 출입리스트가 빌 때 까지, 계산을 반복한다. 이 문제에서 생각해야 할 관건은 크게 2가지만 생각해주면 됐다. 주차 가능한..

신장 트리 : 신장 트리(Spanning Tree)란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하기 때문에, 이러한 그래프를 신장 트리라고 부르는 것이다. 예를 들어보자. 크루스칼 알고리즘 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장 트리를 찾아야 하는데, 이처럼 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '신장 트리 알고리즘'이라고 한다. 대표적인 신장 트리 알고리즘으로는 '크루스칼 알고리즘(Kruskal Algorithm)'이 있다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. 모든 간선에 대하여 정렬을..

최단 경로(Shortest Path) 란 ? : 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. '길 찾기' 문제라고도 불리는데, 다양한 유형이 있다. 예를 들어, "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우" 나 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우" 등이 있다. 보통, 최단 경로 문제는 그래프를 이용해 표현하는데, 각 지점은 그래프에서 '노드(node)'로 표현되고, 각 지점마다 연결된 도로는 그래프에서 '간선(edge)'으로 표현된다. 코딩 테스트에서는 보통 최단 경로를 모두 출력하는 문제보다는 '최단 거리'를 출력하는 문제가 많다. 학부 수준에서 다루는 최단 거리 알고리즘은 대표적으로 아래와 같다. 1. 다익스트라 알고리즘 2. 플로이드 워..

먼저, 꼭 필요한 자료구조의 기초에 대해 살펴보자. '탐색'이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 으로 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS 가 있는데, 이를 제대로 이해하려면, 먼저 스택과 큐에 대한 이해가 선수되어야 한다. 먼저, 스택(stack)을 살펴보자. 스택은 양동이에 물체를 넣는다고 생각하면 된다. 이러한 구조를 선입 후출(First In Last Out) 또는 후입 선출(Last In First Out),LIFO 구조라고 한다. 구조를 그림으로 그려보면 아래와 같다. 이를 파이썬 코드로 표현한다면, stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삭제() - 삽입(1) - 삽입(7..