변별력 있는 탐색 문제에서 이진 탐색이 자주 출몰한다. 이진 탐색이란 우선! 정렬된 리스트에서 사용 가능하다. 탐색 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색 한다. 3가지 변수가 사용됨 : 시작점, 끝점, 중간점 직접 구현 public class Solution { public int binarySearch(int[] arr, int target) { int first = 0; // 시작점 int last = arr.length - 1; // 끝점 int mid; // 중간점 while (first
Transaction Isolation Level Transaction이란 데이터베이스에서 하나의 논리적 작업 단위를 구성하는 일련의 연산들의 집합을 트랜잭션이라고 한다. 트랜잭션은 A.C.I.D 성질이라고 하는 다음의 네 가지 성질로 설명된다. Atomicity 트랜잭션의 모든 연산들이 정상적으로 수행 완료되거나 아니면 전혀 어떠한 연산도 수행되지 않은 상태를 보장 (0 or 1) Consistency 고립된 트랜잭션의 수행이 데이터베이스의 일관성을 보존 랜잭션 수행 전후의 데이터베이스 상태는 각각 일관성이 보장되는 서로 다른 상태 Isolation 여러 트랜잭션이 동시에 수행되더라도 각각의 트랜잭션은 다른 트랜잭션의 수행에 영향을 받지 않고 독립적으로 수행되어야 한다. Durability 트랜잭션이 ..
Heap 우선 순위 큐를 하다가 Heap 구조를 사용한다는 것을 보았는데 Heap 자료구조란 무엇일까? 힙은 일종의 BinaryTree 이며 수의 집합에서 가장 작은 수나 가장 큰 수만을 자주 꺼내올 때 유용한 자료구조 가장 큰 / 작은 수 가져올때 시간 복잡도 : O(log N) 예: 최소 힙 구현 규칙이 있다. 루트는 가장 작은 값이여야 함. 자식은 자신보다 크기만 하면됨. 완전 이진 트리의 규칙을 그대로 적용 힙을 배열 형태로 구현 왼쪽 자식은 (자신의 인덱스 * 2) 오른쪽 자식은 (자신의 인덱스 * 2 + 1) 자신의 부모는 (자신의 인덱스 / 2) Heap 정의 public class Heap { public static final int MAX_N = 10001; public int[] ar..
높은 수준의 모듈? 낮은 수준의 모듈? 이해가 안되어서 TIL에 정리하고자 한다. Dependency Inversion Principle (의존관계 역전) 높은 수준의 모듈은 낮은 수준의 모듈에 의존하지 않아야 한다. 두 모듈 모두 추상화에 의존해야 한다. 추상화는 세부 사항에 의존하지 않아야 한다. 세부 사항은 추상화에 의존해야 한다. 예시 만일 우리가 MySQL 데이터베이스 사용하는 자바 어플리케이션을 만든다고 해보자. 그래서 (높은 수준) Java Application에서 (낮은 수준)MySQL ODBC Driver class를 이용해 작업하고 있다. // Java Application public class Main { public static void main(String[] args) { My..
가끔씩 삼성 A형 문제라던가 구현, 시뮬레이션 문제들 보면 배열을 자주 돌린다. (회전 회오리) 그래서 이번 기회에 기강을 다져보기로 했다. (그저 기록이지만) 코딩테스트 치기전에 한 번 보면 좋겠다 미래의 나 class Map { int[][] map; public Map(int[][] map) { this.map = map; } public void rotate() { // 90도 회전 int rows = map.length; int cols = map[0].length; int[][] newMap = new int[cols][rows]; for(int i = 0 ; i < rows ; i++) { for(int j = 0 ; j < cols ; j++) { newMap[j][rows - i - 1]..
프로그래머스 [가장 먼 노드] 문제를 풀면서 dfs로 해도 되겠지만, 많이 못 써봤던 다익스트라 알고리즘을 사용하면 어떨까 해서 사용해봤는데, 다익스트라 알고리즘에서도 힙 구조를 사용하면 더 효율적으로 사용할 수 있다는 내용이 있어서 한 번 써보았는데 괜찮아져서 TIL에 기록하고 싶다. 다익스트라 알고리즘? 다익스트라 알고리즘은 DP (그 D.P가 아니다) 을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 왜 다이나믹 프로그래밍의 종류이냐? 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징때문이다. 대부분 이차원 배열을 사용하여 선형 탐색을 하는데, 이렇게 작성하면 시간 복잡도가 O(N^2)으로 형성된다. 이를 개선하기 위해 우선 순위 큐의 힙 구조를 활용하여 시간..
Object 클래스란 Object 클래스는 모든 자바 클래스의 최고 조상 클래스가 됩니다. 그래서 자바에서 모든 클래스는 사실 Object를 암시적으로 상속받고 습니다. 그 이유는 모든 클래스가 공통으로 포함하고 있어야 하는 기능을 제공해야하기 때문입니다. 참고) java.lang 패키지 java.lang 패키지는 자바에서 가장 기본적인 동작을 수행하는 클래스들의 집합입니다. 따라서 자바에서는 java.lang 패키지의 클래스들은 import 문을 사용하지 않아도 클래스 이름만으로 바로 사용할 수 있도록 하고 있습니다. java.lang 패키지 중에서도 가장 많이 사용되는 클래스는 바로 Object 클래스입니다. Object 클래스는 모든 자바 클래스의 최고 조상 클래스가 됩니다. 따라서 자바의 모든 클..
Java에서 문자열을 다룰 수 있는 방법은 두 가지가 있습니다. 첫 번째로 문자열 상수에 대해 불변성(immutable)을 가진 String 클래스가 있고, 두 번째로 같은 메모리로 문자열을 다루는 StringBuffer, StringBuilder 클래스가 있습니다. String String 객체는 한번 생성되면 할당된 메모리 공간이 변하지 않습니다. 그래서 String 객체 문자열에 다른 문자열을 붙여도 기존 문자열에 붙이는 것 이 아니라, 새로운 String 객체를 만든 후 새 String 객체에 연결된 문자열을 저장하고 그 객체를 참조합니다. 때문에 String을 조작하는 연산은 시간과 자원을 많이 사용합니다. StringBuffer & StringBuilder 이 둘은 문자열을 한 번 만들고 연산..
