알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving)77

• 

  백준 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.

• 

  백준 1780 java - 종이의 개수 해당 문제는 전형적인 분할정복 문제이다. 크게 어려운 부분은 없었던 것 같다. for문에서 for문 변수로 안 돌려서 삽질한 부분 빼고;;; 1. N x N 크기 행렬 / 1 n/3씩 자르기 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Boj_1780 { static int N, arr[][], count[]; public static void main(String[] args) throws NumberFormatException, IOException { // N x N 크기 .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 20.

• 

  백준 5430 java - AC 타이머, 스톱워치, 시계가 필요할 땐 https://alittlekitten.github.io/SsocoTimer/ SsocoTimer 타이머/스톱워치 애플리케이션 SsocoTimers 입니다 :) 많이 사랑해주세요!! alittlekitten.github.io 배열로도 풀 수 있고 덱으로도 풀 수 있는 문제이다. 제일 먼저 배열로 풀까 했다가 단계별로 풀어보기 큐/덱이어서 덱으로 풀어보았다. 배열로 푸는 경우에는 투포인터로 start, end 부분을 조정해서 풀면 결국 덱과 같아진다. 1. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수 2. 함수 D는 첫 번째 수를 버리는 함수 - 배열이 비어있는데 D를 사용한 경우에는 에러 발생 3. 함수는 조합해서 한 번에 사용 4. T 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 19.

• 

  백준 1021- 회전하는 큐 JAVA 전형적으로 deque을 이용한 큐 돌리기 문제였다. 처음에는 문제를 잘못 읽어서 테스트케이스 2번이 어떻게 되나 했는데 그냥 시계방향, 반시계방향 돌리면서 해당 원소가 나올 때의 최솟값들을 합하면 된다는 것을 알았다. 1. 덱을 활용한 원형큐 느낌이 들었음 2. 시계방향, 반시계방향으로 움직이며 원소들을 일일이 확인하고 두 방향 중 최솟값을 answer에 더하면 끝 +참고: 덱은 front, tail부분에 삽입, 삭제, 조회가 가능한 자료구조이다. package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import jav.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 18.

• 

  백준 18258 - 큐 2 JAVA 해당 문제는 큐를 구현해보라는 문제다. 배열을 쓸지 리스트를 쓸지 고민하다가 이번엔 리스트를 써보았다. 1. 큐 클래스를 정의 2. 적절한 자료 구조 선택(배열/리스트 등) 3. 구현 4. 이항연산자 활용 해당 문제는 큐 구현 문제이다. 따라서 큐의 메소드가 뭐가 있는지 파악해두는 워밍업이라고 생각하면 좋을 것 같다. package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Boj_18258 { sta.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 17.

• 

  백준 2004 - 조합 0의 개수 JAVA 해당 문제는 아이디어가 생각날 듯 말 듯해서 누워서 생각하다가 한 10분 잠들었다가 일어났더니 생각나서 풀어버린 문제이다. 가끔 누워서 아이디어를 떠올리다 보면 풀리는 문제가 있다. 1. nCm = n! / ((n-m)! * m!)이다. 2. 끝자리 0의 갯수는 10이 얼마나 있느냐 = 2 * 5 쌍의 개수 3. 그냥 5의 배수 나열해 보기 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125... 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3 -> 5의 개수는 결국 특정 n에서의 5로 나눈 몫 + 5^2(25)로 나눈 몫... + 5^n으로 나눈 몫 고로 n! 이 포함하는.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 17.