백준25

• 

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

• 

  백준 11660 java - 구간 합 구하기 5(누적합) 이거 시간초과 나야 정상인 것 같은데 시간 초과가 애매하게 안났다. 1초 제한인데 최악 1,024 x 100,000이라서 102,400,000회=> 1초 될랑말랑이라 간당간당했나보다. 그냥 한 번 돌려봤는데 통과되서 놀랬다...! 사실 이러면 안되는 게 될까 말까가 아니라 이건 된다라는 마음으로 문제풀어야하는데... 요행을 바라는 건 실력이 아니다! ㅜ.ㅜ 1. 각 행 별로 누적합을 구해둔다. 2. 테스트 케이스 상 x좌표가 배열의 행좌표, y좌표가 열좌표이므로 헷갈리지 말자 -> 1트에 실패했음 3. 행별 구간합을 구해서 더 해준다. -> 소스코드 참조 package boj; import java.io.BufferedReader; import java.io.IOException; import java... 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 13.

• 

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

• 

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

• 

  백준 12865 - 평범한 배낭 JAVA 해당 문제는 DP의 대표적인 냅색(Knapsack-짐싸기)문제라고 한다. 하지만 본인은 1주일 동안 손을 대지 못하고 있었다. 왜냐하면 무게 W에 대해 중복된 가치를 가질 수 있는가에 대한 의문이 들었기 때문이다. 하지만 그건 기우였다. 중복된 가치가 되든 말든 상관이 없었다..! 드디어 동적 계획법 1까지 단계별로 풀기를 싹 밀었다! 하지만 5개월~6개월 전부터 시작해서 앞부분에 힘겹게 풀었던 것을 또 다시 풀라고 하면 풀 수 있을지는 의문이다. 내 머릿속의 지우개ㅜㅜ 이상한 소리 하지 않고 바로 문제 풀이/접근과정과 소스코드 공유하겠슴다. 1. 1 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 12.

• 

  백준 1912 - 연속합 JAVA 해당 문제는 손으로 끄적여가면서 풀다가 탁 깨달은 시점에서 술술 풀어나간 문제이다. 생각보다 매우 간단한 로직이지만 그동안 풀었던 문제들 + 단계별로 풀기 끝에 있다는 것을 감안해서 스스로 어려운 문제일 것이다라고 되뇌다가 시간이 오래 걸린 문제이다. -> "생각보다 쉬웠다"라는 뜻 1. n개의 정수, 1 1 + 2 가 최대고 -1,000일 때는 굳이 안 더해주는 게 나을지도? 3. 그렇다면 합한 수가 0보다 낮아지지 않는 시점까지는 연속합(누적합)을 해주다가 0보다 낮은 경우에는 그냥 연속합(누적합)에 넣는 것을 포기하고 다시 0보다 큰 수가 나오는 시점부터 합해주면 좋을 듯 하다. 4. 동시에 max값은 유지하면서 n번 째까지 다 돌았을 때의 max값이 답일 것이다. 일반적으로 입력을 받을 때 로직을.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 3.

• 

  백준 1932 - 정수 삼각형 JAVA 해당 문제는 DP(다이나믹 프로그래밍) 문제다. 보자마자 대략 어떤 식으로 풀면되겠다라고 생각이 든 문제였다. (해당 문제 접근과정) 1. subset 느낌으로 dfs로 코드를 짜봄 2. 점화식을 도출해서 DP로 바꿔봄 3. Scanner를 써서 시간이 좀 오래걸리는 것을 보고 BufferedReader로 재구현 글 보다 코드를 보는 게 더 편한 우리는 개발자이므로 DFS 소스코드와 DP소스코드 작성해 보았습니다. 1. DFS로 코드를 짠 경우 package boj; import java.util.Scanner; public class Boj_1932 { static int dp[][], N, max; public static void main(String[] args) { Scanner sc = new.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 26.

• 

  백준 14247 나무자르기 - JAVA 해당 문제를 풀 때 다음과 같이 접근했다. 1. 매일 매일 산에 오를 때마다 가장 큰 것을 자르면 어떨까? -> 테케에 맞지 않는다. 2. 나무가 자라는 게 등차 수열이네 -> 그러면 공차의 오름차순 대로 나무를 잘라볼까? -> 테케 맞음 3. 그러면 오름차순 정렬할 때 Arrays.sort를 쓸까? 4. 어차피 계속 배열을 유지할 필욘 없으니 PriorityQueue를 써볼까? 라는 의식흐름에서 나온게 다음과 같은 코드이다. -> 하지만 함정이 숨어 있었다...흑흑 다름아닌 데이터 타입... 최악의 상황을 가정해 보았다. 나무 100,000개에 등차가 10,000이고 첫항이 전부 100,000 일 경우 99999*100000/2*10000 + 100000 = 49,999,500,100,000 => lo.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 21.