알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving)72 백준 2559 java - 수열(누적합) 누적합을 활용한 문제이다. 시그마(sum) 시그마(1~N) - 시그마(1-M) = 시그마(M+1 ~ N)이라는 식만 알고 있으면 되는 문제이다. 1. N은 2이상 100,000이하, K는 1이상 N사이의 정수 -> int 자료형까지만 필요 2. 누적합을 이용해서 풀어봐야겠다 3. 입력 받는 즉시 바로 누적합으로 빼서도 구할 수 있겠군 4. sum 배열 다 구한 후에 또 for문 돌리면 시간 차이가 많이 나나? 5. 최솟값은 -20,000,000정도까지 나올 수 있겠군? import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 10. 백준 11066 java - 파일합치기(DP) 해당 문제의 경우 1주일 정도 붙잡고 있다가 결국 구선생님의 도움으로 풀게 된 문제이다. 아이디어 자체는 생각할 수 있었는데 그게 맞는 건지, 구현을 어떻게 해야하는 지 감이 오질 않았다. dp의 세계는 정말 무궁무진한 것 같다. 1. 두 개의 파일을 합칠 때 필요한 비용 = 두 파일 크기의 합 2. 최종파일 만드는 데 합치는 횟수 = 총 파일 -1 3. 서로 인접한 파일들끼리만 합칠 수 있음 4. 테스트케이스 관찰 결과 C1 + C2 / C1 + C2 + C3 / C1 + C2 + C3 + C4 = 3*C1 + 3*C2 + 2*C3 + C4 = 9 / 3 3 2 1 C1 + C2 / C3 + C4 / C1 + C2 + C3 + C4 = 2*(C1 + C2 + C3 + C4) = 8 = 2 2 2 2 C.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 8. 백준 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. 이전 1 2 3 4 5 6 다음 728x90