본문 바로가기
반응형

분류 전체보기123

Java 데이터 입/출력 시간 줄이는 방법(BufferedReader, BufferedWriter, StringBuilder, startWith, substring...) / 백준 11723. 집합 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 백준 집합 문제를 풀다가 간단해보이길래 Scanner, System.our.println() 을 이용하여 문제를 풀었다. 하지만 시간초과가 나서 공부를 하던 중 데이터 입출력 부분에서 시간초과가 났다는 것을 알게 되었다. 알고리즘 문제를 풀 때 대량의 데이터를 처리할 때 쓰기 좋은 방법을 배워서 정리하겠다. 1. BufferedReader Scanner 대신에 BufferedReader를 사용하면 입력된 데이터가 바로 전달되지 않고.. 2021. 8. 16.
백준 2961. 도영이가 만든 맛있는 음식 🅰 백준 2961. 도영이가 만든 맛있는 음식 ✏️ 문제 풀이 부분집합을 이용하여 재료를 사용할 수 있는 모든 상황을 고려하였다. LinkedList를 이용하여 {S,B}의 값을 넣어주었다. isSelected 배열을 이용하여 부분집합을 생성하였고, 재료선택 케이스마다 sum,mul을 계산해주어 절대값을 이용하여 최소값을 계속 비교해주었다. ✏️ 소스코드 package com.ssafy.baekjoon; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.StringTokenizer; public class Main.. 2021. 8. 13.
백준 15686. 치킨배달 🅰 백준 15686. 치킨배달 ✏️ **문제 풀이** 조합을 이용하여서 모든 케이스 탐색 LinkedList를 이용하여 문제를 풀었다. 전체 치킨집 개수 C 선택된 치킨집 개수(M) 번의 조합을 선택하여 선택된 치킨집 케이스 마다 최소가 되는 치킨거리를 저장하였고 조합의 모든 케이스를 돌았을 시 그때 최소가 되는 치킨거리를 선택하였다. ✏️ **소스코드** package com.ssafy.baekjoon; import java.util.*; public class Main_골드5_15686_손은성 { static LinkedList chicken = new LinkedList(); static LinkedList selected_chicken = new LinkedList(); static LinkedL.. 2021. 8. 13.
백준 10610. 30 / 배수판정법 🅰 백준 10610. 30 ✏️ 문제 풀이 자리수가 10^5개 이다. 100000의 정수가 아니라 00000000000000000000000000000000000000000000000000 개의 숫자가 들어간다는 말이다. int나 long 형으로 처리할 수 없기 때문에 문자열로 처리해야 한다. 30의 배수가 되기 위해서는 자리수의 합이 3의 배수여야 하고, 마지막 자리가 0이여야 한다. ans에 정렬하여 출력하려고 했으나 숫자 자리수가 10^5이므로 int,long의 자리수를 훌쩍 넘기므로 배열or 문자열로 출력해야 했다. 오름차순으로 배열이 정렬되어 있으므로, 배열의 역 순서대로 출력을 해주었다. ✏️ 소스코드 package greedy; import java.util.*; import java.io... 2021. 8. 13.
백준 1080. 행렬 0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오. 행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0) 이 문제가 그리디 알고리즘인 이유 Q1. 3 * 3행렬로 가장 많이 변경할 수 있는 것이 최적의 해가 아닌가요? 많이 변경함으로써 전체적으로 변경해야할 수가 줄어든 거니깐요. → 뒤집는 연산의 특성상 많이 변경하는 것은 의미가 없습니다. 따라서 최적의 해에 가까워진다고 볼 수 없습니다. Q2. 이게 왜 최적의 해가 되는 건가요? 그냥 순서대로 뒤집어 보다가 단순히 맞추는 것이 아닌가요? 그것이 어떻게 최저횟수가 되는지 모르겠습니다. → 이 문제의.. 2021. 8. 13.
[swexpert] Intermediate / LinkedList / 1228 / 1229 / 1230 🅰 1228. 암호문 1 ​ ✏️ 문제 풀이 0 ~ 999999 사이의 수를 나열하여 만든 암호문이 있다. 암호문을 급히 수정해야 할 일이 발생했는데, 이 암호문은 특수 제작된 처리기로만 수정이 가능하다. 이 처리기는 다음과 같이 1개의 기능을 제공한다. 1. I(삽입) x, y, s : 앞에서부터 x의 위치 바로 다음에 y개의 숫자를 삽입한다. s는 덧붙일 숫자들이다.[ ex) I 3 2 123152 487651 ] 위의 규칙에 맞게 작성된 명령어를 나열하여 만든 문자열이 주어졌을 때, 암호문을 수정하고, 수정된 결과의 처음 10개 숫자를 출력하는 프로그램을 작성하여라. ​ Integer 타입의 List를 선언해주었고, list에 데이터를 입력해주었다. I x y s는 x번 뒤에 y만큼의 데이터 s를 .. 2021. 8. 12.
[swexpert] Intermediate / Queue / 1225 / 1226 / 1227 🅰 1225. 암호생성기 ​ ✏️ 문제 풀이 8개의 숫자를 입력 받는다. 첫 번째 숫자를 1 감소한 뒤, 맨 뒤로 보낸다. 다음 첫 번째 수는 2 감소한 뒤 맨 뒤로, 그 다음 첫 번째 수는 3을 감소하고 맨 뒤로, 그 다음 수는 4, 그 다음 수는 5를 감소한다. 이와 같은 작업을 한 사이클이라 한다. 숫자가 감소할 때 0보다 작아지는 경우 0으로 유지되며, 프로그램은 종료된다. 이 때의 8자리의 숫자 값이 암호가 된다. ​ 큐를 이용하여 8개의 숫자를 입력받은 뒤 while문을 통해 반복을 해주었고 그 안에 for문을 넣어 감소한 숫자를 반복해주었다. q.poll()-i 가 0보다 작거나 같으면 암호문이 종료되는 조건이므로 큐에 삽입 후 while문을 빠져나오도록 설정해주었다. ​ ✏️ 소스코드 pa.. 2021. 8. 12.
[swexpert] Intermediate / Stack2 / 1222, 1223, 1224 🅰 1222. 계산기 1 ​ ✏️ 문제 풀이 중위표기식으로 작성된 문자열을 후위표기식으로 변경해 연산 값을 도출하는 문제이다. 연산자는 + 하나뿐이라 연산자의 우선순위를 고려할 필요가 없었다. 데이터를 문자열로 읽어와 후위표기식으로 변경해주었다. 후위식으로 변경할 때는 스택에 연산자만 들어가고, 후위표기법을 연산할 때에는 스택에 정수만 들어가기 때문에 Stack을 Char형태, Int 형태 2개로 선언한 후 문제를 풀었다. char형식의 arr배열에 피연산자를 먼저 넣고, while문을 통해 Stack에 있는 연산자를 arr배열에 넣어주었다. 후위표기식 연산을 하기 위해 char형태로 저장되어 있는 정수들을 Character.getNumericValut(char a)를 통해 int형으로 변경해 주었으며,.. 2021. 8. 12.
[swexpert] Intermediate / Stack1 / 1217, 1218, 1219 🅰 1217. 거듭제곱 ​ ✏️ 문제 풀이 - 재귀호출을 이용하여 주어지는 입력값을 통해 거듭제곱 값을 구하는 문제이다. - Function(N,M) 함수를 만들어 M만큼 N을 곱해야 하므로 - Function(N, M-1)을 통해 재귀호출을 구현하였다. ​ ✏️ 소스코드 package stack1; import java.util.*; public class Sw1217 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); for (int test_case = 1; test_case 0 && visited[S2[v]] == false) { stack.push(S2[v]); visited[S2[v]] = true; }.. 2021. 8. 12.

티스토리툴바