개발 노트

백준 2912번 백설공주와 난쟁이https://www.acmicpc.net/problem/2912 세그먼트 트리, 이진탐색 알고리즘 문제 세그먼트 트리 모아보기: https://noteofdeveloper.tistory.com/tag/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8%ED%8A%B8%EB%A6%AC 이진탐색 모아보기: https://noteofdeveloper.tistory.com/tag/%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89 너무 어려워서 잡히는 줄 알았다....ㅠㅠㅠ 인덱스를 이용해 자식노드에 접근할 일이 없으므로 세그먼트로 풀기에 좋은 문제 세그먼트 트리는 루트부터 값이 들어가게 되므로 이런 형태로 그려진다. (색상명,난쟁이수)쌍으로 구성 ..

백준 2357번 최솟값과 최댓값 https://www.acmicpc.net/problem/2357 계속 구간을 찾아야하므로 세그먼트 트리로 풀어낼 수 있다. 세그먼트 트리 자료 https://noteofdeveloper.tistory.com/63 최댓값, 최소값쌍 트리.

백준 2042번 구간합구하기 https://www.acmicpc.net/problem/2042 계속 구간을 찾아야하므로 세그먼트 트리로 풀어낼 수 있다. 세그먼트 트리 자료 https://noteofdeveloper.tistory.com/63

백준 10868번 최솟값 https://www.acmicpc.net/problem/10868 계속 구간 최소를 찾아야하므로 세그먼트 트리로 풀어낼 수 있다. 세그먼트 트리 자료 https://noteofdeveloper.tistory.com/63

BOJ 7576번 토마토 https://www.acmicpc.net/problem/7576 BFS를 할 때 상하좌우를 직접 지정해줘도 되지만 방향 순서쌍 dx,dy를 이용해도 됨 BFS와 DFS의 차이는 que 자료형, dist 저장 위치가 가장 큰 차이인 듯.

테스트케이스 포함 BOJ 12015 가장 긴 증가하는 부분 수열2 https://www.acmicpc.net/problem/12015 이 문제는 Lower Bound 개념을 알고 있어야만 풀 수 있는 문제. Lower Bound 개념의 응용버전으로 0번째 자리에 비교 기준값인 0을 갖는다. 어려워서 많이 헤맸던지라 내가 만들거나 백준에서 수집한 테스트 케이스도 있다. (확장자가 없는 파일이라 raw로 봐야함. 이클립스로 열면 한글까지 확인 가능. 테스트 케이스 바로가기) 여러 풀이를 참고했는데 가장 도움이 될만한 글만 모아봤다. 이분탐색을 이용해야하는 이유: 작은 수부터 정렬하는 게 경우의 수를 높일 수 있다. https://guccin.tistory.com/81 Lower Bound 개념 https:/..

BOJ 11053번 가장 긴 증가하는 부분 수열 Java 가장 긴 증가하는 부분 수열의 개념을 먼저 알아야한다. (자세한설명 나무위키) 수열의 정렬을 건드리지 않고, 가장 적은 숫자를 제거해서 오름차순인 수열을 만들어내는 것이다. 백준은 테스트케이스가 다양한 상황을 고려하지 못해서 개인적으로 만들어봤다. 테스트케이스: {1 2 1 3 2 6 4 5} 🎈 1 2 1 3 2 6 4 5 🎈 1 2 1 3 2 6 4 5 이 두가지 경우 중 가장 긴 것을 선택해야한다. 🎈 1 2 3 6 🎈 1 2 3 4 5 이 둘은 각각 { 1 2 3 } + 6 과 { 1 2 3 } + 4 5 한 것중 긴 것을 택한 것. For 1 ~ N For 1~N-1 의 이중포문으로 시간복잡도는 O(NlogN) 이라고 한다.

BOJ 10775번 공항 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 문제를 이해하는데 오래걸렸다.... ⭐⭐당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 1~Gi번째까지 모두 가능하단 얘기다 gi = 2 일 경우 1,2번 게이트 모두 가능 gi = 3 일 경우 1,2,3번 게이트 모두 가능 작은 수는 공통이므로 큰 수부터 차례대로 게이트 사용한..

BOJ 11437번 LCA https://www.acmicpc.net/problem/11437 풀이: 다른 사람들이 왜 이렇게 풀어야만 했는지 이해를 못해서.... 한참 헤맸다 문제에 주어지지 않는 게 있는데 *부모-자식 관계의 정의*가 주어지지 않는다. 1. 주어진 정점들을 다 연결했을 때 1과 가까운 노드가 부모가 된다. 최상위가 1번이라서 작은수가 부모가 된다고 착각하면 방황하게 된다ㅠㅠ 정점을 하나씩 탐색 돌리면 시간 초과가 뜨고, 문제는 항상 한 쌍으로 주어지기 때문에 2. 반복문(for/while) 하나에서 두 정점을 동시에 탐색해야 한다. 두 정점을 동시에 탐색하려면 각 정점의 단계(Level)을 알아야한다. 정점별로 탐색을 돌리면 시간초과가 뜨기 때문에 3. 각 정점별 단계를 미리 단계를 ..

BOJ 1854 K번째 최단경로 풀이: 1. 도로가 단방향. 2. 시작점은 경로비용 0 (문제에서 제시) 3. 시작점은 1번도시로 고정 이 전제하에 각 도시에 대해 모든 최단경로를 가장 작은 순으로 정렬했을 때 문제에서 주어지는 K번째 경로비용을 구하면 된다. 다만 모든 최단 경로를 구할 경우 메모리 초과가 발생한다. 따라서 모든 경로를 탐색하면서 각 K번째 최단경로까지만 보관한다. 각 경로의 최단경로를 보관하기 위해 입력받는 순간 정렬되는 Priorityque를 배열로 사용한다. (PriorityQueue[] costList = new PriorityQueue[N]; //도시 개수만큼 생성) que에 들어가는 순간 정렬되는 효과를 이용한다. 적은 비용은 두고 큰 비용은 그거보다 작은 비용을 만날 경우 ..