[백준] 1707: 이분 그래프 (DFS) - JAVA

알고리즘 분류 (dfs)https://www.acmicpc.net/problem/1707  # 문제  # 필요개념이 문제를 풀기 위해서는 이분 그래프의 개념에 대해 먼저 이해해야한다. 개념 공부를 제대로 하지 않고 접근했다가 내 정답률만 잔뜩 낮춰버렸다 😇 그래서 개념 정리겸 블로그 작성 완료 ! 아래 링크를 걸어두었다https://wanna-developer02.tistory.com/191 [Data Structure] Bipartite Graph (이분 그래프) | 자바백준 문제를 풀다가 처음보는 자료구조를 정리하려고 한다. "이분" 이라는 단어가 들어가는 자료구조들이 꽤 있는 만큼, 개념을 헷갈리지 않게 정리하는 것도 중요하지 않나 싶다. 순서는 간단wanna-developer02.tistory...

[Data Structure] Bipartite Graph (이분 그래프) | 자바

백준 문제를 풀다가 처음보는 자료구조를 정리하려고 한다. "이분" 이라는 단어가 들어가는 자료구조들이 꽤 있는 만큼, 개념을 헷갈리지 않게 정리하는 것도 중요하지 않나 싶다. 순서는 간단하게 이분 그래프란 ?이분그래프의 탐색방법BFSDFS로 진행하려고 한다! * 이분 그래프의 개념과 글에 나온 이미지는 아래 글을 참고하였습니다 *https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html [알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development BlogStep by step goes a long way.gmlwjd9405.github.io1. 이분 그래프란 ?이분 그래프는 그래프 형태의 자료구조로, 인..

알고리즘 분류 (dfs)https://www.acmicpc.net/problem/1520   # 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아..

class 6https://www.acmicpc.net/problem/2533   # 문제페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데,  이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다.  친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로..

class 6https://www.acmicpc.net/problem/2357   # 문제N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.  # 예제입력 :  첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가..

백준 문제를 풀다가 정리하지 않은 자료구조가 나와서 정리하고자 글을 쓴다 ! 이번 주제는 세그먼트 트리이다.순서는 아래와 같다. 세그먼트 트리란?구현하기 (구간합을 예시로)생성데이터를 수정하게 된다면? * 세그먼트 트리의 개념은 아래를 참고하였습니다 *https://cano721.tistory.com/38 [알고리즘 개념] 세그먼트 트리(Segment Tree) / Java세그먼트 트리란 특정 구간 내 데이터에 대한 연산(쿼리)을 빠르게 구할 수 있는 트리. ex) 특정 구간 합,최소값,최대값,평균값 등등 Segment : 부분.분할.나누다.분할하다. 시간복잡도 데이터 변경:cano721.tistory.comhttps://book.acmicpc.net/ds/segment-tree 1. 세그먼트 트리?일반..

단계별 문제풀이 23단계 (동적계획법1)https://www.acmicpc.net/problem/11054   # 문제수열 S가 어떤 수 Sk를 기준으로 S1    > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.  # 예제입력 :  첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄..

단계별 문제풀이 (23단계)https://www.acmicpc.net/problem/2565   # 문제두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남..

알고리즘 분류 (dp)https://www.acmicpc.net/problem/2293   # 문제n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.  # 예제입력 :  첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.3 10125  출력 :  첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 10 # 필요개념n이 100 이하, k..

골드 5 문제집https://www.acmicpc.net/problem/1092   # 문제지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.  # 예제입력 :  첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나..