최장 증가 부분 수열(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에서 삭제한..
문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 어떻게 풀 것인가? 문제의 제목부터가 "최소비용 구하기" 이다. 그래서 다익스트라 최단경로 구하는 알고리즘을 사용하였다. 사실 그래서 처음 접근 자체는 크게 어렵지 않았다. 어떠한 문제를 풀 때 문제의 알고리즘 유형 파악이 빠르다면 코드는 그다지 어렵지 않다. 풀면서 놓쳤던점 X 이 문제를 통해 얻어갈 것 다익스트라 알고리즘 내 코드 import java.i..
안드로이드에서 이미지 로드 라이브러리란 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 이상 찌기도하고 ..
JVM이란운영체제는 자바 프로그램을 바로 실행할 수 없는데, 그 이유는 자바 프로그램은 완전한 기계어가 아닌, 중간 단계의 바이트 코드이기 때문이다. 이것을 해석하고 실행 할 수 있는 가상의 운영체제가 필요하다. 이것이 자바 가상 기계(JVM : Java Virtual Machine)이다. JVM은 실 운영체제를 대신해서 자바 프로그램을 실행하는 가상의 운영체제 역할을 한다. 자바 프로그램은 확장자가 .java인 파일을 작성하는 것부터 시작된다. 이것을 소스 파일이라고 하는데, 이 소스 파일을 컴파일러로(javac.exe)로 컴파일하면 확장자가 .class인 바이트 코드 파일이 생성된다. 바이트 코드 파일은 JVM 구동 명령어(java.exe)에 의해 JVM에서 해석되고 해당 운영체제에 맞게 기계어로 번..
