전체 글354

• 

  [프로그래머스] 광물 캐기 - java 나의 풀이 import java.util.*; class Solution { public int solution(int[] picks, String[] minerals) { int[][] weights = {{1,1,1},{5,1,1},{25,5,1}}; int answer = 0; int pickCnt = Arrays.stream(picks).sum(); // 광물을 5개씩 묶은 그룹들을 각 그룹의 광물의 가중치 합의 내림차순에 따라 정렬한 큐 // 다이아몬드->1 철->5 돌->25 PriorityQueue groups = new PriorityQueue(Collections.reverseOrder()); for(int i=0; i 0){ // 다이아몬드 곡괭이 사용 picks[0]--; pick =.. 알고리즘/그리디 2023. 8. 6.

• 

  [백준] 14719번: 빗물 - java 1. 왼쪽 -> 오른쪽으로 벽의 최대 높이를 저장한다. 이때 비교하는 벽의 기준의 height(지금까지 중 가장 높은 블럭) 이다. 2. 오른쪽 -> 왼쪽으로 벽의 최대 높이를 저장한다. 1 과 2 에서 저장된 높이 중 더 작은 높이를 벽의 높이로 저장하며, 빗물이 고인 양을 구하기 위해 [ 블록 높이 - 벽높이 ] 로 계산한다. 나의코드 import java.io.*; import java.util.StringTokenizer; public class Main { static int h, w, height, answer, blocks[], rain[]; public static void main(String[] args) throws IOException { BufferedReader br = new .. 알고리즘/구현 2023. 7. 7.

• 

  [프로그래머스] 합승 택시 요금 - java 나의 풀이 import java.util.*; class Solution { static final int MAX = 20000001; static ArrayList[] graph; public int solution(int n, int s, int a, int b, int[][] fares) { int answer = MAX; graph = new ArrayList[n+1]; for(int i=0; ia & i->b 까지 따로간다. answer = Math.min(answer, start[i] + startA[i] + startB[i]); } return answer; } public int[] dijkstra(int start, int n){ int[] dist = new int[n+1]; // di.. 알고리즘/Graph 그래프 2023. 4. 24.

• 

  [백준] 1253번: 좋다 - java 구상하기 정렬이 필수다. => 정렬이 된 숫자 배열을 투포인터로 탐색한다면, O(n) 안에 어떤 숫자가 두 개의 합으로 나타낼 수 있는지를 확인할 수 있다. left, right 값을 설정해주는데, 정렬을 해주었다고 right값을 (현재 숫자의 인덱스 - 1) 로 해서는 안된다!! -> 음수가 있어서 현재 숫자보다 큰 수와 더해도 현재 숫자가 나올 수 있다 각 포인터 값의 합이 현재 숫자보다 크다면, 더 작은 수와 더해야하므로 right-- 반대로 현재 숫자보다 작다면, 더 큰 수와 더해야 하므로 left++ 나의 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.. 알고리즘/이것저것 2023. 4. 17.

• 

  sqld 하루 벼락치기,,, 합격! 노랭이 책으로 하루전에 빡집중해서 풀었다 ^^7 이렇게나 고득점일 줄은 몰랐는데,,, 운이 좋았나보다 ~~~! 전공자분들은 며칠동안 노랭이 책만 풀면 고득점 너무 가능입니다..! 저는 하루전날 5시간 정도 공부한 것 같아요 :) 그냥 개념 몰라도 냅다 해답펼쳐놓고 같이 풀었습니다 ~! 그리고 암기해야 하는 부분은 잘 정리해두신 블로그 참조했습니다! 주절주절 2023. 4. 7.

• 

  [swea] 5607번: [Professional] 조합 - java 페르마의 소정리를 모르면 못 푸는 문제... 페르마의 소정리란 p가 소수이고, a가 p로 나누어지지 않는 정수 일 때 성립하는 법칙이다. 이 문제에서 정답을 구하기 위해선 결국 (n! / r! (n-r)!) 를 1234567891 로 나눈 나머지 값, 즉, (n! / r! (n-r)!) % 1234567891 을 구해야 한다. 결국 모듈러의 연산 공식을 활용해야 하는데, 모듈러 연산에서 나눗셈 연산은 허용되지 않는다! 즉, r! (n-r)! 의 분모에 대한 모듈러 연산은 분배법칙을 적용할 수가 없음을 뜻한다. 따라서 모듈러 연산의 곱셈의 분배법칙을 이용해야 한다!! (n! / r! (n-r)!) 을 곱셈꼴로 만들기 위해선 역원을 이용해야 한다! 와 같다. 이때, 페르마의 소정리를 이용한다면 아래와 같다... 알고리즘/이것저것 2023. 4. 6.

• 

  [백준] 2933번 : 미네랄 - java 전체적인 단계 구상은 다음과 같다. 1. 주어진 높이와 방향에서 (왼->오 or 오->왼) 미네랄 파괴 2. 파괴 후, 공중에 떠 있는 클러스트가 있는지 확인 (BFS 탐색으로 클러스트에서 가장 아래에 있는 미네랄이 바닥이 아니라면, 떠 있는 것으로 간주) 3. 공중에 떠 있는 클러스트라면, 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지도록 이동시키기 // 단, 떨어지는 동안 클러스터의 모양은 변하지 않는다. => 클러스트에 포함된 미네랄은 모두 같은 높이로 떨어진다. // 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우는 없다. => 공중에 떠 있는 1개의 클러스터를 발견하면, 더 이상의 클러스트 탐색은 할 필요가 없다. 1) x -> . 로 변경 2) 공중에 떠 있는 클러스트 확인 (.. 알고리즘/구현 2023. 4. 3.

• 

  [백준] 11657번: 타임머신 - java 음수가중치가 있는 문제이므로 다익스트라로는 최단 경로를 갱신할 수 없다. => 다익스트라는 이미 방문한 노드에 대해서는 더 이상 경로탐색을 하지 않기에 (더 탐색하면 양의 가중치를 더 얻게 되므로 당연히 탐색할 필요X) 최단 경로를 판별할 수 없다. 따라서 벨만포드를 사용해서 모든 edge에 대해서 edge relaxation 을 (V-1) 번 수행해준다. 그런데 왜 V-1 만큼일까? V-1 만큼 모든 간선을 탐색하는 것이 확 와닿지가 않았다. 그림으로 이해해보자. 출발점이 A라고 생각해보자. 1번째 방문시, 다음과 같이 갱신이 된다. 사실 A->D 간선이 먼저 갱신된다면 1번째 방문에서 D->C 도 갱신되겠지만, 최악의 경우를 고려했을 때는 아래와 같다. 간선의 순서와 상관없이 A에서 출발하는 간선의 .. 알고리즘/최단경로 2023. 3. 29.

• 

  [백준] 1238번: 파티 - java 아이디어 V = 정점의 갯수 E = 간선의 갯수 T = 목적지 (파티가 열리는 곳) 라고 할 때 다익스트라를 V번 반복하지 않아도 이 문제를 풀 수 있다. 1) T를 출발 노드로 하여 다익스트라 알고리즘을 돌린다. => T에서 출발해서 다른 노드로 가는 최단경로를 모두 구한다. 그럼 이제 임의의 노드 x에서 출발해서 T로 오는 거리만 찾으면 답을 구할 수 있다. 2) x -> T 거리를 구하기 위해선 출발노드 x가 매번 다르기 때문에 다익스트라를 n번 반복해야 한다. 하지만 그래프 간선방향을 거꾸로 뒤집고, (1->3 을 3->1 으로 변경) T 노드를 출발 노드로 하여 다익스트라를 돌리면 x -> T 의 거리를 모두 구할 수 있다. 3) 1, 2 에서 구한 거리를 더해서 가장 큰 값을 찾는다! 이렇게 .. 알고리즘/최단경로 2023. 3. 28.

• 

  [백준] 1937번: 욕심쟁이 판다 - java 만약 모든 칸에서 DFS 탐색을 한다면 매 칸에서 최대 n^2만큼 이동할 수 있다. 따라서 n^2의 칸에서 n^2 만큼의 탐색을 한다면 O(n^4) 로 시간 복잡도가 터져버릴 것이다. 따라서 DP를 이용해서 이미 DFS 를 탐색한 칸에 대해서는 값을 저장해서 탐색 횟수를 줄여야 한다. dp => 해당 칸에서의 최장 경로를 저장해둔 것이다. 즉, 다른 칸(a)에서 탐색을 하다가 이미 방문한 칸(b)을 탐색하게 된다면, b에서 계속해서 탐색을 할 필요가 없이, b칸에 저장되어 있는 dp값을 더하기만 하면 된다. dp[i][j] => 판다가 (i,j) 에서 출발할 때 최대로 이동할 수 있는 칸 수 를 의미한다. 1) 모든 칸에서 탐색 시작 2) DFS 탐색 상 하 좌 우를 탐색하며, 현재 칸 보다 다음칸에 더.. 알고리즘/동적프로그래밍(DP) 2023. 3. 21.

