알고리즘공부(Algorithm Study)83 백준 2566 java - 최댓값(구현) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class boj_2566_최댓값 { static int input[][] = new int[10][10]; // 입력 받을 배열 - 패딩 static int maxValue = -1; // 출력할 최댓값 static int[] maxValueLoc = new int[2]; // 출력할 최댓값의 배열 행, 열 public static void main(String[] args) throws IOException { // 1. 9 x 9 배열 // 2. 0 이상 100 이하의 정수 // 3. 최댓값 찾기 // 4. 몇 행 몇 열인.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 11. 22. 백준 1916 java - 최소비용 구하기(다익스트라 알고리즘) 전형적인 다익스트라 문제이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.sql.Array; import java.util.*; public class Boj_1916_최소비용구하기 { public static void main(String[] args) throws IOException { PriorityQueue pq = new PriorityQueue(new Comparator() { @Override public int compare(int[] o1, int[] o2) { return o1[1] - o2[1]; } }); BufferedReader br .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 7. 15. 백준 1238 java - 파티(다익스트라) 해당 문제는 다익스트라 N번 또는 2번으로 풀 수 있는 문제이다. 1. N번 돌리는 경우에는 A -> X로 가는 경우 N-1번, X->A가는 경우 1번 해서 N번 돌리면 된다 2. 2번 돌리는 경우에는 X -> A로 가는 경우 1번과 간선을 반대 방향으로 저장한 간선리스트로 1번 다익스트라를 돌리면 된다. 3. 2번 다익스트라를 돌리는 경우가 가능한 이유는 X에서 다른 노드에 가는 경우는 이해가 되겠지만 간선리스트를 반대방향으로 저장한 경우 특정 노드에서 X로 가는 길이가 바로 A -> X로 가는 경우 N-1번과 동치이기 때문이다. package 다익스트라; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStr.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 7. 3. 백준 14938 java - 서강 그라운드(플루이드와샬, 다익스트라) 해당 문제는 35분여간 bfs로 풀다가 밑에 문제 분류 보고 플루이드와샬, 다익스트라인 걸 보고 바로 플루이드와샬로 돌려서 풀었다. 그 과정에서 문제를 입력값을 제대로 안봐서 m, r를 혼동하는 바람에 이왜틀 3분간 시전... 1. A에서 B까지 가는 거리가 m(수색가능 범위) 이내면 아이템 회수 가능 2. BFS돌리면서 계속 합해줘서 MAX값 찾아야 겠다. 3. 이왜틀???? 아! bfs로 방문처리하면 더 최단거리가 될 수 있음에도 불구하고 방문처리돼서 최단거리로 가는 게 아닐 수 있겠구나 4. 다익스트라 구현보다 플루이드와샬이 구현할 때 더 빠르니까 플와 써야겠다. 5. 문제 접근, 풀이, 제출, pass까지 약 50분 소요 import java.io.BufferedReader; import java.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 7. 2. 백준 1865 java - 웜홀(벨만 포드 알고리즘) 해당 문제는 벨만포드 알고리즘을 사용하는 문제이다. 본인은 벨만 포드 알고리즘을 알고 있지 않아서 약 2시간 30분만의 사투 끝에 구글링을 통해 공부하여서 맞췄다... 맞췄다기 보다 맞춤당했다. 핵심은 음수 사이클 판별하는 알고리즘으로 벨만포드를 사용할 수 있다는 점이다. 풀이법은 따로 남기지 않고 동빈나님 강의를 링크로 달아두겠다! https://www.youtube.com/watch?v=Ppimbaxm8d8 package 그래프_DFS; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStre.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 6. 30. 백준 1918 java - 후위 표기식(자료구조-스택) 해당 문제는 예~전에 SWEA에서 풀었던 건데 오랜만에 푸니까 시간이 좀 걸렸다... 알고리즘은 꾸준히! 뭐든지 꾸준히 ㅎ는 게 생명이다! 1. 연산자 우선순위 할당 2. 연산자 stack 생성 3. 숫자는 바로 출력 4. 연산자 우선순위 비교 후 낮은 걸 만나거나 더이상 쌓을 연산자가 없으면 pop 5. 괄호 처리 - ( 일때는 stack에 push해 두고 )를 만나면 ( 전까지의 모든 연산자를 pop package 자료구조; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class boj_1918_후위표기식 { public st.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 6. 29. 백준 9465 - java 스티커(동적계획법) 1. 손으로 그려가며 가능한 조합이 어떻게 되는 지 확인 O X O X O X 또는 O X O X X O 뿐이라는 것을 확인 2. 앞의 결과가 뒤에도 영향을 미친다는 것을 인식 3. DP인 것을 어렴풋이 느낌 4. 점화식을 세워보았음 dp[0][n] = max(arr[0][n] + dp[1][n-1], arr[0][n] + dp[1][n-2]) dp[1][n] = max(arr[1][n] + dp[0][n-1], arr[1][n] + dp[0][n-2]) 5. 결국 답은 dp값을 구한 후 Max값을 출력하는 것임 6. 이 생각까지 다다르는 데 약 20분이 걸리고 코드 작성은 10분 가량 걸린 것으로 추정 해당 문제를 풀고 제출한 후 속도가 시간이 단순 System.out.println과 StringBui.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 6. 28. 백준 24416 java - 피보나치 수1(동적계획법/DP) 백준 단계별로 풀기에서 동적계획법1이 all solve이었는데 갑자기 한 문제가 추가 되어서 풀게 된 문제이다. 브론즈 1이지만 DP의 효율성을 알 게 해주는 아주 귀중한 문제이다. 수도 코드가 이미 있어서 따라 치기만 해도 된다. package 동적계획법; import java.util.*; import java.io.*; public class Boj_24416_알고리즘수업_피보나치 { static int a, b, dp[]; public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp = new int[n+1]; dp[1] = 1; dp[2] = 1.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 6. 17. 백준 1707 java 이분그래프 (그래프) 이분그래프에 대한 정의를 이해 하지 못해서 한 1주일 정도는 그냥 바라본 문제다. 답지를 보기에는 골드4라는 티어 때문에 용납이 되지 않았고 금방 풀 수 있을 것 같아서 뚫어져라 쳐다 봤다. 결국 두색 칠하기 문제로 귀결되는 듯 보였다. 1. 인접한 두 수는 다른 색, 다른 숫자, 다른 그룹으로 짝지어 질 수 있는가 2. 그렇다면 조합으로는 안되나? => 조합으로는 시간 복잡도가 터질 수 있음 3. dfs 또는 bfs를 돌리며 색칠해 나가다가 인접한 정점이 같은 색깔 또는 같은 숫자인지를 보면 되겠구나 4. 간선이 연결되지 않은 정점들은 어떻게 처리하지? 5. 간선이 연결되지 않은 정점들은 또 dfs 또는 bfs를 돌리면서 집합을 두 집합으로 만들면 되겠구나! 1번 집합 2번 집합이 나오면 3번 집합/4.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 6. 15. 백준 7569 java - 토마토(그래프/bfs) 해당 문제는 3차원 배열의 6방 bfs문제이다. 딱히 다른 bfs문제와 별다를게 없으므로 바로 해설 들어간다. 1. 토마토가 익었을 경우 1, 날 것일 경우 0, 썩었을 경우 -1 2. H, M, N은 각각 상자의 층수, 상자의 가로칸, 세로칸 크기이다. 3. 익은 토마토는 그 다음차례에 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향의 토마토에 영향을 주어 익게한다. 4. 답 출력에 두 가지 방법이 떠올랐다. - 미리 익지 않은 토마토를 세서 bfs 돌린 후 최종적으로 익은 토마토와 익지 않았던 토마토의 갯수가 같으면 다 익은 것이므로 일수 출력 아니면 -1 출력 - bfs를 돌린 후 익지 않은 토마토가 있나 확인 후 없으면 일수 출력 아니면 -1 출력 5. 처음부터 싱싱한 토마토가 없는 경우에는 1을.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 30. 백준 1637 java - 날카로운 눈(이진탐색, 누적합, 정수론/feat.생애첫플레 1솔) 해당 문제는 결국 구선생님의 힘을 빌어서 풀게 되었으나 그래도 나만의 방식으로 풀어냈다. 이진탐색 + 누적합 + 정수론의 조합이기 때문에 좀 까다로웠다. 정수론이라고 치기에 애매하긴 하지만... 생애 첫 플레티넘 문제 1솔을 했다!! 1. 이진탐색(매개변수탐색)은 결국 순서대로 탐색하기 + 단절점 찾기가 핵심이다. 2. 일단 탐색할 값을 뭐로 할 지 정해야하는데 입력값중 압도적으로 큰 21XXXXX이 있어서 탐색값은 1 (C - A) / B + 1 의 누적합이 짝수인 경우에는 무조건 NOTHING일 수밖에 없다 왜냐하면 홀수개인게 하나고 나머지가 짝수이므로 누적합이 짝수인 경우에는 무조건 홀수가 없다는 뜻이기 때문이다. 5. 정답을 출력할 때는 홀수 개가 존재하는 특정 숫자에다가 그 숫자의 갯수를 출력해.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 29. 백준 12015 java - 가장 긴 증가하는 부분 수열 2(이진 탐색/2가지 풀이) 어제 오늘은 이진탐색 부수기를 하고 있다. 드디어 백준 단계별로 풀기에서 이진탐색을 밀었다! 이진 탐색에 대해서 심리적 거부감이 있던 터라 극복하면 보이지 않는 벽을 부순다는 일념으로 열심히 도전했다. 이진 탐색은 결국 매개변수 탐색과 연결된다는 점이 핵심인 것 같다. 풀이는 List 활용 방식과 Array(배열) 탐색 방식이며 Array방식이 시간이 더 짧다. ( 756ms[List] > 592ms[Array]) 1. 이진탐색(매개변수 탐색)을 사용하기 위해서는 다음 두 가지 조건이 필요하다. 1.1 순차대로 탐색이 가능해야한다. 1.2 특정 단절점이 있어야 한다. 2. 거진 반나절을 꼬박 생각해도 특정 위 두 가지 조건에 맞추는 방법을 생각지 못해서 구글링을 했더니 list 풀이 방식이 나왔다. 3... 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 29. 이전 1 2 3 4 5 6 7 다음 728x90
