본문 바로가기

분류 전체보기

 (261)
[백준] 11399 : ATM JAVA 풀이 그리디 알고리즘의 아주 기초적인 문제였다. 1. 인덱스와 소요시간을 저장하는 클래스 Person을 생성함 2. Person의 ArrayList를 생성한 뒤 갑을 입력해줌 3. ArrayList를 소요시간순으로 정렬함 4. 정렬된 ArrayList를 이용해 소요시간의 누적합을 구하고 출력함 import java.io.*; import java.util.*; public class Main { static class Person{ int idx; int time; Person(int idx, int time){ this.idx = idx; this.time = time; } } public static void main(String[] args) throws IOException{ BufferedReader..
[백준] 1707 : 이분 그래프 JAVA 풀이 이분 그래프란 그래프의 정점들을 두 가지 색으로 칠할 때, 한 정점과 인접해있는 정점들이 서로 다른 색일 때를 말한다. 입력 예제 그래프로 예를 들어보면 이렇다. 두 번째 그래프는 2를 기준으로 3, 4가 파란색이어야 한다. 3을 기준으로는 2, 4가 빨간색이어야 한다. 4를 기준으로는 2, 3이 빨간색이어야 한다. 따라서 두 번째 그래프는 이분 그래프가 될 수 없다. 1. Node 클래스를 생성함. 노드의 인덱스인 idx, 노드의 색깔인 color, 인접노드를 저장할 ArrayList인 child를 멤버변수로 설정 2. V개의 노드를 저장할 Node 배열을 생성함 3. V개의 노드를 방문했는지 검사할 boolean 배열을 생성함 4. 그래프에 대한 정보를 입력받고 양방향그래프를 생성함 5. 아직 방문하..
[백준] 9466 : 팀 프로젝트 JAVA 풀이 뭔가 풀릴 듯 안 풀려서 결국 구글링의 힘을 빌렸다. 학생들이 선택한 학생번호를 저장할 int 배열, 각 학생들의 팀 배정이 완료됐는지 확인하는 boolean 배열, 한 바퀴를 돌았는지(=두 번째 방문한 건지) 확인하는 boolean 배열이 필요하다. import java.io.*; import java.util.*; public class Main{ static boolean[] visit, done; static int[] arr; // 완성된 팀의 개수 static int cnt; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(Sys..
[백준] 1167 : 트리의 지름 JAVA 풀이 11725번 트리의 지름 문제에서 입력방식만 달라진 문제였다. import java.io.*; import java.util.*; public class Main { static class Node{ int idx; int cnt; Node(int idx, int cnt){ this.idx = idx; this.cnt = cnt; } } // 정점의 개수 static int v; // 최대인 거리 static int max = 0; // 루트노드에서 가장 멀리 떨어진 정점 static int max_idx = 0; // 정점을 방문했는지 검사하는 배열 static boolean[] visit; // 트리를 저장할 노드들의 어레이리스트 배열을 생성 static ArrayList[] list; public ..
[백준] 1967 : 트리의 지름 JAVA 풀이 모든 노드에 대해서 dfs를 수행하는 방법과, 루트 노드를 기준으로 dfs를 수행해서 가중치가 가장 큰 노드를 찾고, 그 노드부터 다시 dfs를 수행하는 두 가지의 방법으로 풀어보았다. 코드는 크게 다를 게 없지만 실행시간에서 큰 차이가 났다. 전자는 dfs를 2번만 수행하면 되지만 후자는 N-1번 수행해야 하니 당연하다. import java.io.*; import java.util.*; public class Main { static class Node{ int idx; int cnt; Node(int idx, int cnt){ this.idx = idx; this.cnt = cnt; } } static boolean[] visit; static ArrayList[] list; static int m..
[백준] 11725 : 트리의 부모 찾기 JAVA 풀이 import java.io.*; import java.util.*; public class Main { static class Node{ int data; Node left; Node right; Node(int data){ this.data = data; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); // 양방향그래프 ArrayList list = new ArrayList(); for(int i=0;i
[백준] 1991 : 트리 순회 JAVA 풀이 import java.io.*; import java.util.*; public class Main { static class Node{ char data; Node left; Node right; Node(char data){ this.data = data; } } static int N; static Node[] arr; public static void main(String[] args)throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br.readLine()); // 노드의 배열 생성 arr = new Nod..
[백준] 2146 : 다리 만들기 JAVA 풀이 1. 각각의 섬에 번호를 붙인다. 2. 각 섬에서 bfs를 수행해 다른 섬으로 가는 다리를 구해서 짧은 것으로 업데이트한다. import java.io.*; import java.util.*; public class Main { // 지도의 크기 static int N; // 섬에 붙일 번호 // 0은 바다, 1은 섬이니 2부터 static int landNum = 2; static int[][] map; static boolean[][] visit; // 가장 짧은 다리의 길이 static int answer = Integer.MAX_VALUE; // 방향 배열 static int[] dx = {0,0,-1,1}; static int[] dy = {1,-1,0,0}; static class Node{ ..

티스토리툴바