• 

  [백준] 3020번: 개똥벌레 - java 아이디어 동굴의 길이 N만큼 장애물 배열을 만들고, 구간별 파괴해야하는 장애물의 수를 구한다면 (N크기 : 20만 X H크기 : 50만) 으로 시간초과 가 날 것이다. 따라서 장애물 배열을 구간의 개수인 H만큼 만들고, N만큼의 입력에 대해 장애물의 길이에 해당하는 인덱스에 갯수를 카운트 해주었다. => 해당 길이의 장애물이 몇 개 있는지를 카운트한다. => top[1] = 0 top[2] = 2 top[3] = 3 top[4] = 0 top[5] = 2 down[1] = 1 down[2] = 1 down[3] = 4 down[4] = 1 down[5] = 0 만약 길이가 1,2,3,4 인 종유석이 4개 있다고 가정하고, 아래에서부터 2번째 구간을 지나간다고 생각해보자. 2번째 구간을 지나간다면 파괴해야.. 카테고리 없음 2023. 3. 14.

• 

  [백준] 1493번: 박스 채우기 - java 나의 풀이 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static BufferedReader br; static BufferedWriter bw; static StringBuilder sb; static StringTokenizer st; static int L, W, H, N, min_cnt; static int[] cu.. 알고리즘/이것저것 2023. 3. 6.