전체 글

[JAVA] Priority Queue

우선 순위 큐는 가장 높은 우선 순위 요소의 효율적인 검색을 지원하는 자료구조이다. 요소에는 대기열에서 액세스하거나 제거하는 순서를 결정하는 우선 순위가 할당된다. 우선순위 대기열은 FIFO(First-In-First-Out) 동작을 나타내어 우선순위가 가장 높은 요소가 항상 대기열의 맨 앞에 오도록 한다. Priority Queue의 특징 1. 높은 우선순위의 요소를 하나씩 꺼내서 처리하는 구조 2. 보통 바이너리 힙으로 Priority Queue를 구현하고, 이는 이진트리 구조로 이루어져 있다. 3. 삽입, 삭제에 대해 시간 복잡도가 O(NLogN)이다. Java Priority Queue 구현 import java.util.PriorityQueue; public class PriorityQueueE..

[코루틴] runBlocking

runBlocking은 코루틴을 만들고 코드 블록이 수행이 끝날 때까지 runBlocking 다음의 코드를 수행하지 못하게 막는다. 이 때 코루틴을 만드는 함수를 coroutine builder라고 한다. fun runBlockingFunc(){ runBlocking { println(coroutineContext)// 코루틴 스코프는 코루틴을 제대로 처리하기 위한 정보, coroutineContext를 가지고 있다. coroutineContext는 여러가지 정보를 가지고 있음. println(this) //runBlocking 안에서 this를 수행하면 코루틴이 수신 객체인 것을 알 수 있다. 즉 코드 블런 안에서 모든 코루틴 기능 사용 가능 println(Thread.currentThread().na..

브루트 포스

컴퓨터 과학 및 알고리즘 설계 영역에서 복잡한 문제에 대한 다양한 해결책이 있다. 여러가지 복잡하고 정교한 알고리즘이 있지만 더 직접적인 접근 방식을 취하는 알고리즘인 브루트 포스 알고리즘이 있다. Brute Force Algorithm Brute Force는 Brute(무식한)과 Force(힘)이 합쳐진 말로 힘으로 무식하게 해결하는 것을 말한다. 브루트 포스 알고리즘은 완전탐색 알고리즘이라고도 불리며, 모든 경우의 수를 다 확인하여 문제를 해결하는 알고리즘이다. 즉, 문제를 해결할 때까지 가능한 모든 입력 조합 또는 순열을 고려하여 간단하고 체계적인 접근 방식을 따른다. 단순성과 직관성이 특징으로 구현하기 쉽다. 장점 1. 단순성: 무차별 대입 알고리즘은 가능한 모든 솔루션을 체계적으로 반복하기 때문..

Room Migration

흔히 접하는 Room Error 프로젝트를 진행하다 보면 어쩔 수 없이 데이터베이스 스키마가 변경되고는 한다. 그렇게 Data class를 함께 변경하고 다시 앱을 실행하면 Looks like you've changed schema but forgot to update the version number. You can simply fix this by increasing the version number. 라는 오류를 접하게 된다. 이는 Room 데이터베이스의 스키마가 변경되었을 때 반드시 버전을 올려주어야 하기 때문에 오류가 발생한다. 그렇다면 버전을 어떻게 올릴까?? Room Version 올리기 @Database(entities = [LocationData::class], version = 1) a..

조합

조합 n개의 원소를 가진 임의의 집합에서 순서가 없이 r개를 선택하는 것 구현 아이디어 하나의 원소를 선택 vs 하나의 원소를 선택하지 않음 선택하는 경우 : n개의 원소 중에서 1개를 뽑는다고 생각 → r-1개를 뽑는다. 선택하지 않는 경우 : n개의 원소 중에서 1개를 뽑지 않는다고 생각 → r개를 뽑는다. 구현 조합의 경우의 수 구하기 public class Combination{ static int combination(int n, int r){ if(n==r || r==0) return 1; return combination(n-1, r-1) + combination(n-1, r); } } 조합으로 나온 원소 구하기 static void combination(int[] list, boolean[..

[백준/JAVA] 11659번 구간 합 구하기 4

누적 합 테크닉으로 구간 합을 빠르게 구하는 문제 https://www.acmicpc.net/problem/11659 1. 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 2. 문제 접근 1) 첫째 줄에 수의 개수 N과 합을 구하는 횟수 M을 입력받는다. 2) 둘째 줄에서 N개의 수를 입력받을 때 배열에 누적합을 저장한다. 3) 셋째 줄부터 M번 만큼 시작 인덱스와 종료 인덱스를 입력받고 누적합 배열에서 종료 인덱스 값에서 시작 인데스-1 값을 빼줌으로 구간의 합을 구한다. 3. 코드 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; impor..

[백준/JAVA] 14852번 타일 채우기 3

https://www.acmicpc.net/problem/14852 1. 문제 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자. 2. 문제 접근 1) 첫째 줄에 길이 N을 입력받는다. 2) 타일 채우기의 규칙을 파악한다. 2-1) N이 1일 때 경우의 수는 2, N이 2일 때 경우의 수는 7이다. 2-2) N이 3이상일 때 N-1 크기에서 채우는 경우의 수는 2가지이다. 2-3) N-2 크기에서는 채우는 경우의 수는 3가지이다. 2-4) N-(3이상) 크기에서는 채우는 경우의 수는 2가지이다. 3) 재귀적으로 표현시 시간초과가 발생하기 때문에 모든 타일 채우는 경우의 수 배열의 2배를 더한 값을 저장하고 N번 째 경우의 수는 2배를 더한 값 + N-2의 경우의 수로..

[백준/JAVA] 2133번 타일 채우기

https://www.acmicpc.net/problem/2133 1. 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 2. 힌트 3. 문제 접근 1) 첫째 줄에 N의 크기를 입력받는다. 2) 경우의 수를 고려한 후 다이나믹 프로그래밍에 대한 점화식을 세운다. 2-1) 홀수인 경우 칸의 총 수가 홀수이기 때문에 2X1 혹은 1X2 크기의 타일로 채우지 못하기 때문에 0을 반환한다. 2-2) 짝수인 경우 크기가 2 작은 타일에서 채우는 경우의 수가 3가지이기 때문에 N-2를 매개변수로 하는 재귀함수에 3을 곱하는 경우를 가진다. 2-3) 짝수인 경우 중에 크기가 2보다 큰 짝수(4,6,8)만큼 작은 타일에서 채우는 경우의 수가 2가지이기 때문에 N-(2보다 큰 짝수)를..