본문 바로가기

분류 전체보기

 (56)
[Baekjoon] 백준 21924번: 도시 건설 (JAVA) 문제 21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net [ 문제 풀이 ] 모든 건물을 최소한의 비용으로 연결하는 문제이므로 크루스칼 알고리즘으로 풀면 됩니다. 크루스칼 알고리즘에 대한 자세한 설명은 아래 포스트를 참고해주세요 :) [JAVA] 서로소 집합(Disjoint Sets)과 연산 최근 알고리즘 문제를 풀면서 최소 신장 트리 개념에 대해 공부하다가 알게 된 크루스칼 알고리즘..
[Baekjoon] 백준 14567번: 선수과목 (JAVA) 문제 14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net [ 풀이 과정 ] 대표적인 위상 정렬 문제입니다. 위상정렬 문제는 아래의 내용을 기본으로 해서 풉니다. 1. 방향 그래프를 만든다. (연결 리스트 생성) 2. 각 노드의 진입차수를 배열로 저장한다. 3. 진입차수가 0인 노드를 그래프에서 하나씩 지워가며 queue에 저장한다. 학기는 depth로 생각할 수 있으므로, 큐의 현재 사이즈만큼 돈 후에 하나씩 증가시켜주면 됩니다. 문제에 나와있는 예제 입력 2를 보면 아래와 같습니다. 진입차수가 0인 노드 1, 4, 6을 먼저 q..
[Baekjoon] 백준 11085번: 군사 이동 (JAVA) 문제 11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net [ 풀이 과정 ] 입력으로 받는 c와 v를 연결하는데, 가장 넓은 너비를 가지는 간선으로만 연결하는 문제입니다. 시작과 끝이 각각 c와 v이므로 이 점을 유의하며 크루스칼 알고리즘으로 해결할 수 있습니다. 간선을 나타내는 Edge 클래스를 만들고, Comparable을 이용하여 간선의 너비가 넓은 순(내림차순)으로 정렬할 수 있도록 compareTo()를 오버라이딩 합니다. PriorityQueu..
[Baekjoon] 백준 11123번: 양 한마리... 양 두마리... (JAVA) 문제 11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net [ 풀이 과정 ] 양들의 무리만 카운트하면 되므로 map[][]에 양과 풀을 저장한 후 for()문으로 순회하면서 '#' 가 있는 위치에서 카운트를 하나 증가시키고, bfs()를 돌려주면 상하좌우로 붙어있는 '#' 끼리 최대한 방문하게 됩니다. (행, 열의 최대 크기가 각각 100이므로 시간복잡도는 충분합니다.) !! for()문으로 순회할 때 방문체크까지 해주어야 정점을 중복해서 방문하지 않게 됩니다. [ 코드 ] import..
[Baekjoon] 백준 14248번: 점프 점프 (JAVA) 문제 14248 14248번: 점프 점프 첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000) 다음 줄에는 출 www.acmicpc.net [ 풀이 과정 ] 입력값을 살펴보면, 돌의 개수를 입력받은 후 각 돌의 위치에서 좌우로 점프할 수 있는 거리, 즉 칸의 개수를 입력받습니다. 따라서 jump[]에 각 위치에서 점프할 수 있는 거리를 입력 받아 저장해주고, BFS를 사용하여 현재 칸에서 점프하여 갈 수 있는 모든 위치를 큐에 넣고 방문표시를 해준 후, 전역변수 cnt를 하나씩 증가해줍니다. [ 코드 ] import java.io.*; import java..
[Baekjoon] 백준 5972번: 택배 배송 (JAVA) 문제 5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net [ 풀이 과정 ] 간선에 비용이 있고, 최소 비용을 구하는 문제이므로 다익스트라로 풀 수 있습니다. Node 클래스를 만들어 정점의 값과 비용을 저장하고, ArrayList 배열을 만들어 Node 인스턴스를 저장하여 시작 정점에서 도착 정점까지의 간선 비용을 저장합니다. 최소 비용을 구하기 위해 우선순위 큐를 사용하여 비용이 작은 값부터 방문할 수 있도록 하고, dist[]에 각 정점까지의 최소 비용을 저장해줍니다. [ 코드 ] import java.io...
[Baekjoon] 백준 17070번: 파이프 옮기기 1 (JAVA) 문제 17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [ 풀이 과정 ] (1, 1) 에서 (N, N) 까지 가는 경우의 수를 구하는 것이기 때문에 그래프 탐색 방법인 BFS, DFS가 떠올랐습니다. 흔히 그래프 탐색 문제는 현재 좌표에서 상하좌우 또는 대각선까지 갈 수 있는 좌표를 모두 탐색하는 것이 대부분이지만, 이 문제에서는 현재 좌표에서 갈 수 있는 방향이 오른쪽, 아래쪽, 대각선(오른쪽 아래) 이렇게 총 3가지이고, N의 범위도 3 ~ 16으로 작습니다. BFS로 풀게..
[SWEA] 4038. [Professional] 단어가 등장하는 횟수 (with JAVA) 문제 4038 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 처음에는 정말 단순한 방법으로 하나씩 비교해가며 풀었습니다. 당연하게 시간초과가 났고, 좀 더 효율적으로 푸는 알고리즘인 KMP 알고리즘을 활용하여 해결하였습니다. KMP 알고리즘을 살펴보기에 앞서, 단순하게 비교하며 푸는 방법에서 어떤 부분을 효율적으로 개선시켜야 하는지에 대해 알아보겠습니다. 탐색할 문자열이 "ababa" 일 때, "aba" 가 몇 번 들어가는지를 알아보려고 합니다. 아래는 제가 처음에 풀었던 방식입니다. 이렇게 해서 총 2번이 들어가는 것을 확인할 수 있지만, 총 7번에 걸쳐서 찾을 수 있었습니다. 즉, 찾으려는 단어의 길이가 ..

티스토리툴바