본문 바로가기

알고리즘/문제26

[자바] 백준 4386 - 별자리 만들기 각 별(=노드)의 위치를 좌표평면 상에 주고, 별들 간 거리는 알아서 계산한 다음에, 최소 스패닝 트리를 구하는 문제. n이 최대 100이기 때문에 거리를 구하는 데에는 100x99의 연산이 필요하니까 큰 문제는 없을 것 같은데 좀 귀찮네 ㅎㅎ 게다가 실수값이라 더 귀찮다. 1. 배열을 만들어서 각 별들의 x,y 좌표 담아두기 2. 이중 for문 이용해서 각 별들간 거리 구하고 그 값들은 PriorityQueue에 담아두기 3. PriorityQueue를 while문으로 탐색해서 최소 스패닝 트리값 구하기 DefimalFormat이라는 클래스를 써봤다. 그리고 다른 통과자들 코드를 보니까 PQ 이용하는 것보다는 ArrayList가 더 빠른가보다. /* 2021.01.05(화) */ import java... 2021. 1. 5.

[자바] 백준 1197 - 최소 스패닝 트리 최소 스패닝 트리(MST) 문제는 보통 크루스칼이나 프림 알고리즘으로 해결할 수 있다고 한다. - 크루스칼 : 간선 위주로 생각. 가중치가 가장 낮은 간선을 선택하거나 가중치가 가장 큰 간선을 제거하는 방향으로 로직을 구현한다. · 시간복잡도는 간선이 e개 있을 때 O(elog₂e) - 프림 : 노드 위주로 생각. 노드 하나를 선택하여 그 노드와 연결된 간선 중 가중치가 가장 작은 간선을 선택해가는 방향으로 로직을 구현한다. · 시간복잡도는 노드가 n개 있을 때 O(n^2) 둘 다 공통적인 건, 사이클이 생기면 안 되기 때문에 유니온-파인드 알고리즘을 알고 있어야 한다는 것. 이 문제는 가중치가 낮은 간선을 선택해가는 방식으로 풀었다. 방법 1. 각 간선들을 ArrayList에 담아서 Collection.. 2021. 1. 5.

[자바] 2019 카카오 개발자 겨울 인턴십 - #3 불량 사용자 카카오는 참 문자열 문제를 좋아하는 것 같다. programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 자료구조 HashSet과 String의 matches() 메소드를 이용해서 풀었는데 구글링 안 했으면 못 풀었을 거다. 정답을 넣는 HashSet의 경우에는, HashSet 안에 또 Set나 List를 담아서 중복을 제거할 수도 있겠지만, 나는 String이 제일 편해서 찾아낸 user_id값들을 StringBuilder 이용해서 합.. 2021. 1. 2.

[자바] 백준 1976 - 여행 가자 최단 경로를 찾는 것도 아니고, 다른 도시를 거쳐서라도 들를 수만 있으면 된다. 유니온 파인드로 각 도시들의 최상위 parent를 찾고, 경로상의 도시들이 같은 parent인지만 체크하면 된다. /* 2021.01.02(토) */ import java.io.BufferedReader; import java.io.InputStreamReader; public class Main{ static int[] parent; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readL.. 2021. 1. 2.

이전 1 2 3 4 5 6 7 다음

티스토리툴바