본문 바로가기

분류 전체보기242

[알고리즘] 최대공약수(GCD), 최소공배수(LCM) - JAVA 최대공약수(GCD)GCD는 Greatest Common Divisor의 약자로 최대공약수이다. 두 수의 약수들의 공통된 값 중 최댓값을 말한다. GCD를 구하는 방법을 알아보자. 1. BigInteger 내장 함수private static int gcd(int a, int b) { BigInteger n = BigInteger.valueOf(a); BigInteger m = BigInteger.valueOf(b); return n.gcd(m).intValue();}2. 재귀private static int gcd(int a, int b) { if(b == 0) { return a; } return gcd(b, a % b);}3. 반복문private static.. 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.
[자료구조] 스택 & 큐 스택Stack 클래스에서 구현된 메서드는 다음과 같다. - `E push(E item)`:   스택의 맨 위에 요소를 추가한다. - `E pop()`:   스택의 맨 위 요소를 제거하고 제거된 요소를 반환한다. - `E peek()`:   스택의 맨 위 요소를 제거하지 않고 반환한다. - `boolean empty()`:   현재 스택에 요소가 존재하지 않을 경우 `true`, 그 외의 경우 `false`를 반환한다. - `int search(Object o)`:   스택의 상단부터 탐색하여 지정된 객체가 있는 요소의 위치를 반환한다. 없을 경우 `-1`을 반환한다. 스택은 먼저 들어온 데이터가 마지막에 나가는 구조이다. 페이지 뒤로가기, 실행 취소, 수식 괄호검사 등에서 응용된다. Stack 클래스는 .. 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.
[백준] 5464: 주차장 - JAVA https://www.acmicpc.net/problem/5464 풀이주자창의 칸별로 요금이 책정되어있고, 차량의 무게 \* 요금이 해당 차량의 무게가 된다. ParkingLot이라는 클래스를 만들었다. 주차장의 사이즈를 받아 배열을 선언하고, 메서드로 빈 칸이 있는지 보는 isEmpty(), 차량이 들어올 때 enter(), 차량이 나갈 때 요금정산까지 하는 out()메서드를 만들었다. 동작을 입력받으면서 주차장이 꽉 차서 못들어오는 차량의 대기열로 queue를 이용했다.  메모리: 14724KB시간: 160ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class ParkingLot { int[].. 2024. 5. 18.
[프로그래머스] 광고 삽입 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이시청자의 시청 시작, 종료 시각이 주어지고, 광고 지속 시간이 주어진다. 광고 지속 시간동안 누적 재생 시간이 가장 많은 구간을 골라야 한다. 누적합을 이용했다. 시청 시작시간에 +1 하고, 종료시간에 -1을 해놓고 누적합 배열을 끝까지 가면서 `preSum[i] += preSum[i - 1]` 해줬다. 누적합 배열을 완성한 후, 0 ~ 광고시간 까지를 첫 기준으로 삼아 1씩 늘려가면서 비교하며 .. 2024. 5. 18.
[백준] 1497: 기타콘서트 - JAVA https://www.acmicpc.net/problem/1497 풀이처음에는 기타마다 연주할 수 있는 곡을 비트마스킹으로 체크하려고 했으나 곡의 개수가 최대 50까지 되기 때문에 int범위에서 비트마스킹을 할 수 없었다. 따라서 boolean 이차원 배열을 만들어 체크했다. N개의 기타로 만들 수 있는 조합을 모두 만들어 연주할 수 있는 곡을 체크해줬다. 비트마스킹을 사용하려고 했던 것이 아쉬워 조합을 만들 때 비트마스킹을 이용했다.for (int i = 1; i 1부터 2의 N제곱까지의 자연수 중 비트의 자리수가 1인 것이 선택된 기타이다.  메모리: 14548KB시간: 136ms언어: Java 11import java.util.*;import java.io.*;public class Main { .. 2024. 5. 18.
[백준] 1062: 가르침 - JAVA https://www.acmicpc.net/problem/1062 풀이배운 알파벳을 체크하기 위해 비트마스킹을 이용했다. 알파벳은 26자인데 int자료형은 2의 31제곱까지 표현이 가능하므로 비트마스킹을 적용할 수 있다. a, n, t, i, c 5개 문자를 -97 해서 숫자로 바꾼 뒤 체크해주었다. K개의 글자를 배울 수 있으므로 조합을 통해 K개를 채워주었다. K개가 되었다면 주어진 단어 중 읽을 수 있는 단어를 카운트해줬다.  메모리: 15216KB시간: 300ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int N, K, ans; static String[] arr; public static .. 2024. 5. 18.
[백준] 2169: 로봇 조종하기 - JAVA https://www.acmicpc.net/problem/2169 풀이`(0, 0)`에서 `(N-1, M-1)`까지 각 칸의 값을 더하면서 가는데 최댓값을 구해야한다. 이동은 아래, 왼쪽, 오른쪽으로 이동할 수 있다. 첫번째 줄에서는 오른쪽으로 이동할 수 밖에 없다. 첫번째 줄의 dp를 먼저 채우고 아랫줄로 내려간다. 두번째 줄부터는 왼쪽, 오른쪽 모두 이동할 수 있다. 오른쪽으로 가는 경우, 왼쪽으로 가는 경우를 나눠 tmp라는 배열에 저장한다. 이때 위에서 내려오는 값과 바로 옆 칸에서 오는 값을 비교하여 저장한다. 오른쪽, 왼쪽 경우를 비교하여 dp배열에 채운다. `dp[N-1][M-1]`을 출력하면 끝.  메모리: 79660KB시간: 608ms언어: Java 11import java.util.*;.. 2024. 5. 18.
[백준] 20160: 야쿠르트 아줌마 야쿠르트 주세요 - JAVA https://www.acmicpc.net/problem/20160 풀이야쿠르트 아줌마의 판매 경로 10개가 주어진다. 아줌마가 해당 위치에 도착하기 전에 가있어야 아쿠르트를 살 수 있다. 먼저 내 시작위치로부터 각 위치까지 얼마나 걸리는지 다익스트라를 통해 구했다. 야쿠르트 아줌마의 시간을 누적해가면서 경로대로 움직였다. 아줌마의 현재위치부터 다익스트라를 통해 다음 위치까지 시간을 구했고, 해당 시간이 `Integer.MAX_VALUE`이면 그 다음 위치를 보는 식으로 구현했다. `ans`를 갱신하여 정점의 번호가 가장 낮은 것이 정답.  메모리: 68732KB시간: 920ms언어: Java 11import java.util.*;import java.io.*;public class Main { s.. 2024. 5. 18.

티스토리툴바