본문 바로가기

Algorithm85

[Java] 프로그래머스 - 마법의 엘리베이터 https://school.programmers.co.kr/learn/courses/30/lessons/148653?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 시나리오 현재 층수의 일의 자릿수를 조사, 5보다 크면 (10-일의 자릿수)만큼 덧셈하고, 작으면 일의 자릿수만큼 뺄셈하여 끝자리를 0으로 맞춘다. 한번에 이동할 수 있는 층수는 절댓값이 \(10^c)\인 정수이기 때문이다. 일의 자릿수를 덧셈/뺄셈하여 끝자리를 맞췄다면 다음으로 십의 자릿수를 조사, 같은 방법으로 해당 자릿수를 0으로 맞춘다. 이 과정은 가장 앞자리까지.. 2023. 4. 28.
[Java] 백준 18870 - 좌표 압축 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 시나리오 주어진 좌표 \(X_i\)을 압축 알고리즘을 적용하여 결과 좌표 \(X'_i\)를 출력하는 문제이다. 여기서 압축 알고리즘에 대한 규칙은 제시되어 있지 않아 추론해봐야 하는데, 문제 조건 중 좌표를 압축한 결과 \(X'_i\)의 값은 \(X_i > X_j\)를 만족하는 서로 다른 좌표의 개수와 같아야 한다고 한다. 이점과 주어진 예제를 고.. 2023. 4. 21.
[Java]백준 1260 - DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 주어진 정수를 입력받아 인접행렬 혹은 인접리스트를 만들고 DFS와 BFS로 탐색하는 문제이다. DFS, BFS문제는 파이썬으로 많이 풀어봤지만 자바로는 한 번도 시도해보지 못했다. 언젠간 자바로도 그래프 문제를 풀어야 하니 생각난 김에 오늘 시작하게 되었다. 시나리오 정점의 수, 간선의 수, 시작점이 각각 첫번째 줄에 주어지고 나머지 줄은 두 정점이 이어진 정.. 2023. 4. 20.
[Java] 백준 1927 - 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net min-heap을 구하는 간단한 문제이다. 다만 자바로 힙을 구하는 문제는 처음이다 보니 힙 자료구조가 구현된 클래스가 있는지 조차 잘 몰랐다. 그래서 구글링 해보니 PrioriryQueue라는 자료구조가 있었고 디폴트가 트리의 탑이 최솟값이 되는 min-heap이었기 때문에 클래스만 가져다 사용하면 문제해결이 가능했다. import java.io.IOException; imp.. 2023. 4. 14.
[Java] 백준 1003 - 피보나치 함수 https://www.acmicpc.net/problem/1003 각 테스트 케이스마다 0과 1이 출력되는 횟수를 구하는 문제이다. 코드 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int tc = Integer.parseInt(br.readLine()); for (int i = 0; i < tc; i++) { int N = Integer.parseInt(br.readLine()); int[][] fibonacci = new int[41][2]; //초기값 fibonacci[0.. 2023. 4. 13.
[Java] 백준 9375 - 패션왕 신해빈 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 시나리오 케이스 하나에 n개의 의상의 이름, 의상의 종류가 주어진다. 같은 종류의 의상은 하나만 입을 수 있는데 이때, 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 구하라고 한다. 따라서 의상 조합의 모든 경우의 수를 구하되, 하나의 옷만 입어도 알몸이 아닌 것으로 간주되기 때문에 종류별 의상 개수에 .. 2023. 4. 12.
[Java] 백준 1620 - 나는야 포켓몬 마스터 이다솜 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제가 너무 긴 관계로 삽입은 생략한다. 결국엔 영문으로된 포켓몬의 이름을 N개 입력받고 추가로 입력된 M개의 포켓몬 이름 또는 숫자에 매칭되는 포켓몬 이름, 숫자 중 하나를 출력하면 되는 문제이다. 내 코드 \(N\)과 \(M\)은 100,000보다 작거나 같기 때문에 \(O(N)\)의 시간복잡도 내에 풀어야 하는 문제이다. 배열로 풀게된다면 indexOf등의 메서드.. 2023. 4. 12.
[Java] 프로그래머스 Lv2. 숫자 변환하기 모법 답안 import java.util.*; class Solution { int[] dp = new int[3000003]; int INF = 1000002; public int solution(int x, int y, int n) { int answer = 0; Arrays.fill(dp, INF); dp[x] = -1; dp[y] = 0; for(int num = Math.max(y - n, Math.max(y / 2, y / 3)); num >= x; num--){ dp[num] = Math.min(dp[num + n] + 1, Math.min(dp[num * 2] + 1, dp[num * 3] + 1)); } return dp[x] >= INF ? -1 : dp[x]; } } 내 풀이(실패, .. 2023. 4. 8.
[Java] 백준 2217 - 로프 문제 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 입력 첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수.. 2023. 4. 8.

티스토리툴바