알고리즘공부(Algorithm Study)83

• 

  백준 13549 java - 숨바꼭질 3(BFS) 단순한 BFS라고 생각하면 틀리는 문제이다. 조건이 필요한 BFS 문제이다. 1. 0 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 6.

• 

  백준 2470 java - 두 용액(투 포인터) package boj; import java.io.*; import java.util.*; public class Boj_2470 { public static void main(String[] args) throws Exception { // 완탐 불가능 //-99, -2, -1, 4, 98 // O O // O O // O O // O O // O O // O O // O O // O O // O O // O O // // O O // 4, 98 // O, O = // 이미 0이 된 경우는 그냥 답 // 왼쪽 끝 커서, 오른쪽 끝 커서로 시작 // 오른쪽 커서 움직이다가 이전보다 0에서 멀어지면 왼쪽 커서 움직임 // 왼쪽커서 < 오른쪽커서 일때까지 돌림 BufferedReader br = new Bu.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 5.

• 

  백준 3273 java 두 수의 합(투 포인터) 전형적인 투포인터 문제 였다. 잔디심기용으로 제격! 1. 각 끝에서 시작 2. 합보다 클경우 오른쪽 포인터를 --, 합보다 작은 경우 왼쪽 포인터를 ++ 3. 합과 같을 경우 왼쪽 ++, 오른쪽 ++ 4. 왼쪽 포인터 < 오른쪽포인터 일 때까지 반복 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Boj_3273 { public static void main(String[] args) throws NumberFormatException, .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 5.

• 

  백준 1504 java - 특정한 최단 경로(최적화된 다익스트라) 해당 문제는 다익스트라를 이용한 문제로 다익스트라를 까먹고 다시 공부해서 풀게 된 문제이다. 1. 정점의 개수 N(2 ≤ N ≤ 800), 간선의 개수 E(0 ≤ E ≤ 200,000), 거리 c (1 ≤ c ≤ 1,000) 2. 다익스트라를 3번 돌리면 된다. (1에서 한 번, v1에서 한 번, v2에서 한 번) 3. 최적화된 다익스트라 기준 시간 복잡도 O(logN*(N+M)) = O((N+M)logN)(N은 정점 수 , M은 간선 수) -> 3번 돌리므로 3*O((N+M)logN) 4. distance의 INF값은 무지성 Integer.MAX_VALUE를 쓰기보다 정확한 계산을 근거로 넣어야 하므로 싸이클 다 돈다고 생각하면 800 x 1000 이므로 800,000보다 큰 값을 INF값으로 대체해서.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 4.

• 

  백준 2914 java - 저작권 SSAFY에서 관통프로젝트 후 너무 눈이 아프고 집중도 안돼서 잔디심기용으로 풀어본 브론즈5 문제이다. 1. 자바의 나눗셈은 버림을 기본으로 함 2. 창영이 앨범에 수록된 곡에 포함되어 있는 저작권이 있는 멜로디의 개수) / (앨범에 수록된 곡의 개수) = 저작권이 있는 멜로디의 평균값 = X / A = I => 결국 A*(I-1)< X A*(I-1) < X 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 3.

• 

  백준 2178 java - 미로탐색 DP 문제, 대회 문제를 붙잡고 있다가 도저히 풀리지 않아서 도피용으로 푼 BFS 문제이다. 흑흑 1. 전형적인 bfs 문제이다. 2. 4방 delta를 만들어서 풀어야 한다. 3. 1,1 -> N,M 이기 시작점을 0,0이 아닌 1,1? -> 패딩을 활용하자 4. 최단거리이기 때문에 BFS를 통해서 풀어야 한다. -> DFS 활용하면 stackoverflow가 뜰 수도 있으니 조심하자 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.Stri.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 1.

• 

  백준 2110 java - 가운데를 말해요 해당 문제는 아이디어 도출 : 구현 = 3 : 2 정도 시간이 걸린 문제이다. 이중 우선순위큐 문제랑은 약간 다른 느낌이지만 결국 시간 제한 0.1초 이내에 풀려면 이중 우선순위큐를 써야한다는 점이 핵심이다. 1. 1 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 28.

• 

  백준 11286 java - 절댓값 힙 해당 문제는 최소힙 + CompareTo를 통해 풀 수 있었다. 그리고 자료형의 중요성과 문제를 제대로 읽어야 한 다는 것을 번 깨달은 문제이다... 1. 배열에 정수 x (x ≠ 0)를 넣는다. 2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. -> 가장 작은 수를 출력하라고? 최소힙(우선순위큐)을 쓰면 되겠네 3. 1 따로 클래스 선언해서 써야겠다. 5. 자료형을 순간 2^32승이 int형 범윈 줄 알고 int형을 썼어서 틀렸고 절댓값이 같을 때를 처리 하지 않아서 계속 틀렸다. -> 이왜틀 시전 package boj; import java.io.BufferedReader; i.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 27.

• 

  백준 11444 java - 피보나치 수 6 해당 문제는 그냥 우연찮게 맞추게 된 문제이다. 이리 저리 생각하다가 그냥 점화식을 행렬로 만들어볼까? 해서 그냥 만들어본 행렬의 곱이 피보나치수열이길래 행렬거듭제곱을 통해서 풀게 된 문제이다. 1. 1 = O(logN) 시간복잡도를 만들어야하는구나 3. 분할정복이 맞다! 4. 근데 어떻게 하지? 이전 배운 분할 정복은 곱셈, 행렬거듭제곱인데? 5. 행렬로 해볼까? 6. 행렬로 어떻게 피보나치 수열 점화식을 짜지? 7. 이렇게 하면 되려나? -> 이게 되네? 8. 코딩하자! 참고 : 모듈러연산 (A 연산 B) mod p= (A mod p 연산 B mod p) (나눗셈 연산은 페르마 소정리를 이용한.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 24.

• 

  백준 7662 JAVA - 이중 우선순위 큐 1. I value -> value 넣기 2. D -1 -> 최솟값 빼기 3. D 1 -> 최댓값 빼기 4. k 이 부분 때문에 1차 삽질함 후 한 달 만에 드디어 풀었다. 이 문제 붙잡고 있느라 사실상 하루 꼬박 걸린 것 같다. 1. I value -> value 넣기 2. D -1 -> 최솟값 빼기 3. D 1 -> 최댓값 빼기 4. k 이 부분 때문에 삽질함 문제명이 이중 우선순위큐라 오로지 우선순위 큐로만 풀고자 했었다 ㅜㅜ package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Collection; import java.util.Co.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 23.

• 

  백준 10830 java - 행렬 제곱 해당 문제는 아래의 두 문제를 조합해서 풀 수 있는 문제이다. 백준 1629 곱셈 문제의 경우 https://chaaany.tistory.com/40?category=957446 본인이 작성한 글이 있으니 참고하면 좋을 것 같다. 백준 1629 java - 곱셈(분할정복) 해당 문제는 쉽게 보면 쉽고 어렵게 보면 어려운 문제이다. 모듈러 연산을 활용한 것이기 때문에 모듈러의 특징을 잘 알아야 한다. 해당 문제에 대해서 두 가지의 풀이법으로 풀어보았으니 참고 chaaany.tistory.com https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 22.

• 

  백준 1629 java - 곱셈(분할정복) 해당 문제는 쉽게 보면 쉽고 어렵게 보면 어려운 문제이다. 모듈러 연산을 활용한 것이기 때문에 모듈러의 특징을 잘 알아야 한다. 해당 문제에 대해서 두 가지의 풀이법으로 풀어보았으니 참고하시라! 1. 거듭제곱의 지수는 합연산이다. ex1) x^7 = x^(1+3+3) -> x^(1+(1+1+1)+(1+1+1)) ex2) x^4 = x^(2+2) -> x^((1+1) + (1+1)); 2. 지수가 0일 때 1이며, 1일 때는 자기자신 이다. 3. 결국 f(x) x는 지수 x = 1일 때 x; x = 0일 때 1; x가 홀수 일 때 x * (x/2) *(x/2) x가 짝수 일 때 (x/2)*(x/2) 라는 점화식이 도출된다. 4. 모듈러 연산이란 합, 차, 곱연산에 대해서 (A 연산 B) mod C ==(동.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 21.