본문 바로가기

알고리즘182

[백준 1717] 집합의 표현 / 자바 / 자료구조(유니온 파이든) #문제         레벨: G5알고리즘: 자료구조(유니온 파이든) 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1717#문제 풀이        이 문제는 "Disjoint Set(분리 집합)" 또는 "Union-Find" 알고리즘을 사용하여 효율적으로 해결할 수 있다.유니온 파인드 자료구조는 자기의 부모를 기록하는 것이다. 위 그림에서 2와 3이 같은 집합인지 알려면 최상위 부모가 같은지 확인 하는 거다. 집합을 추가하는 방법은 또 그림으로 설명하겠다. 3과 6이 같은 집합인 걸 알고 집합을 추가할 때, 6의 최상위 부모인 7과 3의 최상위 부모인 1를 자식-부모 관계로 만들면 된다. 1을 자식으로 두던 7을 자식으로 두던 그건 구현하는 사람 마음이다.#.. 2024. 8. 26.
[백준 9095] 1, 2, 3 더하기 / 자바 / dp #문제         레벨: S3알고리즘: dp풀이시간: 30분 힌트 참조 유무:https://www.acmicpc.net/problem/9095#문제 풀이        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이와 같은 점화식이 세워진 이유는 이러하다. dp[4] = dp[3] +  dp[2] + dp[1] 를 예시로 들어 설명해보겠다.         dp[1] = 1;  // 1         dp[2] = 2;  // 1+1, 2         dp[3] = 4;  // 1+1+1, 1+2, 2+1, 3dp[4]는 dp[1] 마지막에 3을 붙이면 되고 dp[2] 마지막에 2를 붙이면 된다. dp[3] 마지막에 1를 붙이면 된다.1+31+1+2, 2+21+1+1+1, 1+2+1,.. 2024. 8. 25.
[백준 1149] RGB거리 / 자바 / dp(기본) #문제         레벨: S1알고리즘: dp(기본)풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/1149#문제 풀이        위 문제느 dp 기본 문제이다. 점화식을 도출하고 그를 코드로 구현하는 것이다. 위 문제의 점화식은 아래와 같다.             // 빨강으로 칠할 경우             dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + costs[i][0]            // 초록으로 칠할 경우             dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + costs[i][1]            // 파랑으로 칠할 경우             dp[i][2].. 2024. 8. 23.
[백준 1275] 커피숍2 / 자바 / 자료구조(세그먼트 트리) #문제         레벨: G1알고리즘: 자료구조(세그먼트 트리) 풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/1275#문제 풀이        위 문제는 세그먼트 트리의 전형적인 문제이다.https://jsw5913.tistory.com/208 [백준 2243] 사탕상자 / 자바 / 자료구조(세그먼트 트리)#문제         레벨: P5알고리즘: 세그먼트 트리풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2243#문제 풀이         위 문제는 2가지로 구현할 것이다.위 문제를 봤을 때 가장 직jsw5913.tistory.com위 글을 보고 오면 이해하기 쉬울 것이다.#풀이 코드      import java.i.. 2024. 8. 22.
[백준 16988] Baaaaaaaaaduk2 (Easy) / 자바 / 구현 + bfs #문제         레벨: G3알고리즘; bfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/16988#문제 풀이         문제를 보는 순간 규칙이 없고 완전탐색(브루트 포스)로 해결해야겠다고 생각이 들었다. 시간복잡도를 구해보자면 2개의 바둑돌을 놓는 경우의 수(400 C 2) X 상대 바둑돌을 잡아먹는 수 구하기(400) = 400 x 399 % 2 X 400 = 대략삼천 이백만 정도 되므로 가능한 경우의 수이다. 이제 구현할 차례이다. dfs를 돌며 바둑 돌을 놓는 구현은 0인 자리에만 놓고 dfs 재귀 깊이가 2인 함수를 구현하면 된다. 여기서 막혔다. 어떻게 함수를 구현해야 겹치치 않고 400 C 2를 구현할 수 있을까? 정답은 이중 for문을 돌며 .. 2024. 8. 18.
[백준 17090] 미로 탈출 / 자바 / dfs(dfs 코드구현 연습) #문제         레벨: G5알고리즘:  dfs(dfs 코드구현 연습)풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/17090#문제 풀이        visted이 0,1,2(방문x,       방문O && 정답아님,     방문O && 정답임) 세가지 상태를 담을 때import java.util.*;public class Main { static int N, M; static char[][] maze; static int[][] visited; static int[] dx = {-1, 0, 1, 0}; // U, R, D, L static int[] dy = {0, 1, 0, -1}; // U, R, D, L public stat.. 2024. 8. 16.
[백준 1240] 노드사이의 거리 / 자바 / dfs (dfs구현연습) #문제         레벨: G5알고리즘:  dfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/1240#문제 풀이         dfs + void  static void dfs(int current, int end, int distance) { if (current == end) { result = distance; return; } visited[current] = true; for (int[] next : tree[current]) { if (!visited[next[0]]) { dfs(next[0], end, dista.. 2024. 8. 16.
[백준 11375] 열혈강호 / 자바 / 이분 매칭 #문제         레벨: P4알고리즘: 이분 매칭 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/11375#문제 풀이         이 문제는 이분 매칭 문제이다. 예시를 통해 문제를 설명하겠다. 헷갈릴 수 있으니 일을 1 ~5로 표현하고 직원을 A,B,C,D,E로 표현하겠다.예제 1을 보면 1. A는 1번 일과 2 번일을 할 수 있다. 일단 1번 일을 맡겠다고 치자. A B C D E1 2. B는 1번 일만 할 수 있다. 그래서 1 번 일을 맡고 있는 A가 다른 일을 맡을 수 있는지 확인한다. 확인하니 1 번 말고 2 번 일을 맡을 수 있다. B는 1 번일, A는 2 번일을 맡도록 하자. A B C D E2 1 3. C는 2, 3 번일을 할 수 있다. .. 2024. 8. 15.
[백준 16930] 달리기 / 자바 / bfs + dp #문제         레벨: P3알고리즘: bfs 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/16930#문제 풀이        위 문제는 dp + bfs(우선순위 큐) 문제이다. 기존 비슷한 문제와 다른 점은 1초에 1칸 움직이는 것이 아니라 1 ~ K 개수 만큼 이동할 수 있다는 거다. 그래서 우선순위큐를 사용하더라도 해당 위치에 도달하기 까지가 최소 이동횟수가 아닐 수도 있다. 최소이동횟수가 아닐 것을 이용해 계속 탐색하면 의미가 없지 않은가?(시간초과) 그래서 우린 이때, dp를 도입하는 거다. dp를 도입하여 각 칸에 도달한 최소 이동횟수를 적어준다. 그보다 많다면 break해줘 탐색시간을 줄이는 거다.#풀이 코드      import java.i.. 2024. 8. 13.

티스토리툴바