Algorithm/Baekjoon208 [백준] 16169: 수행 시간 - JAVA https://www.acmicpc.net/problem/16169 풀이컴퓨터마다 계급이 있어서 i번 컴퓨터가 동작하기 위해서는 i-1번 컴퓨터들이 먼저 동작을 해야한다. 위상정렬을 이용해 구현했다. 컴퓨터들의 정보를 저장하고, 계급의 오름차순으로 i번과 i+1을 연결시키는 연결리스트로 저장했다. 위상정렬을 위한 배열도 저장하여 이 값이 0인 것부터 큐에 넣어 처리해주었다. 메모리: 14148KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Computer { int idx; int rank; int speed; public Compu.. 2024. 5. 19. [백준] 1039: 교환 - JAVA https://www.acmicpc.net/problem/1039 풀이정수 N의 i번 위치와 j번 위치의 숫자를 바꿀 수 있다. 이 행위를 K번 반복할 때 최댓값을 구해야 한다. 위치를 바꿀 때 바꾼 수가 0으로 시작하면 안된다. n번 수행했을 때 나온 수를 방문처리 하기 위해 이차원 배열로 방문처리했다. bfs탐색을 통해 숫자와 바꾼 횟수를 저장해가면 진행했다. 메모리: 54616KB시간: 244ms언어: Java 11import java.io.*;import java.util.*;public class Main { static final int MAX = 1_000_001; static int answer; static class Node { int num; .. 2024. 5. 18. [백준] 2150: Strongly Connected Component - JAVA https://www.acmicpc.net/problem/2150 풀이SCC는 정점들의 부분집합이며, 그 부분집합에 들어있는 서로 다른 두 정점 u, v에 대해 u에서 v로 가는 경로, v에서 u로 가는 경로가 모두 존재하는 경우를 말한다. 간선의 정보가 주어질 때, SCC의 개수와 그 안의 정점들을 출력해야 한다. SCC를 구하는 방법으로 코사라주 알고리즘과 타잔 알고리즘이 있다. - 코사라주 알고리즘 방향 그래프, 역방향 그래프, 스택을 사용하여 SCC를 구한다. 방향 그래프와 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한다. 1. 방향 그래프의 모든 정점에 대해 dfs를 수행하여 끝나는 순서대로 스택에 삽입한다. 2. 아직 방문하지 않은 정점이 있는 경우 다시 DFS를 수행한다... 2024. 5. 18. [백준] 2792: 보석 상자 - JAVA https://www.acmicpc.net/problem/2792 풀이M가지 보석을 N명의 학생들에게 나눠주어야한다. 보석을 받지 못하는 학생이 있어도 된다. 따라서 질투심을 몇 개로 할지를 변수로 두고 이분 탐색을 했다. 질투심을 mid로 했을 때 보석을 받는 학생의 수가 N보다 작으면 정답이 될 수 있다. N보다 크면 left를 mid + 1로, 그렇지 않으면 right를 mid - 1로 좁혀가면서 탐색한다. 메모리: 34892KB시간: 356ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Buffer.. 2024. 5. 18. [백준] 7578: 공장 - JAVA https://www.acmicpc.net/problem/7578 풀이A열과 B열에 같은 숫자들을 연결할 때, 케이블들이 서로 교차하는 부분의 개수를 세는 문제이다. A열: 1 2 3 4 5 B열: 2 4 1 3 5 위와 같이 주어졌을 때, B열에서 A열로 줄을 쏴주었다. B열의 2에서 A열의 2로 줄을 쐈을 때, A열의 2보다 오른쪽에 이미 연결된 점이 있다면 그 점이 교차하는 점이다. B열은 앞에서부터 순서대로 보는데, A열의 연결된 점 오른쪽으로 연결된 점이 있다는 것은 B열의 앞쪽 점과 연결되어 있다는 것이므로 교차한다는 것이다. A열의 인덱스를 저장해주었고, B열의 점이 A열의 어떤 인덱스와 연결되는지 저장했다. 세그먼트 트리를 이용해 A열의 인덱스부터 N까지 구간합을 구해 교차점이 몇개인지 구.. 2024. 5. 18. [백준] 10868: 최솟값 - JAVA https://www.acmicpc.net/problem/10868 풀이N개의 정수 배열의 a~b구간에서의 최솟값을 찾아야 한다. 세그먼트트리를 만들어 구간별로 최소값을 갖는 배열의 인덱스를 저장했다. a~b구간에서 최솟값의 인덱스를 찾아 배열의 값을 출력하면 된다. 인덱스를 저장하지 않고 최솟값 자체를 세그먼트트리에 저장하는 것도 좋다. 메모리: 48788KB시간: 600ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class SegmentTree { int[] tree; int treeSize; public SegmentTree(int arrSize) { .. 2024. 5. 18. [백준] 13701: 중복 제거 - JAVA https://www.acmicpc.net/problem/13701 풀이정수를 입력받으면서 부른적이 없는 정수만 출력하는 문제이다. set자료구조를 생각했지만 메모리 제한때문에 비트마스킹으로 풀어야한다. N의 범위는 2^25로 주어져있다. int범위는 32bit까지 담을 수 있기 때문에 32개의 숫자를 중복검사할 수 있다. 따라서, 2^25개의 수를 중복검사하려면 2^20크기의 배열을 만들어 배열의 원소 한 개가 32개의 숫자를 중복검사하도록 구현해야 한다. `int[] number = new int[1 메모리: 350208KB시간: 1388ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void.. 2024. 5. 18. [백준] 2517: 달리기 - JAVA https://www.acmicpc.net/problem/2517 풀이N명의 선수의 실력을 입력받는다. 입력을 받는 순서대로 해당 위치에 있다고 할 때, 실력이 자기보다 안좋은 선수가 앞에 있으면 역전할 수 있다. 예를들어 실력이 2, 8, 10으로 주어졌다면 8실력을 가진 선수는 앞에 자기보다 낮은 실력의 선수 1명이 있으므로 이 선수가 할 수 있는 최선의 등수는 1등이다. 10인 선수는 앞에 2명을 앞지를 수 있으므로 최선의 등수는 1등이 된다. 세그먼트 트리를 이용하여 실력을 tree의 인덱스로 하여 1늘린다. 1부터 자신의 인덱스까지 구간합을 구하면 자신과 자신보다 실력이 낮은 선수들의 합이 된다. 구간합과 입력받은 순서를 이용하여 최선의 등수를 계산할 수 있다. 각 선수의 실력은 모두 다르므로 .. 2024. 5. 18. [백준] 24042: 횡단보도 - JAVA https://www.acmicpc.net/problem/24042 풀이1 ~ N 까지 영역이 있고 각 영역을 잇는 횡단보도를 통해 건널 수 있다. M개의 횡단보도가 켜지는 순서대로 주어진다. 즉, 첫번째 횡단보도는 0, M, 2M... 시간에 켜지고, 두번쨰 횡단보도는 1, M + 1, 2M + 1... 시간에 켜진다. 켜지는 시간을 가중치로하여 다익스트라 알고리즘을 수행하면 된다. 현재 시간보다 다음 건널 횡단보도에 적힌 시간이 작다면 더 커질때까지 M을 더해야 한다. `long nextCost = curr.cost + ((next.cost - curr.cost) % M + M) % M + 1;` 위 식으로 계산할 수 있었다. 메모리: 222712KB시간: 1292ms언어: Java 11import.. 2024. 5. 18. [백준] 16120: PPAP - JAVA https://www.acmicpc.net/problem/16120 풀이문자열을 앞에서부터 보면서 'PPAP'가 되면 'P'로 바꿔준다. 최종적으로 'P'가 되면 성공. P가 들어오면 cnt를 1 늘려준다. A가 들어올 때 cnt가 2보다 작다면 PPAP를 만들수 없으므로 실패. cnt가 2이상이고, 다음 글자가 P라면 PPAP를 만들 수 있으므로, cnt를 1 줄여준다(P가 2개 빠지고 새로운 P가 들어오기 때문). 메모리: 20080KB시간: 260ms언어: Java 11import java.io.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new .. 2024. 5. 18. 이전 1 ··· 4 5 6 7 8 9 10 ··· 21 다음