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를 ..
1. 문제 그래프의 정점의 집합을 둘로 분할하는데 각 집합에 속하는 정점끼리는 서로 간선이 존재하지 않도록 분할하고 싶다. 이것이 가능한지를 판별하는 프로그램을 작성해본다면? 2. DFS 알고리즘 무방향 그래프라고 가정함 어떤 정점을 방문하면서 방문한 정점에 그룹 1을 할당 인접한 정점을 순회하면서, 인접한 정점이 방문하지 않은 정점이면 그룹 -1을 할당하고 방문 하지만 인접한 정점이 이미 방문한 정점이라면, 현재 정점의 그룹(현재 그룹이 할당됨)과 이미 방문한 정점(이미 그룹이 할당됨)이 서로 같은 그룹이면 이분 그래프가 아니다 3. 예를 들어서 생각해보기 다음과 같은 그래프가 이분 그래프인지 생각해보자 임의의 정점 아무거나 하나를 선택하고 방문을 시도 방문하면서 파란색을 부여한다 현재 방문한 정점과 ..
1. 문제 1861. 정사각형 방 ttps://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE&problemTitle=정사각형+방&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 $n^{2}$개의 방이 $N*N$ 형태로 늘어서있고, 각각은 1부터 $n^{2}$이하까지 전부 서로 다른 수로 순서와 무관하게 적혀있다. 어떤 방에 있을때, 정확히 현재 방보다 1 더 큰 수가 적힌 방으로만 이동할 수 있다고 할때, 처음에 어떤 수가 ..
1. 기본 스택 구현 방문배열 visited 초기화 첫 시작정점 v를 방문 처리 그 후 탐색 반복문 수행 v에 인접한 정점 w중에서 아직 방문하지 않은 w를 찾으면, 이미 방문한 v를 스택에 넣고 v를 w로 교체한 후에, w를 방문처리하고 바로 break 그 후 다시 w에 인접한 정점중에서 방문하지 않은 정점을 찾으면, w를 스택에 넣고 새로운 정점으로 교체한 뒤에 방문처리하고 반복 수행 더 이상 방문할 곳이 존재하지 않는다면 스택이 비어있는지 검사한다 스택이 비어있다면, 전체 탐색을 종료 스택이 비어있지 않다면, 하나씩 pop하여 다시 인접한 정점중에서 방문하지 않은 정점이 존재하는지 탐색 수행 visited = [0] * n def dfs(v,visited): visited[v] = 1 stack =..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
