자바

[백준] 9370 - 미확인 도착지 (자바 Java)

[Gold II] 미확인 도착지 - 9370 문제 링크 성능 요약 메모리: 283148 KB, 시간: 1220 ms 분류 다익스트라(dijkstra), 그래프 이론(graphs) 문제 설명 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교..

[백준] 13549 - 숨바꼭질 3 (자바 Java)

[Gold V] 숨바꼭질 3 - 13549 문제 링크 성능 요약 메모리: 23028 KB, 시간: 216 ms 분류 0-1 너비 우선 탐색(0_1_bfs), 너비 우선 탐색(bfs), 다익스트라(dijkstra), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 ..

[백준] 4195 - 친구 네트워크 (자바 Java)

[Gold II] 친구 네트워크 - 4195 문제 링크 성능 요약 메모리: 105968 KB, 시간: 1048 ms 분류 자료 구조(data_structures), 분리 집합(disjoint_set), 해시를 사용한 집합과 맵(hash_set) 문제 설명 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 ..

[SWEA] [모의 SW 역량테스트] 5656 - 벽돌 깨기 (자바 Java)

dfs와 bfs를 활용하여 문제를 풀었다. dfs는 벽돌 깨기를 진행하는 과정을, bfs는 특정 벽돌을 깨뜨렸을 때의 연쇄 작용을 구현하기 위해 사용했다. 벽돌 깨기의 경우 한 번 깬 벽돌의 column에 대해서도 다시 벽돌을 깰 수 있으니 방문 여부를 저장할 필요가 없다. // col에 따라 벽돌깨기 진행 for (int i = 0; i < W; i++) dfs(i, 0); dfs는 N번 진행하기 때문에 N이 되었을 때 남은 벽돌 수를 세어서 ans와 비교하였다. 그리고 세로줄 (column)에 대해 벽돌을 깨야 하니까 i열에 대해 map[r][i]가 0이 아닌 경우에 벽돌 깨기 (game)을 진행했다. static void dfs(int i, int depth) { if (depth == N) { i..

[백준] 1197 - 최소 스패닝 트리 (자바/Java)

[Gold IV] 최소 스패닝 트리 - 1197 문제 링크 성능 요약 메모리: 230420 KB, 시간: 1196 ms 분류 그래프 이론(graphs), 최소 스패닝 트리(mst) 문제 설명 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며,..

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree) (자바/Java)

목차 최소 신장 트리 (MST) 신장트리: 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리 최소신장트리: 신장 트리 중에서 사용된 가중치의 합이 최소인 트리 특징 무방향 가중치 그래프 그래프의 가중치 합이 최소여야 한다 N개의 정점을 가지는 그래프에 대해 반드시 N-1개의 간선을 사용 사이클을 포함하면 안된다. 크루스칼 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 올므차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 (사이클 존재: 대표가 같으면 사이클(Find-Set)) n-1개의 간선이 선택될 때까지 2)를 반복 Kruskal(G) { A

[백준] 10986 - 나머지 합 (자바/Java)

[Gold III] 나머지 합 - 10986 문제 링크 성능 요약 메모리: 160148 KB, 시간: 440 ms 분류 수학(math), 누적 합(prefix_sum) 문제 설명 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 출력 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 누..

[백준] 16139 - 인간-컴퓨터 상호작용 (자바/Java)

문제 링크 성능 요약 메모리: 106172 KB, 시간: 608 ms 분류 누적 합(prefix_sum) 문제 설명 승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다. '문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.' 승재를 도와 특정 문자열 $S$, 특정 알파벳 $\alpha$와 문자열의 구간 $[l,r]$이 주어지면 $S$의 $l$번째 문자부터 $r$번째 문자 사이에 $\alpha$가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 $0$번째부터 세며, $l$번째와 $r$번..

[백준] 11659 - 구간 합 구하기 4 (자바/Java) : 누적 합

문제 링크 성능 요약 메모리: 235808 KB, 시간: 1080 ms 분류 누적 합(prefix_sum) 문제 설명 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 누적합 알고리즘의 기본을 익힐 수 있는 문제다. 누적 합 arr[i] = 0~i까지의 합 i부터 j까지의 누적 합: arr[j]-arr[i-1]; = i, i+1, … j-1, j 까지의 합 pack..

[백준] 2565 - 전깃줄 (자바/Java)

문제 링크 성능 요약 메모리: 13084 KB, 시간: 124 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에..