DFS도 재귀보다는 반복문으로 구현 연습하기1

DFS도 재귀보다는 반복문으로 구현 연습하기1

1. 문제 1987번: 알파벳 (acmicpc.net) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 2. 풀이1 기본적인 DFS문제긴한디 분명히 맞는데 시간초과에 애먹었다.. from sys import stdin def dfs(x,y,s): global answer for i in range(4): dx = x + d[i][0] dy = y + d[i][1] if dx >= 0 and dx = 0 and dy = 0 and dx = 0 and dy = 0 and dx = 0 and dy = 0 a..

  • format_list_bulleted 알고리즘/DFS BFS 정복기
  • · 2023. 8. 19.
  • textsms
Binary Lifting을 이용한 개선된 최소 공통 조상(Lowest Common Ancestor) 구하는 방법 배우기2

Binary Lifting을 이용한 개선된 최소 공통 조상(Lowest Common Ancestor) 구하는 방법 배우기2

https://www.youtube.com/watch?v=O895NbxirM8 https://kibbomi.tistory.com/201 최소 공통 조상 (LCA, Lowest Common Ancestor)(C/C++) 여러 자료를 참조하면서 LCA를 공부했는데, 어떤 자료는 너무 쉽고 깔끔하지 못하고, 어떤 자료는 난이도가 있고 깔끔하게 설명된 자료였습니다. 그래서 여러 자료를 찾아보며 이해하고, 또 이해 kibbomi.tistory.com 1. 문제 11438번: LCA 2 (acmicpc.net) 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다..

  • format_list_bulleted 알고리즘/그래프 이론 정복기
  • · 2023. 8. 13.
  • textsms
최소 공통 조상(Lowest Common Ancestor,LCA)문제 기본 해법 배우기1

최소 공통 조상(Lowest Common Ancestor,LCA)문제 기본 해법 배우기1

https://www.youtube.com/watch?v=O895NbxirM8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=15   https://www.crocus.co.kr/660 LCA(Lowest Common Ancestor) 알고리즘LCA(Lowest Common Ancestor) 알고리즘이란? LCA 알고리즘이란 영어 해석 그대로 최소 공통 조상을 찾는 알고리즘이고, 두 정점 u, v(혹은 a, b)에서 가장 가까운 공통 조상을 찾는 과정을 말한다. 예를들어www.crocus.co.kr https://kibbomi.tistory.com/201 최소 공통 조상 (LCA, Lowest Common Ancestor)(C/C++)여러 자료를 참조하면서 LCA를 공..

  • format_list_bulleted 알고리즘/그래프 이론 정복기
  • · 2023. 8. 7.
  • textsms

2차원 배열에서 경로의 개수 구하기 - 최단 경로가 아닌 경우

1. 문제 1520번: 내리막 길 (acmicpc.net) 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 2. 풀이 이 문제에서 핵심은 "어떤 칸을 최초 방문할 때 해당 칸에서 목적지까지 도달할 수 있는 경우의 수에 대한 정보를 기록해 놓고, 다음 방문 시 기록된 값을 참조해서 반복된 연산을 피하는 것이다" dp[y][x]를 (x,y)에서 (n-1,m-1)까지 조건에 맞는, 도달하는 경우의 수라고 정의하자. m,n = map(int,stdin.readline().split()) maps = [list(map(in..

  • format_list_bulleted 알고리즘/다이나믹 프로그래밍
  • · 2023. 2. 19.
  • textsms

DFS 재활훈련 - return이 있는 DFS 작성하기 연습 + 트리의 경로 유일성 배우기

1. 문제1 13023번: ABCDE (acmicpc.net) 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 2. 풀이 A는 B의 친구이다 B는 C의 친구이다 C는 D의 친구이다 D는 E의 친구이다 이 말은 무슨말일까? A에서 시작해서 B로 가고, B에서 C로 가고 C에서 D로 가고 D에서 E로 갈 수 있는 경우가 존재하는지 아닌지를 판단하라는 말 주어진 그래프에서 DFS 탐색으로 깊이 4까지 갈 수 있다면 1을 return하면 될 것 깊이가 4이면 1을 return하고.. 깊이가 4가 아니면.. 탐색을 수행 현재 방문하는 점 x에 대한 방문처리 visited[x] = 1 x와 연결된 점 graph[x]에서 순회해..

  • format_list_bulleted 알고리즘/DFS BFS 정복기
  • · 2023. 2. 13.
  • textsms

BFS 최단경로 역추적하는 방법 배우기

1. 문제 24463번: 미로 (acmicpc.net) 24463번: 미로 첫 번째 줄에는 미로의 크기 $N, M$이 주어진다. $(3 \le N, M \le 2,001$, $N, M$은 홀수$)$ 두 번째 줄부터는 미로의 정보가 주어진다. 두 번째 줄부터 $N$줄에 거쳐 각 줄에는 길이가 $M$이고 .과 +만으로 이 www.acmicpc.net 입구에서 출구로 가는데, 최단 경로가 아닌 경로는 모두 @로 바꿔서 표시하는 문제 2. DFS 풀이 최단 경로가 아닌 경로를 찾는게 그냥 찾을려하면 생각보다 까다롭다 아이디어의 핵심은 이동할 수 있는 모든 위치 .을 먼저 @로 바꿔놓는다 n,m = map(int,stdin.readline().split()) maze = [list(stdin.readline()...

  • format_list_bulleted 알고리즘/DFS BFS 정복기
  • · 2023. 2. 7.
  • textsms