Java

문제https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일www.acmicpc.net풀이 전형적인 크루스칼 문제입니다. 가중치 값이 소수라는 것이 조금은 특이합니다.  우선 입력받는 좌표 값을 stars 라는 ArrayList 에 입력받고, 이 값을 edgeList라는 ArrayList에서 연결했습니다.  이 때, 제공되는 좌표를 가중치(거리)로써 필요한 것에 집중하고, 두 쌍의 좌표는 하나의 인덱스(i or j)로 ArrayList에 입력을 해주었습니다. 그렇게 인덱스를 통해 서..

Java를 사용해 알고리즘 문제를 풀다가, StringBuffer와 StringBuilder의 사용법도, 내장 메서드도 비슷한데 왜 두 가지로 나뉘어져 있는가에 대한 의문이 들었다. 그렇게 찾아보니 String과의 차이도 중요하다는 것을 알게 되었다.  이번 포스팅에서는 세 가지 자료형에 대한 성능과 차이를 공부한 것을 정리해보려 한다.  1. String 과  StringBuffer / StringBuilder 비교String 우선 StringBuilder와 StringBuffer는 주로 문자열을 이어붙일 때 주로 사용한다. 하지만, String만으로도 concat() 또는 "+" 연산을 통해 문자열을 이어 붙일 수 있다.  굳이 String이 아닌 StringBuilder와 StringBuffer를 ..

문제 https://www.acmicpc.net/problem/19949 19949번: 영재의 시험 컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다. 평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다. 당연하게도 문제를 하나도 풀지 못하였지만 다행 www.acmicpc.net 풀이 백트래킹을 이용한 문제입니다. 백트래킹 메서드에 매개변수로 찍었는데 맞은 정답의 수, 현재의 인덱스, 찍은 배열을 전달했습니다. 이 때 조건에 따라 정답의 수가 5개가 넘으면 ans++를 통해 답을 구합니다. 그리고 3개 이상 연속된 수를 고를 수는 없다는 조건에 맞게 idx가 2이상일 때는 만약 앞의 idx의 값이 두 번 연속되었다면, 그 수는 다음에서 선택할 수 없도록, ban이라는 변수..

문제 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 문제의 조건에서 N의 input size가 최대 10,000 입니다. 만약 배열을 두 번 돌게 된다면 시간 복잡도 O(N^2)는 1억으로 1초가 넘어가 문제의 시간 제한 조건인 0.5초를 넘어가게 됩니다. 그래서 이 문제는 투 포인터를 통해 접근해야 합니다. 매커니즘의 순서는 다음과 같습니다. 1. 만약 sum이 M과 같다면, cnt를 증가시키고..

문제 https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 풀이 전형적인 다익스트라 문제입니다. 다익스트라 알고리즘을 사용할 수 있는 조건이 몇 가지가 있습니다. 1. 가중치는 모두 0 이상이어야 한다. 2. 방향 그래프를 가정으로 둔다. 3. 사이클이 없어야 한다. 위 문제에서는 무방향 그래프가 주어졌기 때문에, 간선을 분리해서 방향 그래프로 바꾸었습니다. 소스 코드 import java.util.ArrayList; import java.ut..

문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 이전에 포스팅한 백준 2003. 수들의 합2 문제와 매우 유사합니다. 풀이 보러 가기 만약 수들의 합2 문제를 풀지 않으셨다면 위 문제부터 푸는 것을 추천드립니다. 위 문제의 풀이에서 포인터 사이의 간격을 최소로 갱신해주기만 하면 됩니다. 소스 코드 import java.util.Scanner; public class Main { public static void main..