알고리즘공부(Algorithm Study)78 백준 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. 백준 24444 & 24445 알고리즘 수업 - 너비 우선 탐색1 & 너비우선 탐색 2 해당 문제를 잘못 이해한 부분이 있었다. 인접 정점을 오름차순, 내림차순으로 방문한다고 해서 특정 차수 기준 오름차순 방문인 줄 알고 PriorityQueue를 썼다가 여러번 시도 끝에 그냥 queue로 돌렸더니 pass가 됐다. 1. 시간 제한 : 1초 => 약 1억 번 연산 가능 2. 메모리 제한 : 512MB => 정수(4바이트) 기준 256 x 1024 x 512 개 생성 가능 = 2^8 x 2^10 x 2^9 = 2^27 3. N개 정점, M개 간선 & 무향 그래프 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤N) -> 2차원 배열로는 100,000 x 100,000이므로 인접리스트, 리스트로 풀어야 함 4. 1 ~.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 28. 백준 24479 & 24480 알고리즘 수업 - 깊이 우선 탐색 1&2(DFS) 이번에는 두 문제를 갖고와봤다. 백준 단계별로 풀어보기 1, 2번 문젠데 그냥 dfs를 오름차순, 내림차순으로 하느냐의 차이여서 java에서 오름, 내림차순 정렬하는 법만 알면 되니 한 큐에 풀어제꼈다 1. DFS로 풀어야한다. 2. 정점의 수가 100,000개까지이므로 100,000 x 100,000이므로 2차원 배열로는 안된다. 3. 리스트나 우선순위큐를 이용하여 풀어야 한다. 4. 리스트를 사용할 경우 정렬 함수를 써야하며 우선순위큐를 사용할 경우 오름차순인지 내림차순인지 정의해줘야 한다. -> 본인은 리스트 + 정렬 함수를 썼다. 정렬과 관련해서는 이전에 작성한 글을 참고하면 좋을 듯 하다. 2022.02.20 - [프로그래밍공부(ProgrammingStudy)/자바(JAVA)] - (JAVA/자.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 24. 백준 1520 java - 내리막길(DP, 동적계획법) 해당 문제는 자력으로 푼 건 아니고 다른 분의 풀이를 참고하여 푼 것이다. 왜 Queue를 사용한 bfs는 안되는 걸까 생각하다가 힙을 쓰면 된다고 생각하니 풀렸다. 정석으로는 탑다운 방식의 DP였다. 1. 내리막길의 개념은 현재 방문한 곳의 높이(값) 보다 다음에 방문할 곳의 값이 더 낮은 경우이다. 2. BFS+DP또는 DFS+DP로 풀면 된다. 3. 두 가지 접근법이 있는데 0,0(시작점-바텀업) 부터 아래로 쌓거나, M-1, N-1(도착점-탑다운)부터 쌓으면 된다. 4. 해당 문제는 dp다 보니까 탑다운, 바텀업 전부 되지만 나는 바텀업(0,0 부터 쌓기)방식으로 풀었다. 5. PriorityQueue를 쓰지 않으면 주변 내리막길이란 내리막길은 다 가기 때문에내리막길 다음의 그다음 제일 큰 내리막.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 23. 백준 11049 java - 행렬 곱셈 순서(DP/동적계획법) 해당 문제는 거진 3일? 4일? 생각했다가 파일합치기를 응용하면 된다는 것은 알지만 점화식이 도출안돼서 답답해하다가 범죄도시 2 영화 보고 카페와서 깨닫고 풀 수 있게 된 문제이다. 파일합치기에서 응용이므로 참고하면 좋을 것 같다. 2022.05.08 - [알고리즘공부(AlgorithmStudy)/문제풀이(ProblemSolving)] - 백준 11066 java - 파일합치기(DP) 백준 11066 java - 파일합치기(DP) 해당 문제의 경우 1주일 정도 붙잡고 있다가 결국 구선생님의 도움으로 풀게 된 문제이다. 아이디어 자체는 생각할 수 있었는데 그게 맞는 건지, 구현을 어떻게 해야하는 지 감이 오질 않았다. dp chaaany.tistory.com 1. 두 개의 파일을 합칠 때 필요한 비용 = .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 22. 백준 1358 java - 하키(기하/백준단계별로풀기 기하 clear) 2022.05.18 - [알고리즘공부(AlgorithmStudy)/문제풀이(ProblemSolving)] - 백준 1004 java - 어린왕자(기하) 백준 1004 java - 어린왕자(기하) 해당 문제는 이게 되나? 라고 했다가 테케 1번 맞추고 바로 제출하니 패스된 문제이다. 논리상 이거 밖에 없다!라고 해서 냈더니 너무 순순히 성공이 뜬... 신기하다. 1. 그림 chaaany.tistory.com 종전에 풀었던 어린왕자와 같이 원의 방정식과 좌표평면 상의 거리구하기 개념으로 접근하면 바로 풀린다. 기하는 그냥 아냐 모르냐의 개념이기에 바로 소스코드 들어간다. 1.1 x 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 19. 이전 1 2 3 4 5 6 7 다음 728x90