본문 바로가기
728x90

전체 글259

[백준] 자바 문제 풀이 2109 : 골드3 BOJ 2109 풀이 코드 import java.io.*; import java.util.*; public class Main { static class Lecture { int cost; int day; Lecture(int cost, int day) { this.cost = cost; this.day = day; } } public static void main(String[] args) throws Exception { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new Output.. 2023. 9. 23.
[Java] 조건문 - Switch Switch문 switch문은 if문과 유사하면서 다르다. 조건식을 만족하는 경우에만 실행하는 것은 똑같지만 if문은 비교연산자를 이용한 조건식을 사용한다 switch문은 특정 변수안에 초기화 되어 있는 값이 어떤 값이냐에 따라 조건문을 실행한다. 예를 들어, 성별이 남성이면 "남성입니다", 여성이면 "여성입니다"를 출력하고 싶을 때 if문과 switch문으로 다음과 같이 작성할 수 있다. public class Main { public static void main(String[] args) { String gender = "Male"; //if문 if(gender.equals("Male") { // equals : String 비교 메소드 System.out.println("남성입니다"); } els.. 2023. 9. 23.
[Java] 조건문 - if if문 if문이란 조건식에 의해 true일 때만 실행되게 하는 문법이다. 예를 들어 입력받은 수가 양수일 때만 양수입니다라고 출력하고 싶을 때는 if문을 활용하여 다음과 같이 작성할 수 있다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); if(n > 0) { System.out.println("양수입니다."); } } } n이 양수(0보다 큰 정수)일 때에는 if문안의 조건식인 n > 0 을 만족(true)하기 때문에 중괄호({})안에 선언된 출력문이 실행된다. if-else문 만약 위의 예시에서 양수가 아닌 경우에는 "양수가 아닙니다".. 2023. 9. 23.
[알고리즘]그래프6 - 벨만포드(feat. Java) 벨만-포드(Bellman-Ford) 알고리즘 그래프 최단 경로를 구하기 위한 알고리즘 하나의 정점에서 출발하는 최단 거리를 구함 음수 싸이클 없어야 함, 음수 가중치는 허용 O(mn) 시간 복잡도 과정 dist : 출발지로부터 최단 거리를 기록하는 1차원 배열. 출발지는 0 / 나머지는 무한으로 초기화 정점의 개수 n만큼 아래를 반복 간선 m개를 하나씩 살펴본다. 현재 간선의 가중치를 cost(v, w)라고 하면 dist[v]는 지금까지 계산한 출발지에서 v까지 최소 거리이다. dist[v]가 무한대가 아니라면 아랫단계 진행 지금까지 계산한 dist[v]와 dist[v]+cost(w, v) 중 최솟값을 다시 dist[v]에 할당 n = 5, m = 9, 출발 정점은 4 dist 배열에 무한이 아닌 값은 .. 2023. 9. 23.
[알고리즘]그래프5 - 다익스트라(feat. Java) 다익스트라(Dijkstra) 알고리즘 그래프의 최단 경로를 구하는 알고리즘 하나의 정점에서 출발하는 최단 거리를 구함 음수 가중치 X 가정 배열로 구현 그래프의 경우 : O(n^2) 우선순위 큐 사용 -> O(mlogn) 과정 아직 방문하지 않은 정점 중 출발지로부터 가장 거리가 짧은 정점을 방문 해당 정점을 거쳐 갈 수 있는 정점의 거리가 이전 기록한 값보다 적으면 갱신 pq : 우선순위 큐, 정점과 출발지에서 정점까지 가는 최소 거리를 저장, 거리가 짧을 수록 우선순위 높음 check : 정점을 방문한지 체크하는 배열 dist : int 배열로 출발지에서 최소 거리를 기록 출발지 4를 우선순위 큐에 넣음, 출발지이므로 거리는 0 우선순위 큐에서 하나 꺼내 nowVertex에 저장하고 방문체크, now.. 2023. 9. 22.
[백준] 자바 문제 풀이 17822 : 골드2 BOJ 17822 풀이 코드 import java.io.*; import java.util.*; public class Main { static class Point { int a; int b; Point(int a, int b) { this.a = a; this.b = b; } } public static void main(String[] args) throws Exception { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out.. 2023. 9. 22.
[백준] 자바 문제 풀이 1715 : 골드4 BOJ 1715 풀이 코드 import java.io.*; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); PriorityQueue pq = new Priorit.. 2023. 9. 22.
[백준] 자바 문제 풀이 12837 : 골드1 BOJ 12837 풀이 코드 import java.io.*; import java.util.*; public class Main { static class SegmentTree { private long[] tree; SegmentTree(int n) { double treeHeight = Math.ceil(Math.log(n)/Math.log(2))+1; long treeNodeCount = Math.round(Math.pow(2, treeHeight)); tree = new long[Math.toIntExact(treeNodeCount)]; } long init(long[] arr, int node, int start, int end) { if(start == end) { return tree[nod.. 2023. 9. 22.
[백준] 자바 문제 풀이 9935 : 골드4 BOJ 9935 : Stack & Deque import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader((System.in))); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String str = br.readLine(); String bomb = br.readLine(); char b = bomb.charAt(bomb.length() - 1); Deque d.. 2023. 9. 22.
[알고리즘]그래프4 - BFS(feat. Java) BFS란? 저번 글에서 알아본 DFS는 깊이 우선 탐색이었다면 BFS(Breadth-First Search) 너비 우선 탐색으로서 DFS와 함께 코딩 문제에 단골로 등장하는 그래프 탐색 알고리즘이다. DFS는 제일 깊이 있는 노드까지 탐색한 뒤에 돌아오는 방식이면, BFS는 인접한 노드를 먼저 탐색을 하는 알고리즘이다. 그렇기 때문에 재귀(Stack 구조)를 활용하여 구현했던 DFS와 달리, BFS는 Queue를 통해 구현을 하게 되고 Queue를 생각하면 이해하는 것도 쉽습니다. 저번 시간에 다루었던 예제를 또 다루어보면, 1번 노드를 큐에 넣은 후 방문처리 큐에서 노드를 꺼낸 후 인접 노드를 큐에 넣고 방문 처리 바로 위의 과정을 반복 1번 노드 꺼낸 후 2, 3, 8번 노드가 큐에 들어감 (Queu.. 2023. 9. 21.
[알고리즘]그래프3 - DFS(feat. Java) DFS란? DFS란 그래프를 순회하는 알고리즘 중 하나이다. Depth-First Search의 줄임말로 깊이 우선 탐색이라고 한다. 이름에서 알 수 있듯이 연결된 노드(정점 : vertex)를 따라서 계속 방문을 한 후에 더 이상 연결된 노드들이 없을 때 그 전 노드로 되돌아가고 다시 연결된 노드를 따라서 탐색을 한다. 예를 들어 다음 그림에서, 1번 노드에서 DFS를 사용하여 탐색을 진행한다고 한다면, (연결된 노드가 여러개라면 오름차순으로 방문한다고 가정) 1번 노드 방문 후 2, 3번 노드 중 2번으로 방문 2번 노드 방문 후 6, 8번 노드 중 6번으로 방문 6번 노드 방문 후 더 이상 연결된 노드가 없으므로 2번으로 돌아감 2번 노드에서 방문하지 않았던 8번으로 방문 8번 노드 방문 후 연결된.. 2023. 9. 21.
[알고리즘]그래프2 - 구현(feat. Java) 2차원 배열 2차원 배열을 사용하여 정점에서 다른 정점으로 가는 간선의 존재유무(1 : 존재, 0 : 없음)를 알 수 있다. 2차원 배열을 사용할 경우 연결된 정점을 찾기 쉽고 구현이 쉽다는 장점이 있지만 O(n^2)의 공간 복잡도를 가진다는 단점이 있다. 구현 코드 public static void main(String[] args) { int[][] edges = new int[][] { {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5} }; int n = 5; //정점의 개수 int[][] matrix = new int[n + 1][n + 1]; for(int[] edge : edges) { //무방향 그래프이기 때문에 양쪽 모두 1로 초기화 matrix[edge[.. 2023. 9. 21.
728x90
반응형

티스토리툴바