xxheexx

BFS (Breadth First Search) 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 그래프에서 모든 노드를 방문하기 위한 알고리즘 예시 - (0,0)과 상하좌우로 이어진 모든 파란색 칸 BFS로 확인 (0,0) 방문했다는 표시 남기고 해당 칸 큐에 삽입 초기 세팅 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌효의 상하좌우를 살펴보면서 큐에 넣어주는 작업 반복 큐의 front는 (0,0)이고 pop (0,0)의 상하좌우 칸 확인 -> 파란색 칸이면서 아직 방문하지 않은 칸 큐 삽입 ...큐가 빌때까지 반복 큐가 비었을 때 확인해보면 (0,0)과 연결된 파란색 칸 모두 방문 완료 시간복잡도 : 모든 칸이 큐에 1번씩 들어가므로 칸이 N개일 때 O(N) 좌..

bfs로 count를 구하는 문제 bfs: queue를 이용하여 count 구하기 쉬움 dfs: 재귀 함수로 구현되기에 count 구하기 쉽지 않음 예시 : 수빈이 N - 5, 동생 K - 17 0초 1초 2초 3초 4초에 17 도달 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.pa..

자바를 오랜만에 써서 기본 자료구조를 선언하는 방법이 헷갈리는 본인을 위한 정리 map Map map = new HashMap(); SortedMap sortedMap = new TreeMap(); queue Queue q = new LinkedList(); Queue 변수명 = new LinkedList(); //다른 자료형 넣기 가능 // 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자) PriorityQueue pQ = new PriorityQueue(); // 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자) PriorityQueue pQ = new PriorityQueue(Collections.reverseOrder()); stack Stack stackInt = new Stack(); de..

Greedy = 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘 이상적인 풀이 흐름 1. 관찰을 통해 탐색 범위를 줄이는 방법 고안 2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명 3. 구현해서 문제 통과 관련 문제 풀이 https://ssohee-coding.tistory.com/36

그리디 알고리즘 종료 시간을 기준으로 정렬 -> 이전 종료시간에 대해 겹치는 것들은 제외하고 남은 것들 중 선택 빨리 끝나는 것 선택 : a1 a1을 선택한 뒤 다음으로 빨리 끝나는 것 a2 (a1과 겹치므로 제외), a3도 마찬가지 a4는 a1과 겹치지 않으면서 다음으로 빨리 끝남 -> 총 4개 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine())..

다이나믹 프로그래밍 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정하기 예제 - 백준 2 X n 타일링 (11726) #include using namespace std; int d[10005]; int mod = 10007; int main(void){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; d[1] = 1; d[2] = 2; for(int i = 3; i

상한 : 찾고자 하는 특정 값을 초과하는 '첫 위치' 반환 하한 : 찾고자 하는 특정 값 이상인 '첫 위치' 반환 -> 중복 값이 있을 때의 활용 arr1{1, 2, 2, 2, 3} 일 때 Key 값이 2이고, Upper Bound로 찾는다면 2를 초과되는 처음 위치인 arr[4] = 3인 index 4 반환 Lower Bound로 찾게 된다면 2 이상 위치 중 처음 위치인 arr[1] = 2인 index 1 반환 중복 원소에서 가장 끝 값(가장 오른쪽 값)을 찾고자 한다면 Upper Bound - 1 중복 원소 중 가장 왼쪽 끝 값(가장 왼쪽 값)을 찾고자 한다면 Lower Bound 그대로 private static int lowerBound(int[] arr, int key) { int lo = 0..

풀이 (참고) 길이에서 최대값(max)은 주어진 랜선의 길이중 최대값+1로 설정하고 최소값(min)은 0으로 시작한다. mid = (min+max)/2로 설정한 후 주어진 랜선의 길이에서 얻어낼 수 있는 랜선의 수 n을 구한다. n과 N을 비교해 n

영속성 컨텍스트 엔티티를 관리하는 논리적인 개념 어플리케이션과 DB 사이에서 객체를 보관하는 가상의 DB 같은 역할 엔티티를 메모리에 저장, 엔티티의 생명주기 관리, 엔티티와 DB 간의 작업 캐시해서 처리 준영속 엔티티 영속성 컨텍스트가 더는 관리하지 않는 엔티티 (DB에 한 번 갔다와서 식별자 존재) 수정하는 방법 - 변경 감지 기능, 병합(merge) 사용 변경 감지 기능 사용 @Transactional void update(Item itemParam) { //itemParam: 파리미터로 넘어온 준영속 상태의 엔티티 Item findItem = em.find(Item.class, itemParam.getId()); //같은 엔티티를 조회한다. findItem.setPrice(itemParam.get..

완전탐색으로 구현 import java.util.*; import java.io.*; public class Main { static int N; static Vector v; static Stack st; static void print(){ if(st.size()==N) { for(int num:st){ System.out.print(num+" "); } System.out.println(); return; } for(int i=1;i