문제 NxM 크기의 격자 미로 안에서 출발지 (x, y)에서 도착지 (r, c)로 가는 경로를 알파벳으로 표기했을 때, 사전 순으로 가장 빠른 경로를 찾는 문제이다. 미로를 탈출하는 데에는 조건이 있다. 격자 밖으로 나갈 수 없음 출발지에서 도착지까지의 총 이동거리는 k여야 함. (이동거리 == 이동 횟수 == 경로 문자열 길이) 출발지와 도착지를 포함하여 두 번 이상 방문 가능 경로 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 함 경로를 문자열로 바꿀 때는 다음과 같이 바꿀 수 있다. l : 왼쪽 이동 r: 오른쪽 이동 u: 위쪽 이동 d: 아래쪽 이동 풀이 깊이 우선 탐색(DFS) 알고리즘을 활용하여 경로를 찾을 수 있다. DFS 알고리즘은 LIFO(Last In First Out)의 특징을 갖고..
문제 모눈종이 위에 k개의 직사각형을 그릴 때, 직사각형이 그려지지 않은 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 m = 5, n = 7 인 모눈종이 위에 3개의 직사각형을 그렸을 때, 다음과 같이 3개의 영역으로 나누어질 수 있다. 각각의 넓이는 1, 7, 13이다. 이와 같이 직사각형에 포함되지 않는 분리된 영역의 각 크기를 오름차순으로 출력하는 문제이다. 풀이 먼저 주어진 직사각형을 모눈종이 영역에 표시한다. 이때 본 문제에서는 상하좌우 방향을 유의해야 한다. 여기서는 직사각형이 차지하는 공간이 중요한 부분임으로 임의로 row를 m, col를 n으로 보고, 왼쪽 아래 꼭짓점의 x1, y1좌표값과 오른쪽 위 꼭짓점의 x2, y2좌표값을 왼쪽 위, 오른쪽 아래로 가정하였다. (편의상 상하..
인접한 노드(정점)끼리 서로 다른 색으로 칠해서 두 가지 색으로 분할할 수 있는 그래프를 이분 그래프라고 한다. 즉 각각의 집합에 속한 노드끼리는 서로 인접하지 않도록 분할하는 것이다. 시간복잡도: O(V+E) 1. 이분 그래프 알고리즘 BFS, DFS 를 사용하여 이분 그래프인지 여부를 확인 가능하다. 판단 방법 서로 인접한 노드가 같은 색이면 이분 그래프가 아니다. BFS, DFS로 노드를 방문할 때마다 두 가지 중 한가지 색으로 칠한다. (1 혹은 2) 이때 인접한 노드와는 서로 다른 색을 선택한다. 즉, 현재 노드의 색(1)과는 다른 색(2)으로 연결된 다음 노드를 칠한다. 여기서 0은 방문하지 않음을 뜻하고 1 혹은 2는 서로 다른 색을 뜻한다. $color_{next}= color_{befor..
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 이분탐색
- Prefix sum
- 알고리즘
- 우선순위큐
- greedy
- 분리집합
- 수학
- pytorch
- disjoint set
- 이분 그래프
- DP
- 백준
- dfs
- 파이썬
- python
- 구현
- boj
- 트랜스포머
- 코딩테스트실력진단
- lis
- bipartite graph
- COLAB
- Look-ahead Mask
- Transformer
- 누적합
- padding mask
- 코드트리
- 그리디
- 1202
- Algorithm