본문 바로가기

분류 전체보기215

백준 9655: 돌 게임(java) 문제풀이 문제 분류가 다이나믹 프로그래밍으로 되어 있지만 규칙을 파악한다면 정말 간단하게 풀이 가능하다.N=1일 때 상근이가 1개를 가져오면 무조건 승리하고, N=2일 때 상근이가 1개, 창영이가 1개를 가져올 수밖에 없으므로 창영이가 승리하며, N=3일 때는 상근이가 1개, 창영이가 1개, 상근이가 1개를 가져오거나 상근이가 3개를 가져올 수 있고 두 경우 모두 상근이가 승리한다. 이런 식으로 N을 증가시키며 계산해 보면, N이 홀수일 때는 상근이가, N이 짝수일 때는 창영이가 무조건 이긴다는 것을 알 수 있다. 전체 코드import java.util.Scanner;public class ex9655 {public static void main(String[] args) { Scanner scanne.. 2024. 9. 5.
백준 18870: 좌표 압축(java) 문제풀이 입력 순서 그대로 정렬하지 않은 배열과 오름차순으로 정렬한 배열 2개를 사용했는데, arr가 sortedArr보다 작아질 때까지 추가로 탐색하는 과정을 거치기 때문에 시간 초과로 표시된다. (접은글 참고)더보기import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStr.. 2024. 9. 3.
11659: 구간 합 구하기 4(java) 문제풀이 m부터 n까지의 부분 합은 0부터 m까지의 부분 합에서 0부터 (n-1)까지의 부분 합을 뺀 값임을 이용한다. 입력된 수들을 저장할 arr 배열과 0부터 n까지의 배열을 저장할 sum 배열을 선언했을 때, i부터 j까지의 부분 합은 (sum[j]-sum[i-1])이다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new.. 2024. 9. 2.
백준 3477: 버그왕(java) 문제풀이 파일이 끝날 때까지 입력받고, replaceAll()을 사용해 "BUG"를 ""으로 변경해 주면 되는데, 이상하게 계속 오류가 나던 문제이다.이때 BUG가 더 이상 존재하지 않을 때까지 replaceAll() 작업을 계속해야 한다는 점에 주의해야 한다.while((str=br.readLine())!=null) { while(str.contains("BUG")) { str=str.replaceAll("BUG", "");}문제에 주어진 "ABUBUGGB"의 경우, 첫 번째 replaceAll()로 BUG를 삭제(밑줄 친 부분)하면 " ABUGB"가 되어 다시 BUG 문자열이 생기므로, 이 경우 while문을 이용해 문자열에 BUG가 존재하지 않을 때까지 반복해야 한다. 전체 코드import jav.. 2024. 8. 31.
백준 10816: 숫자 2(java) 문제풀이 해시맵을 사용한 방법 또는 이분 탐색을 이용한 방법 2가지로 풀이할 수 있다.1. 해시맵 사용 카드와 그 카드의 개수를 각각 키와 값으로 가진 해시맵을 사용한다.if(hm.containsKey(input)) hm.put(input, hm.get(input)+1);else hm.put(input, 1);입력된 숫자가 해시맵에 존재하지 않을 경우(=처음으로 등장한 카드일 경우) 지금까지 한 장 등장한 것이므로 해시맵에 을 삽입하고, 입력된 숫자가 해시맵에 이전에 삽입된 적 있는 숫자일 경우 이전보다 한 장 더 등장한 것이므로 (n, (지금까지 해당 카드 개수)+1)을 삽입한다.if(hm.containsKey(input)) sb.append(hm.get(input)+" ");else sb.append.. 2024. 8. 28.
히프 응용-LPT 알고리즘 LPT(Longest Processing Time first): 가장 긴 작업을 우선적으로 할당하는 방법- 서로 다른 소요 시간을 가지는 작업들을 가장 짧은 시간 내에 마무리해야 할 때 LPT를 이용해 근사의 해를 찾을 수 있다. m개의 기계와 n개의 작업이 있고, 각 작업에 걸리는 기계의 사용 시간이 다르다고 가정하자. 모든 기계를 가동하여 최소의 시간 내에 작업들을 모두 끝내는 문제를 머신 스케줄링(machine scheduling)이라 한다. 이때 LPT를 활용해 문제를 해결할 수 있다. 아래와 같이 기계 사용 시간에 따라 정렬된 7개의 작업이 있고 동일한 기계가 3대 있을 때,J1J2J3J4J5J6J78765321 LPT 알고리즘은 각 작업들을 가장 먼저 사용 가능하게 되는(=이전 작업이 가장 빨.. 2024. 8. 26.

티스토리툴바