dfs45 [자바] 백준 24479 - 알고리즘 수업 - 깊이 우선 탐색 1 (boj java) 문제 : boj24479 단순한 dfs 문제로 보이겠으나, 문제는 '오름차순' 부분이다. 이걸 위해 인접 행렬로 간선을 저장할 경우 O(N^2)이 필요하므로 시간초과가 나게 될 것이다. 그러니 인접 리스트로 간선을 표현하는게 좋고, 미리 오름차순으로 각 정점의 간선들을 정렬시켜두면 이 문제에서는 인접 행렬의 경우보다 시간도 덜 들고 메모리도 덜 들어 더 효율적으로 짤 수 있다. 위의 전처리 이외에는 기본 DFS로 구현하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.Stri.. 2022. 5. 18. [자바] 백준 25195 - YES or yes (boj java) 문제 : boj25195 그래프 탐색에 대해 단순하게 DFS, BFS만 익힌게 아니고 이해하고 있다면 사실 엄청 쉬운 문제이다. 결국 DFS(깊이 우선 탐색)으로 진행하면서 팬을 만나지 않고 더이상 진행할 간선이 없는 곳에 도착하는지만 보면 된다. 주의할 점은 방문체크를 두면 안된다. 왜냐면 이미 팬을 만난채로 진행한 경로라서 방문체크가 됬더라도 팬을 만나지 않은채로 진행이 가능해야 하기 때문이다. 이럼 사실 방문체크를 하되, 팬을 만나고 도착했는지 팬을 안만나고 도착했는지에 따라 dp를 좀 끼얹어서 그래프 탐색을 해도 되긴한다. 근데 어차피 DAG(Directed Acyclic Graph. 사이클 없는 방향그래프)이므로 팬을 만났다면 바로 back tracking으로 이전으로 돌아가기만 해도 된다. 이.. 2022. 5. 16. [자바] 백준 5670 - 휴대폰 자판 (boj java) 문제 : boj5670 너무 대놓고 Trie 써야할것같이 생긴 문제였다. 사실 플래라곤 하지만 Trie 자료구조를 알고 있다면 별 문제 없이 풀 수 있는 기본 형태의 문제이다. 예를들어 'hello, hell, heaven, goodbye'를 Trie에 담아보면 다음과 같이 생겼다. 다음과 같이 소문자 하나씩 트리 구조로 유지하는 형태의 자료구조이다(주황색은 단어의 끝이 존재함을 의미한다.). 문자열 쪽으론 유명한 알고리즘이라 검색해보면 엄청 많이 나온다. 그럼 로직을 다음과 같이 구현하면 된다. 1. N개의 단어를 Trie 자료구조에 넣는다. 2. N개의 단어를 Trie 자료구조에서 찾으면서 주어진 조건에 따라 몇 번의 입력이 필요한지 센다. 3. '2'를 전부 더한다. 좀 더 효율적으로 하려면 1. .. 2022. 4. 27. [자바] 프로그래머스 - 타겟 넘버 (코딩테스트 연습 Lv2) 문제 : Programmers-타겟넘버 결국 주어진 numbers를 순서대로 + 한번, - 한번씩 모든 경우를 구해보면 된다. 이 경우 O(2^n)이 된다(+,-의 2가지 경우를 n번 봐야 하므로). 예를들어 numbers가 [1, 2, 3]일 경우 다음과 같이 진행된다. 이 중 target과 동일한 경우를 세서 return해주면 된다. 코드 : github /** * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges */ class Solution { int cnt = 0; private void rec(int[] numbers, int target, int idx, int sum) { if (idx == numbers.length.. 2022. 4. 18. 백준 1707 자바 - 이분 그래프 (BOJ 1707 JAVA) 문제 : boj1707 '그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.' 무슨말이냐면, 정점을 두개의 그룹으로 나눴을 때, 해당 그룹끼리는 간선이 없도록 나눌 수 있으면 이분 그래프라는 얘기이다. 아래의 그림을 보면 바로 이해가 될 것이다. 1,2,3은 이분 그래프를 그려봤다. 4는 이분 그래프가 아닌 경우이다. 즉, 어떻게든 2 종류의 정점으로 나눌 때 간선 연결된 것 끼리 같은 종류만 아니면 된다 (4번의 경우 노란 정점 둘이 간선이 연결되었으므로 이분 그래프가 아니다. 그리고 다른 방식으로 2종류로 나눠도 모두 마찬가지로 이분 그래프가 될 수 없다.). 또 .. 2022. 3. 22. 백준 1035 자바 - 조각 움직이기 (BOJ 1035 JAVA) 문제 : boj1035 처음엔 그리디로 풀어보려 했지만, 별다른 규칙을 찾지 못했다. 와중에 생각해보니 어차피 5x5 밖에 안되고, 조각은 최대 5개 이므로 최악의 경우라도 O(25^5*25*5) 정도로 풀 수 있다. 25^5는 5x5 크기의 보드에 5개의 조각을 모든 위치에 놓는 경우의 수이고, 해당 경우의 수에 대해 *25는 그 중 하나의 조각을 찾는 것이고, *5는 5개가 인접해있는지 확인하는 것이다. 저대로는 당연히 불가능하지만, 여기에 백트래킹을 더해서 이미 나왔던 최소 이동 횟수 이상이라면 해당 경우의 수와 그 이후의 경우의 수를 중간에 중지하는 방식으로 진행한다면 어느정도 가능할 것 같아서 일단 해봤다. 참고로 이 경우 모든 경우의 수는 조각이 n개 있었다면 다음과 같이 확인하면 된다. 1... 2022. 3. 21. 백준 6186 자바 - Best Grass (BOJ 6186 JAVA) 문제 : boj6186 상하좌우로 인접한 풀때기들의 군락(?) 수만 잘 구하면 된다. 그러니 일단 입력받고, 방문체크 하면서 dfs 돌리며 수를 세면 쉽게 구할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void dfs(int r, int c, boolean[][] arr) { for (int dr = -1; dr 2022. 3. 12. 백준 1765 자바 - 닭싸움 팀 정하기 (BOJ 1765 JAVA) 문제 : boj1765 1. '내 친구의 친구는 내 친구' + '내 원수의 원수도 내 친구' 이걸 해석은 명확히 해야한다. 우선 '내 친구의 원수'에 대한 내용은 없으니 신경쓸 필요가 없다. 그리고 '내 친구의 친구는 내 친구' 라고 했으니 내 친구라면 쭉쭉 이어나가면서 친구를 찾을 수 있음을 알 수 있다. '내 원수의 원수도 내 친구' 부분이 문제인데, 원수의 원수의 원수 이런건 생각할 필요가 없다. 딱 두 단계에 걸친 원수사이면 친구라는 말이다. 또한 첫 번째 조건과 합쳐져서, 원수의 원수의 친구 또한 내 친구이다! 원수의 원수의 친구의 친구 또한 내 친구이다! 좀 헷갈릴 수 있는데 그냥 주어진 조건 2개에 대해 여러 경우를 생각해보면 저렇게 된다. 정리해보면 - 내 원수 -> 그냥 원수임 - 내 원.. 2022. 3. 7. 백준 16936 자바 - 나3곱2 (BOJ 16936 JAVA) 문제 : boj16936 난이도 기여 멘트들을 보니 많은 분들이 ad hoc으로 보고 수학적으로 푼 것 같다. 3의 차수라는 내용이 많이 나오던데 솔직히 뭔지 잘 모르겠다 ㅋㅋ. 내 경우엔 수학적으로 잘 모르겠으니 그냥 무식하게 풀었다. 각 수를 하나의 정점으로 치고, 방향 그래프를 만든다. 만약 두 수 X, Y가 있고 X*2 == Y 혹은 X/3 == Y 라면 X->Y 처럼 X에서 Y로 가는 간선을 만든다. 예를들어 '예제 입력 1'에 대한 방향 그래프는 다음과 같다. 이렇게 모든 쌍에 대해 간선을 만들고 (모든 쌍이라고 해봐야 100x100개 뿐임), 모든 정점에서 출발해서 DFS를 돌린다. 어떠한 지점에서 DFS를 통해 모든 정점에 갈 수 있다면 해당 루트를 출력해주면 된다. 여기서 좀 더 효율적으.. 2022. 2. 23. 백준 18126 자바 - 너구리 구구 (BOJ 18126 JAVA) 문제 : boj18126 N이 최대 5000이고, 간선도 각 노드마다 최대 5000개 이므로 O(N^2)으로만 해도 충분하다. 따라서 그냥 dfs로 모든 경우를 확인하고, 그 사이에 나온 거리들 중 가장 큰 값을 출력하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; class Edge { int to, c; public Edge(int to, int c) { this.to = to; this.c = c; } } public class Main { long answer = 0; int n; Arra.. 2022. 2. 8. 이전 1 2 3 4 5 다음
