Algorithm/PS
[Baekjoon] 1654: 랜선 자르기
[Baekjoon] 1654: 랜선 자르기
2023.03.11문제 다양한 길이를 가진 n개의 랜선을 가지고 일정한 길이를 가진 k개의 랜선을 만들 때 만들 수 있는 최대 길이를 구하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Q1654 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nk = br.readLine().split(" "); int n = Integer.parseInt(nk..
[Baekjoon] 1167: 트리의 지름
[Baekjoon] 1167: 트리의 지름
2023.03.08문제 트리에서 두 점 사이의 거리가 가장 긴 길이를 트리의 지름이라 하는데 트리의 지름을 구하는 문제이다 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q1167 { private static List tree; private static boolean[] visited; private static int maxVertex; private static int max; public static void main(String[] args) throws IOException { BufferedReader br = new..
[Baekjoon] 7662: 이중 우선순위 큐
[Baekjoon] 7662: 이중 우선순위 큐
2023.03.08문제 삽입 연산과 삽입된 값들 중에 최대값과 최소값 삭제 연산을 통해 최종적으로 남아있는 최대값과 최소값을 출력하는 문제이다. 문제 제목 자체가 이중 우선순위 큐로 힌트를 주기 때문에, 좀 더 풀이가 쉽지 않았나 생각한다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q7662 { private static BufferedReader br; private static StringBuilder sb; public static void main(String[] args) throws IOException { br =..
[Baekjoon] 2533: 사회망 서비스(SNS)
[Baekjoon] 2533: 사회망 서비스(SNS)
2023.03.02문제 문제가 조금 복잡하다. 간단히 설명하자면, 주변의 모든 친구가 얼리어답터이면 자신은 얼리어답터가 될 필요가 없는데, 이때 최소 얼리어답터의 수를 구하는 것이다. 풀이 대표 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class Q2533 { private static List graph; private static int[][] dp; private static boolean[] visited; public static void main(String[] args) thro..
[Baekjoon] 1655: 가운데를 말해요
[Baekjoon] 1655: 가운데를 말해요
2023.03.02문제 수가 순차적으로 주어지면 입력된 수 들 중에서 중간값을 계속 출력해나가는 문제이다 -> 짝수개 일 시 더 작은 값 출력 풀이 내 풀이 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q1655 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuild..
[Baekjoon] 2170: 선 긋기
[Baekjoon] 2170: 선 긋기
2023.03.02문제 선을 정해진 횟수만큼 긋고 최종 길이를 구하는 단순 스위핑 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; public class Q2170 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer..
[Baekjoon] 9935: 문자열 폭발
[Baekjoon] 9935: 문자열 폭발
2023.03.02문제 대상 문자열과 삭제할 문자열이 주어지면, 대상 문자열에서 삭제할 문자열이 더 이상 없을 때까지 계속 삭제해나가는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main9935 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); // 대상 문자열 String deleteStr = br.readLin..
[Baekjoon] 16934: 게임 닉네임
[Baekjoon] 16934: 게임 닉네임
2023.03.02문제 닉네임의 접두사를 계속 체크하여 중복없이 별칭을 만들도록 하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Main16934 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.i..
[Baekjoon] 1138: 한 줄로 서기
[Baekjoon] 1138: 한 줄로 서기
2023.02.26문제 각 index 번째에 있는 사람들의 왼쪽에 자기보다 큰 사람이 몇 명 있는지 주어지면, 각 사람들의 번호를 위치 순서로 출력하는 문제이다. 풀이 내 풀이 public class Q1138 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); List numbers = new ArrayList(); int n = Integer.parseInt(br.readLine()); String[] leftCounts = br.readLine().split(" "); for (int i = n - 1; i >= 0; i--) ..
[Baekjoon] 17298: 오큰수
[Baekjoon] 17298: 오큰수
2022.12.06문제 각 원소 A_i에 대해 오른쪽에 있으면서 A_i보다 큰 수 중에서 가장 왼쪽에 있는 수를 구하는 문제이다. (없을 경우 -1) 예를들어 3 5 2 7 이라는 수열이 있으면, 3의 오큰수는 5, 5의 오큰수는 7, 2의 오큰수는 7, 7의 오큰수는 없으므로 5 7 7 -1 이라는 결과가 나오게 된다. 풀이 내 풀이 import sys input = sys.stdin.readline n = input() arr = list(map(int, input().split())) result = [0] * len(arr) stack = [0] for i in range(1, len(arr)): while stack and arr[i] > arr[stack[-1]]: result[stack.pop()] = arr..
[Baekjoon] 3190: 뱀
[Baekjoon] 3190: 뱀
2022.10.23문제 어릴 때 많이 했던 뱀 게임을 구현하는 문제이다. 풀이 내 풀이 import sys from collections import deque n = int(sys.stdin.readline()) apple_count = int(sys.stdin.readline()) board = [[0 for i in range(n)] for i in range(n)] board[0][0] = 1 for i in range(apple_count): r, c = map(int, sys.stdin.readline().split()) board[r-1][c-1] = 2 directs = deque([]) for i in range(int(sys.stdin.readline())): s, d = sys.stdin.readlin..
[Baekjoon] 11054: 가장 긴 바이토닉 부분 수열
[Baekjoon] 11054: 가장 긴 바이토닉 부분 수열
2022.10.19문제 풀이 내 풀이 import sys n = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [1] * n for i, v in enumerate(seq): for j in range(i-1, -1, -1): if seq[j] v: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) 이 문제는 이전에 풀었던 11053번 가장 긴 증가하는 부분 수열 문제에서 변형된 문제이다. 아이디어는 11053번 문제..