알루 코딩

오늘은 matrix 와 관련한 문제를 가져와봤습니다.해당 문제는 Hard 라고 표기되어 있지만, Medium 정도의 난이도로 잘 생각한다면 코드는 길어져도 풀 수 있는 문제입니다.문제 설명리트코드 2392번 Build a Matrix With Conditions 문제는 주어진 조건에 따라 k * k 행렬을 구성하는 문제입니다. 행과 열에 대한 조건이 주어졌을 때, 각 숫자가 주어진 순서에 맞게 매트릭스에 배치되어야 합니다.각 조건은 '[a,b]' 형태로 주어지며, rowConditions 에서는 숫자 'a'가 숫자 'b'보다 윗 행에 위치해야 하고, colConditions 에서는 숫자 'a'가 숫자 'b'보다 왼쪽 열에 위치해야 함을 의미합니다. 나머지 행렬위치에는 0으로 채우면 됩니다. 만약 만족하는..

이 문제는 전형적인 bfs,dfs 문제입니다. 문제 설명을 간단히 하자면, 주어진 image 그래프에서 (sr, sc) 위치에서부터 시작해 상,하,좌,우 4방향을 탐색하면서 image[sr][sc]와 값이 같다면, 해당 자리를 color 값으로 치환하는 문제입니다. 간단히 말해서, 시작하는 위치와 값이 같으면서 연결된 자리를 color 값으로 바꾸면 됩니다. 먼저, 코드를 살펴보면서 설명을 해보겠습니다. import copy class Solution(object): def floodFill(self,image, sr, sc, color): """ :type image: List[List[int]] :type sr: int :type sc: int :type color: int :rtype: List[L..

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

'DFS/BFS'와 '최단 경로'에서 다룬 내용도 그래프 알고리즘의 한 유형으로 볼 수 있다. 그래프 알고리즘은 코딩 테스트에서 출제 비중이 낮은 편이지만, 출제되기 때문에 기타 그래프 알고리즘도 살펴볼 필요가 있다. 지금부터 다룰 알고리즘은 앞서 배운 내용에 기반하는데, 예를 들어 크루스칼 알고리즘(Kruskal Algorithms)은 그리디 알고리즘으로 분류되고, 위상 정렬 알고리즘(Topology Algorithms)은 앞서 배운 큐 자료구조 혹은 스택 자료구조를 활용해야 구현할 수 있다. 복습을 해보자면, 그래프란 노드와 간선의 정보를 가지고 있는 자료구조이고, 알고리즘 문제에서 '서로 다른 개체가 연결되어 있다'는 얘기가 있다면 가장 먼저 그래프 알고리즘을 떠올려야 한다. 더불어, 그래프 자료구..

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