potato's devlog

👉 문제 링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 🧑🏻‍💻 문제 풀이 이분그래프 이면 1, 이분그래프가 아니면 -1를 flag에 저장해주었다. 정점은 각각 1과 -1로 구별해주었다. 만약 인접한 정점이 둘다 1이거나, 둘다 -1이라면 이건 이분그래프가 아닌거다! 이 값들은 visited 에 넣어주었다. 아래 코드는 main으로 돌아가는 부분이다. 차례대로 설명을 작성해보자면 처음 입력받는 K 만큼 result가 출력되어야 하므로 모..

🙋🏻‍♀️ 이분그래프 위 사진처럼 그래프가 '두개의 색'으로 표현되는 것을 이분그래프라고 한다. 빨간정점과 검은정점 두 그룹으로 나뉘었는데, 같은 그룹끼리는 인접하지 않아야한다. 즉, 그래프의 모든 정점이 두 그룹으로 나뉘어지고 서로 다른 그룹의 정점만이 간선으로 연결된 그래프를 말한다. 👻 이분그래프의 특징 이분 그래프인지 확인하기 위해서는 BFS와 DFS 탐색 방법을 이용할 수 있다. DFS와 BFS를 통해서 그래프를 탐색하게 되면, 같은 depth에 있는 정점은 같은 색을 갖게 되는 것이다. 연결 요소의 개수를 구하는 방법과 유사하다. 모든 정점을 방문해서 검사하기 때문에 시간복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다. 🧑🏻‍💻 이분그래프인지 확인해보는 방법 ⚠️ 주의사항: 서로 인접한 정..

문제 링크 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 풀이 https://didu-story.tistory.com/98 [알고리즘] 탐색 알고리즘 DFS, BFS -- 본 포스팅은 이것이 취업을 위한 코딩 테스트다 with 파이썬 책을 참고하여 작성되었습니다. 1. DFS Depth First Search, 깊이 우선 탐색 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘 주로 스 didu-sto..

최장 증가 부분 수열 (LIS,Longest Increasing Subsequence) 이란? 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 "최장 증가 부분 수열"이라고 한다. - 나무위키 🌳 ▷ 예시를 들어보자. [ 3, 5, 7, 9, 2, 1, 4, 8] 다음과 같은 수열이 있다고 하자. 이 수열에서 몇 개의 수를 제거해서 부분수열을 만들 수 있다. 몇 개의 수를 제거해서 오름차순으로 이루어진 수열을 최장 증가 부분 수열이라고 하였는데, 즉, '공차'가 존재하지 않아도 부분수열이라고 본다는 것이다. (규칙적이지 않고 오름차순이면 된다는 뜻) 따라서 위 수열에서 도출될 수 있는 부분수..