문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 어떻게 풀 것인가? 기존의 다익스트라 알고리즘을 사용해도 무방하나, 다만 최단경로가 지나온 노드들을 보여줘야 하고, 그리고 지나온 노드들의 갯수를 보여줘야 한다. 이에 나는 route로 지나온 노들을 담으며, 이후에 while 문을 이용하여 routes에 정답의 경로들을 전부다 담는 로직을 세웠다. 출발 노드 -> 목적 노드까지는 모든 노드를 거치지 않을 수도..
문제 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 어떻게 풀 것인가? 처음에 보고 조금 당황스러웠다. DP로 풀기에는 너무나도 큰 수 이다. 아마 처음에 단순 DP로 접근했다면 분명히 시간초과가 발생했을 것이다. 그렇다면 이러한 시간초과 부분을 획기적으로 줄일 수 있는 것이 무엇이 있을까? 바로 행렬이다. 사실 백준알고리즘을 많이 풀어본 이들이라면 위와 같은 피보나치 문제들은 많이 봐왔기 때문에 아래와 같은 점화식은 익숙할 것이다. D(n+2) = D(n+1) + D(n) ( D0 = 0, D1 = 1, n >= 0)..
문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 어떻게 풀 것인가? 문제를 읽어보자. 예제 1에서 "mirkovC4nizCC44" 이라는 문자열에 "C4"라는 문자열이 포함되어있으면 모두 없애야 한다. 케이스로 살펴보자. Case 1 : mirkovC4nizCC44 => mirkovnizCC44 Case 2 : mirkovnizCC44 => mirkovnizC4 Case 3 : mirkovnizC4 => mirkovniz(정..
문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 어떻게 풀 것인가? 최단경로 다익스트라 알고리즘을 사용하여 풀어야하는 문제이다. 하지만 무조건 V1와 V2를 지나야 한다. 해결법은 간단하다. 시작점 -> V1 까지 가는 최단경로 비용 V1 -> V2 까지 가는 최단경로 비용 V2 -> 목적지 까지 가는 최단경로 비용 즉, 최단경로를 3번 사용하여 위3개의 최단경로 비용의 합을 구하면 된다. 단 ..
문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 어떻게 풀 것인가? 문제를 잘 읽어보자. 웜홀에 들어가면 시간은 뒤로간다. 그말인 즉슨 현재 간선 간의 가중치가 시간이라는 점에서 웜홀의 간선은 음의 가중치를 갖는 것이다. 다시말하면 다익스트라 알고리즘으로는 풀 수가 없다. 그렇다면 문제에서 요구하는 것은 무엇일까? 바로 벨만 - 포드 알고리즘이다. 즉, 현재 문제가 원하는 것은 벨만 포드 알고리즘을 이용하여 음수 사이클이 발생..
문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 어떻게 풀 것인가? LIS와 LDS의 혼합 문제였다. 처음에 LIS를 시행이후에 LDS를 시행하면 문제가 원하는 최장 바이토닉 수열의 길이가 나온다. 간단했다. 아래는 LIS 와 LDS의 정리글이다. https://superohinsung.tistory.com/199 [Algorithm] LIS, LDS (최장 증가 부분 수열, 최장 감소 부분 수열) 최장 증가 부분 수열(LIS, Longest Increasi..
최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)은 주어진 수열에서 요소들이 증가하는 순서대로 선택되는 가장 긴 부분 수열을 말한다. 즉, 주어진 수열에서 원래 순서를 유지하면서 순서대로 증가하는 숫자들을 선택하여 만들 수 있는 가 장 긴부분 수열을 찾는 문제이다. 예를 들어 수열 {3, 1, 5, 2, 4}가 주어졌을 때, 이 수열의 최장 증가 부분 수열은 {1, 2, 4}가 된다. 이 부분 수열은 원래 수열의 순서를 유지하면서 각 요소가 증가하는 순서대로 선택되었기 때문에 최장 증가 수열 부분이라고 할 수 있다. 최장 증가 부분 수열은 다이나믹 프로그래밍(DP)와 이분탐색을 이..
동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming, DP)란 컴퓨터 프로그래밍 기법 중 하나로, 주로 최적화 문제나 중복되는 부분 문제를 효율적으로 해결하는 데 사용되는 알고리즘 설계 기법이다. 이는 큰 문제를 작은 부분 문제로 쪼개어 해결하는 분할 정복(Divide and Conquer)과 유사하지만, DP는 중복되는 부분 문제들을 한 번만 계산하고 이를 이용하여 전체 문제를 해결한다. 즉,한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘. -> 점화식을 요구하는 이유이기도 하다. DP의 핵심 아이디어는 "작은 문제들의 해를 저장하고 재활용함으로써 전체 문제의 해를 구하는 것"이다. 이를 통해 중복 계산을 피하고 실행 시간을 크게 줄일 수 있습니다..
이번에는 자바에서 큐를 사용해보자. 이전에 큐는 무엇인가에 대하여 공부했다. https://superohinsung.tistory.com/178 [DataStructure] 큐(Queue) feat. C, Java 자료구조 큐에 대해서 정리를 해보자. 큐(Queue)란 큐(Queue)는 컴퓨터 과학에서 사용되는 선형적 자료구조 중 하나이다. 큐는 데이터를 일시적으로 저장하거나 관리하는데 사용되며, 데이터를 먼 superohinsung.tistory.com Java Queue 클래스 java.util 패키지에서 Queue 클래스 제공 메서드 소개 boolean add(E e): 큐의 끝에 요소를 추가한다. 큐가 가득 찬 경우 예외(IllegalStateException)를 발생시킨다. boolean off..
이번에는 자바에서 스택을 사용해보자. 이전에 스택이 무엇인가에 대하여 공부했다. https://superohinsung.tistory.com/177 [DataStructure] 스택(Stack) feat. C, Java 자료구조 스택에 대해서 정리를 해보자. 스택(Stack)이란 스택(Stack)은 컴퓨터 과학에서 사용되는 선형 자료구조 중 하나이다. 스택은 데이터를 일식적으로 저장하거나 관리하는데 사용되며, 데이 superohinsung.tistory.com JAVA Stack 클래스 java.util 패키지에서 Stack 클래스 제공 메서드 소개 push(item) : item을 Stack에 추가한다. pop() : Stack 에서 마지막에 넣은 아이템을 리턴하고, 해당 아이템은 Stack에서 삭제한..
안드로이드에서 이미지 로드 라이브러리란 Glide 외에 Coil, Picasso, Presco도 있지만 오늘은 Glide만 알아보자. Glide란? Glide란 Android에서 많이 사용하는 이미지 로드 라이브러리이다. 안드로이드 앱에서 이미지 로딩 및 디스플레이를 쉽게 처리 할 수 있게 도와주는 오픈 소스 라이브러리이다. 이미지 로딩은 안드로이드 앱 개발에서 자주 사용되는 작업 중 하나이며, 대량의 이미지를 효율적으로 로드하고 캐싱하여 앱 성능을 최적화하는 것이 중요한데, Glide는 이러한 작업들을 쉽게 처리할 수 있도록 도와준다. 공식페이지: https://bumptech.github.io/glide/ 공식깃허브: https://github.com/bumptech/glide Glide를 사용해보자..
그냥 밤에 잠이 안 올때마다 작성을 해보았다.20대를 돌아보며 회고록을 작성했다.누추하지만 귀한 분이 오셔서 이 글을 읽어줘서 감사합니다...사실 내가 좋아하는 블로거의 회고록을 보고 작성을 해보았다. https://todaycode.tistory.com/42 20살 ~ 21살(2015년 ~ 2016년) 고등학교 시절 여러가지의 이유가 겹쳐서 바로 대학을 진학하지 않고 일을 시작했다.인생에서 가장 외로웠고 힘든 시기였다...직장도 다녀보고, 배달도 해보고, 편의점 알바나, 마트에서 알바도 했다.물론 중간중간에 수능공부도 계속했다.인생의 암흑기 중 하나였다. 22살 (2017년)지금까지 모은 돈으로 재수학원에 들어가 공부를 했다.사실 인생에서 가장 노잼시기였던 것 같다....살이 10Kg 이상 찌기도하고 ..
