문제풀다가 모든 점에 대한 최단경로를 구해야하는 문제를 풀다가 플로이드 와샬을 떠올랐지만 알고리즘을 까먹엇다. (대충 3중 for문 이라는 것 정도..) 특징 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘. 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘. 3중 for 문 (제일 밖) 첫 번째 for 문: 거쳐가는 노드 두 번째 for 문 : 출발 노드 세 번째 for 문 : 도착 노드 검증 출발→거쳐 + 거쳐→도착 가 출발→도착 보다 더 짧으면? 출발→도착 갱신. Code for(int k = 0; k < number ; k++) { for(int i = 0; i < number ; i++) { for(int j ..
배경 & 문제점 바우처 관리 프로그램을 JAVA Spring 프레임워크로 구현하다가 Test Code 작성 중에 난관에 부딪혔다. VoucherService 테스트 코드를 작성하는데 Mockito 라이브러리를 이용해서 행위에 대한 테스트를 구현한다. class VoucherServiceTest { @Test @DisplayName("voucher가 생성되어야 한다.") void testCreateVoucher() { // ... } } Voucher Class를 만드는 VoucherFactory 클래스의 method인 createVoucher() 가 정해진 인스턴스(fixedAmountVoucher)를 반환하도록 mocking하려고 한다. // VocherFactory.class public class ..
변별력 있는 탐색 문제에서 이진 탐색이 자주 출몰한다. 이진 탐색이란 우선! 정렬된 리스트에서 사용 가능하다. 탐색 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색 한다. 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)으로 형성된다. 이를 개선하기 위해 우선 순위 큐의 힙 구조를 활용하여 시간..
TIL 오늘 한 일 [✅] W3D1 강의 [ ] Slack #team-마르코 채널에서 올려줬던 Tip들 확인 [ ] SQL LevelUP 2강 정리 [ ] 자바 객체 지향의 원리와 이해 읽고 정리 느낀점 W3D1강의 스프링 부트가 어떻게 탄생하게 되었는지 유례를 알 수 있었고, 역시나 결합도, 의존성 등 OOP에서 나오는 개념들이 등장한다. 오전에 강의를 듣고 바로 책을 읽어야겠다. 집에서보단 카페에서해야쥐 내일 할 일 [ ] W3D2 [ ] SQL Level Up 발표 [ ] Slack #team-마르코 채널에서 올려줬던 Tip들 확인 [ ] SQL LevelUP 2강 정리 [ ] 자바 객체 지향의 원리와 이해 읽고 정리
