전체 글
-
BOJ) 작업 (2056 번)알고리즘/백준 2021. 3. 3. 00:45
작업 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 작업의 개수 N이 주어지고, 다음 N줄에 거쳐 각 작업의 수행 시간과 선행돼야하는 작업의 숫자가 주어진다. K작업에서 선행되는 작업은 1 ~ K-1 사이의 작업이 주어진다. 이 문제는 DP와 위상정렬로 분류되어있다. 그래서, 위상정렬로 접근하려고 했다. ArrayList에 각 선행되는 작업들을 넣어주고, 선행작업이 없는 작업들을 Queue에 넣어주어 순회했었다. 각 작업은 상관관계가 없으면 동시에 진행되니까, group을 넣어주고, depth를 함..
-
자바 참조 유형 (Strong, Soft, Weak, Phantom Reference)Java & Spring/자바 2021. 2. 28. 22:54
자바 참조 유형 강한 참조(Strong Reference) 일반적으로 new를 통해서 객체를 생성하게 되면 생기게 되는 참조. 강한 참조를 통해 참조되고 있는 객체는 가비지 컬렉션의 대상에서 제외된다. 소프트 참조(Soft Reference) java.lang.ref.SoftReference 객체를 참조하는 경우가 SoftReference 객체만 존재하면, GC의 대상이 됨 일반적으로는 메모리 여유에 따라 GC의 대상 여부가 결정 메모리 여유가 충분하면 GC가 수행되더라도 수거되지 않는다. JVM의 메모리가 부족하다면(Out Of Memory에 가깝다면) 힙 영역에서 제거된다. 약한 참조(Weak Reference) java.lang.ref.WeakReference GC가 발생하면 무조건 수거됨 GC의 ..
-
Checked Exception vs Unchecked ExceptionJava & Spring/자바 2021. 2. 28. 22:24
Exception과 Error An exception is represented by an instance of the class Throwable (a direct subclass of Object) or one of its subclasses. Throwable and all its subclasses are, collectively, the exception classes. (subclass of Throwable must not be generic) The classes Exception and Error are direct subclasses of Throwable. Exception is the superclass of all the exceptions from which ordinary pr..
-
BOJ) 빵집 (3109 번)알고리즘/백준 2021. 2. 23. 01:18
빵집 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다. 이 문제에서 필요한 제약 조건들이다. 그리고 가장 중요한 힌트는 문제의 사진 첨부에 나온다..
-
BOJ) 자두나무 (2240 번)알고리즘/백준 2021. 2. 23. 01:12
자두나무 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 처음 위치 1을 기준으로 자두나무에서 떨어지는 열매를 최대한 받을 수 있는 개수를 구하는 문제다. 자두나무는 1과 2 위치에만 있고, 1초마다 떨어지는 위치 정보가 주어진다. DP를 이용해서 이 문제를 풀었다. DP의 인덱스는 시간과 움직이는 횟수를 가진다.1초에 n번을 움직였을 때, 가장 큰 값을 저장해나간다.이동한 횟수가 짝수일 때와 홀수일 때를 나누어주었다.for문 하나에서 인덱스만 각각 구해서 돌릴 수 있겠지만, if문을 통해 w를 넘는지 확인해주어야 하..
-
BOJ) 수들의 합 2 (2003 번)알고리즘/백준 2021. 2. 18. 11:48
수들의 합 2 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net N개의 수열에서 i ~ j 번 째의 값들의 합이 M이 되는 경우를 구하는 문제다. N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000) 의 조건이 주어진다. 투포인터는 슬라이딩 윈도우와 유사하지만 다른 점은 바로 탐색 구간의 길이가 정해져있지 않다는 것이다. 투포인터를 활용해서 푸는 문제인데, 익숙하지 않아서 기록에 남겨둔다. 우선, 시작점 탐색을 도와줄 left와 끝점 탐색을 도와줄 ..
-
BOJ) 가르침 (1062 번)알고리즘/백준 2021. 2. 18. 11:40
가르침 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다. 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 구하는 문제다. 단어는 모두 소문자로 주어지고, 1
-
BOJ) 순열 사이클 (10451번)알고리즘/백준 2021. 2. 15. 14:58
순열 사이클 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 1 ~ N 으로 이루어진 순열을 방향 그래프로 나타냈을 때, 몇 개의 사이클이 존재하는지 구하는 문제다.각 Node에서 다음 Node의 vertex를 가지고 있고, 이 정보가 주어지기 때문에 배열을 활용했다.또한, find-union에서 착안하여 연결되는 지점을 DFS로 찾아가며 문제를 해결했다. 사이클을 형성하는지 확인하는 isCycle 메소드를 만들어 주었다.return 값은..