알고리즘181 [백준 1707] 이분 그래프 / 자바 / dfs #문제 레벨: G4알고리즘: dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/1707#문제 풀이 이분 그래프가 뭔지 모르는 분들을 위해 설명하겠다. 형식상, 이분그래프의 정의를 먼저 보자면 "모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.".그림으로 더 쉽게 이해해보겠다.1노드를 빨간색이라고 하면 그에 인접한 노드들은 모두 블루여야 한다. 그렇다면 3번 노드는 블루이기 떄문에 3번 노드에 인접한 노드들은 모두 레드여야 한다.만약 아래 그림과 같이 4번 노드가 b라면, 3번 4번이 인접한데 같은 색상이므로 이분 그래프가 아니다.이제 이해가 되는가? 그러면 우리가 코드.. 2024. 7. 13. [백준 2533] 사회망 서비스 / 자바 / dp + dfs #문제 레벨: G3알고리즘: dp + dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/2533#문제 풀이 dp와 dfs를 섞은 문제이다. 이 문제에서 얻을 수 있는 점은 두가지이다.첫 째, 그래프를 배열로 표현하는 것. 둘 째, 큰 문제를 작은 문제로 쪼개는 방법.셋 째, vistied배열 대신 parentNode로 판별하는 방법(중복 탐색 예방)넷 째, dp 구현방식위 문제는 dp[node][0], dp[node][1]를 가지는 이차원 배열로 풀어내야 한다. 가장 아래에 있는 리프 노트부터 시작하여 루트 노드의 dp 값을 채우는 방식이다. 예를 들면 dp[5][0] 은 노드 5가 얼리어답터가 아닐 때이다. 그러니 반드시 부모(.. 2024. 7. 11. [백준 1937] 욕심쟁이 판다 / 자바 /dp #문제 레벨: G3알고리즘: dp풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/1937#문제 풀이 위 문제를 순수 dfs 코드로 풀면 O(n x n x n x n)입니다. 값을 대입해보면 500 x 500 x 500 x 500 = 625억입니다. 시간제한은 2초이므로 2억 초과인 625억은 시간제한 초과입니다. 특별한 규칙이 없으니 dfs임은 확실하고 시간복잡도를 줄이기 위해서 dp를 도입해야 합니다. dp를 도입한다는 것은 이미 방문한 경로는 반복해서 가지 않는 것을 의미합니다. 그럼 각 배열을 한 번씩만 방문하면 되기 때문에 시간 복잡도는 O(n x n)입니다. 이만 오천으로 넉넉히 통과할 수 있습니다. (한 번씩만 방문하면 되므로.. 2024. 7. 10. [백준 11066] 파일 합치기 / 자바 /dp #문제 레벨: G5알고리즘: dp 풀이시간: 1힌트 참조 유무:https://www.acmicpc.net/problem/11066#문제 풀이 그리드 문제로도 착각할 수 있지만 연속된 파일들만 합칠 수 있기 때문에 그리드 문제는 아니다. (그리드 문제라면 파일을 합치고 정렬하고 합치고를 반복하기 때문에 연속된 파일임을 보장하지 않음) dp[i][j] = i ~ j까지 파일 합쳤을 때 최솟값+행은 시작인덱스를 나타내고 열은 끝인덱스를 나타낸다.{2,3}이면 2에서부터 3까지 더했을 때 최솟값이다. dp 배열을 이 방향으로 채워진다. 빨간색 숫자는 채워지는 순서를 뜻한다. 아래 코드르 보면 알겠지만 이중 for문이 뜻하는 것은 파란색 방향을 말하는 것이다.가장 깊숙히 있는 fo.. 2024. 7. 10. [백준 14002] 가장 긴 증가하는 부분 수열4 / 자바 / dp #문제 레벨: G4알고리즘: dp풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14002#문제 풀이 [1번째 시도: 실패]멍청한 풀이. 시간복잡도 n으로 풀 수 있지 않을까? 그리드 형식으로 랭킹을 매기는 방식. 혹시 나와 같은 사람이 있을까봐 기입해두었다. skip해도 된다.package project;import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(.. 2024. 7. 10. [백준 17070] 파이프 옮기기1 / 자바 / dp #문제 레벨: G5알고리즘: dp 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/17070#문제 설명 문제에서 놓칠 수도 있는 부분 몇 가지만 짚고 넘어가겠습니다.1. 파이프는 90~180도까지 +45도 or -45만 움직일 수 있다.2. 대각선 파이프는 4칸을 차지한다. 그 4칸 중 벽(1)이 있으면 안 된다. 이 문제는 dfs 또는 dp로 풀 수 있습니다. dfs로 풀 수 있는 이유는 입력최대값이 작아서 그렇습니다. 저는 dp를 공부중이기 때문에 dp를 사용해서 풀겠습니다. #알고리즘 설명 dp를 알려면 이 유형은 꼭 알아두었으면 좋겠습니다. 이 문제에서 어떻게 dp를 이용하냐면, 각 위치에 도착할 수 있는 경우의 수를 담는 것입니.. 2024. 7. 10. dp 뿌시기 1(feat 양치기) 이 글은 고급 알고리즘인 dp의 이해를 위해 작성하였습니다. 다른 알고리즘 같은 경우 설명과 코드를 보면 이해가 단 번에 이해가 갔지만, dp의 경우에는 일반적 사고와는 달라 이해하기 쉽지 않았습니다. 이를 위해 dp의 다양한 유형을 분석하므로써 dp의 사고흐름을 정확히 이해하기 위해 작성하였습니다. 아래 문제들은 백준 골드 정도 되는 문제들로 구성되어있습니다. 문제풀이에서 가장 중요한 건 어떤 알고리즘인지 파악하는 게 중요하기 때문에 dp문제라는 것을 미리 알고있지만, 문제를 처음 보았을 상황을 가정해서 dp 문제풀이를 해보도록 하겠습니다. 또, 하나 dp의 사고과정을 위해 작성한 글이기 때문에 코드를 직접 작성하지 않겠습니다. #1번째 문제: 백준10942 팰린드롬?https://www.acmic.. 2024. 7. 9. [백준 2565] 전깃줄 / 자바 / dp + LIS 문제 레벨: G5알고리즘: dp + LIS 풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/25651 번째 시도 [알고리즘 설명]이 문제는 최장 증가 부분 수열(LIS: Longest Increasing Subsequence) 알고리즘을 사용하여 해결할 수 있습니다. 전깃줄이 교차하지 않으려면, B 전봇대의 연결 위치가 증가하는 순서여야 합니다. 따라서 LIS를 찾으면 교차하지 않는 최대 전깃줄의 개수를 알 수 있고, 전체 전깃줄 개수에서 이를 뺀 값이 제거해야 할 최소 전깃줄의 개수가 됩니다. 시간복잡도 O(n^2) 코드import java.util.*;import java.io.*;public class Main { public s.. 2024. 7. 8. [백준 2096] 내려가기 / 자바 / dp + 슬라이딩 윈도우 문제 레벨: G5알고리즘: dp + 슬라이딩 윈도우 풀이시간: 1시간힌트 참조 유무: 유 https://www.acmicpc.net/problem/20961 번째 시도 [알고리즘 설명]위 방식을 어떻게 dp 로 구현하지? 아무리 생각해도 작은 문제를 해결해서 위 문제를 해결하지 못할 것 같은데 ?1줄만 있는 경우 -> 2줄만 있는 경우 - > 3줄만 있는 경우 이런 식으로 업데이트 해도 조건이 달라질 때마다 경로가 달라지는데?=> dp[]의 각 원소를 각 줄의 최적값으로 생각하지 말고, 한 줄의 세 숫자의 최적값으로 생각하자.위 고민들을 dp[] size = 3배열로 해결할 수 있다. 나는 최소, 최댓값을 구하기 위한 경로에 집착했다. 관점을 달리해 매줄 마다 세 개의 숫자에 지난 줄.. 2024. 7. 8. 이전 1 ··· 6 7 8 9 10 11 12 ··· 21 다음
