알고리즘181 [백준 2638] 자바 / 치즈 / bfs #문제 레벨: G3알고리즘: bfs 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2638#문제 풀이 1. 2변이상 접촉 시 1시간만에 다 녹음 2. 치즈 내부에 있는 경우에는 안 녹음3. 치즈가 다 녹는데 걸리는 시간은? 이 문제의 중심은 치즈의 안인지 밖인지 어떻게 판단할 것인지이다.처음엔 치즈 안 쪽을 표시해야겠다고 생각했다. 그러나 구현이 복잡해 보였다.(알고리즘 문제에서 구현이 복잡하면 웬만하면 올바른 방향으로 풀이되는 게 아님) 그래서 치즈 바깥 쪽을 표시하기로 결정했다. 치즈 바깥면을 구하는 건 bfs로 해결할 수 있다. 녹이기 전, 치즈 밖에 있는 (0,0)에서부터 bfs를 시작한다. 1을 만나면 airconta.. 2024. 7. 23. [백준 2458] 키 순서 / 자바 / dfs #문제 레벨: G4알고리즘: dfs 풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/2458#문제 풀이 자기가 간접적으로 지목(화살표)을 당해도, 간접적으로 지목(화살표)을해도 그 사람이 나보다 키가 작은지, 큰지 알 수 있다. 그래서 우리는 키 작은 사람을 지목하는 그래프 하나, 키 큰 사람을 지목하는 그래프 하나 두개를 만들어야 한다. 그 두 개의 그래프를 따로 따로 dfs하여 자기가 알 수 있는 학생의 수를 알아낸다. #풀이 코드 import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { static.. 2024. 7. 22. [백준 17471] 게리맨더링 / 자바 / dfs + bfs #문제 레벨: G3알고리즘: dfs + bfs 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/17471#문제 풀이 1. 지역을 나누는 조합을 구한다.2. 나눈 지역 조합 중 불가능한 조합이 있는지 확인한다.3. 이상이 없다면 차이를 구한다. 가능한 조합으로 나누려고 하니 아이디어 생각이 안 났다. 일단 효율을 포기하더라도 조합을 다 구한 후 그 조합이 가능한 조합인지 판별하는 것이 알고리즘 문제풀이에서는 효율적이라 생각한다.#풀이 코드 import java.io.*;import java.util.*;public class Main_17471_2 { static int N; static int peoples[]; // 구역별.. 2024. 7. 22. [백준 2178] 미로 탐색/ 자바 / bfs #문제 레벨: S1알고리즘: bfs풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/2178 #문제 풀이 bfs 문제의 기본 문제이다. queue와 visited[][]배열을 이용해서 길을 되돌아 가지도 않고 최단 거리를 찾을 수 있다. visited[][]배열을 쓰고 싶지 않다면 distance[][]배열에 해당위치에 도달하기 까지 걸린 이동횟수를 기입하면 된다. distance[][]에 0 이 아닌 숫자가 있다면 방문한 것이므로 해당 위치는 또 queue에 넣지않는다.(방문하지 않는다.) #풀이 코드 import java.util.*;import java.io.*;public class Main { static int N.. 2024. 7. 21. [백준 1655] 가운데를 말해요 / 자바 / 우선순위 큐 #문제 레벨: G2알고리즘: 자료구조 (우선순위 큐)풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/1655#문제 풀이 이 문제를 봤을 때 한 번에 떠올리는 아이디어로 한다면 시간초과가 날 것이다. 입력을 받을 때마다 정렬을 하고 중간값을 찾는 다는 생각은 오답이다. 배열 정렬의 최선의 시간복잡도는 O(n)이고 최악은 O(n^2)이다. 그래서 우리는 더 나은 정렬된 자료구조를 사용해야 한다. 그건 정렬의 특화된 우선순위 큐이다. 우선순위 큐 정렬(Heap정렬 사용)의 시간복잡도는 O(logn)이다.아이디어는 이러하다. 중간값보다 낮은 숫자들을 담을 maxHeap과 중간값보다 높은 숫자들을 담을 minHeap을 생성한다. maxHeap은.. 2024. 7. 20. [백준 14889] 스타트와 링크 / 자바 /dfs #문제 레벨: S1알고리즘: dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14889 #문제 풀이 dfs로 조합을 구한 후 조합이 완성될 때마다 답의 최솟값을 구하면 되는 쉬운 문제이다. 설명은 생략하겠다.#배운 점 dfs함수는 사람마다 구현하는 게 다 다르다. visited[] = true 순서이다. 재귀호출 전 true만들기 dfs(int i) { for (int j = i; j 재귀호출 후 첫 코드에서 true만들기 dfs(int i) { visited[] =true; for (int j = i; j 이것도 사고의 흐름이 편한대로 작성하면 될 것이다. 자기만의 d.. 2024. 7. 18. [백준 2573] 빙산 / 자바 / dfs #문제 레벨: G4알고리즘: dfs풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/2573 #문제 풀이 이 문제는 두가지를 구현하면 되는 문제이다.1. 빙산의 개수 카운팅 함수2. 빙산을 녹이는 함수하지만 난 보다시피 dfs가 간접적으로 빙하를 카운팅 하는데 도움을 주면서 빙하를 녹였다. 원래 내생각에는 한번 배열을 순회하는 김에 다 처리하자. 그게 성능상 이점을 가져갈 것 같다였다. 그러나 두가지 일을 동시에 하는 코드를 짜니 코드를 짜기 복잡했다.그래서 위에 쓴 과정처럼 논리의 흐름대로 코드를 짰다.#풀이 코드 import java.io.*;import java.util.*;public class Main { st.. 2024. 7. 17. [백준 13023] ABCDE / 자바 / dfs #문제 레벨: G5알고리즘:dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/13023 #문제 풀이 이 문제에 key point는 dfs 경로를 다양하게 탐색할 수 있느냐이다. 보통은 그래프에서 dfs를 사용할 때 연관된 노드들을 모두 방문한다에 포커스가 맞춰져 있다. 그러나 이 문제는 경로에 포커스가 맞춰져있다. 그래서 우리는 dfs 함수 중 boolean[] = false 이 부분을 잘 봐야 한다. 이것 덕분에 이전dfs 경로에서 탐색했던 노드들도 다시 탐색하게 되는 것이다.#풀이 코드 import java.io.BufferedReader;import java.io.IOException;import java.io.I.. 2024. 7. 16. [백준 9466] 텀 프로젝트 / 자바 / dfs + cycle #문제 레벨: G3알고리즘: dfs + cycle풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/9466#문제 풀이 본 유형은 나에게는 신유형이다. 보통 dfs라면 cycle를 돌지 않고 한 번 간 곳은 visited[] 배열로 방문하지 않는다. 그러나 이 문제는 done[] 배열을 만들어 두 번 순회하여 dfs를 마친다. 한 번 순회로 dfs를 마칠 수 있지 않나? (그럴 수도 있을 것 같긴 하다..) 그러나. 가볍게 이해하기 위해서는 dfs를 두 번 도는 것이 좋다. 한 번 돌 때는 연결고리를 만드는 과정이고 두 번 순회할 때는 cycle인지 판별하여 팀원인지 가려내기 위함이다. #풀이 코드 import java.io.Bu.. 2024. 7. 15. 이전 1 ··· 5 6 7 8 9 10 11 ··· 21 다음
