꼬비.com

그리디 문제를 풀고있는데 또다시 어려움을 직면했고 오답노트겸 따로 정리를 했다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의..

그리디 문제를 풀고있는데 처음으로 어려움을 직면했고 다른 사람들의 풀이를 읽어도 명확하게 이해가 되지 않아서 따로 정리를 했다. 앞으로 문제를 풀고나서 리마인드도 할겸 어려워하는 사람에게 도움도 될겸 겸사겸사 블로그에 정리해볼까 싶다. https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, ..

알고리즘 공부를 어떻게 시작해야할까? https://steady-coding.tistory.com/260 알고리즘 공부를 어떻게 시작해야할까? (Feat. 백준 500문제 푼 기념으로 적는 PS 회고록) 안녕하세요? 코딩중독입니다. 어제 "백준 6219번 소수의 자격" 문제를 풀었고, 이것이 저의 500번째 푼 문제가 되었습니다. 물론, 아직 세자리수 등수에 들지 못하였고, 다른 분들이 보기에 많은 문 steady-coding.tistory.com 알고리즘 문제 풀이하기 https://plzrun.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4PS-%EC%8B%9C%EC%9E%91%ED%9..

Brute + Force = 무식한 + 힘 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과 만을 가져오는 알고리즘. 완전 탐색 알고리즘이라고도 불린다. 문제 해결 방법 1. 주어진 무제를 선형 구조로 구조화한다. 2. 구조화된 문제 공간을 적절한 방법으로 해를 구성할 때까지 탐색한다. 3. 구성된 해를 정리한다.

최근에 2022.10.30 - [알고리즘/문제풀이] - 백준 문제풀이할 목록 에 있는 문제를 풀고 있는데 중요도가 높다고 생각되는 dp 문제를 풀면서 만났던 유형들을 정리해보았다. (아직 많은 문제를 풀어본 것이 아니라서 모든 dp 문제 풀이 유형을 정리한건 아니다.) 1. 단순한 점화식 사용 dp[i] = dp[i - 1] + dp[i - 2]; dp[i] = dp[i - 1] + n * dp[i - 2]; [1로 만들기](https://www.acmicpc.net/problem/1463) [2×n 타일링](https://www.acmicpc.net/problem/11726) [2×n 타일링 2](https://www.acmicpc.net/problem/11727) [1, 2, 3 더하기](https:..

1. 개요 동적 계획법 ( Dynamic Programming, 줄여서 DP ) 은 프로그래밍 대회에서 출제되지 않으면 이상할 정도로 높은 출제빈도를 보이고 있을 만큼 중요한 알고리즘 설계 기법입니다. 동적 계획법은 주어진 문제를 여러 개의 하위문제들로 나누어 먼저 처리한 후 그 답들을 이용해 문제를 처리하는 방법을 뜻합니다. 하위문제들을 수행할 시에는 같은 문제를 여러 번 처리하는 경우가 발생하는데 이 때, 한번 수행한 문제들의 답을 저장해 놓으면 그 다음부터는 답을 바로 알아낼 수 있어 속도가 비약적으로 빨라지게 할 수 있습니다. 2. DP 기본 예제 – 피보나치 수열 피보나치 수열은 F[0] = 0, F[1] = 1, F[i] = F[i-1] + F[i-2] ( i > 1 ) 을 만족하는 수열인데 ..

Dynamic Programming 이란? 복잡한 문제를 더 간단한 하위 문제의 모음으로 쪼개서 각 하위 문제들을 풀어서 그 답을 저장하는 방식으로 문제를 푸는 것 대부분의 문제에 적용할 수 있는 것은 아니지만 사용할 수 있는 경우에는 코드의 속도를 많이 향상시켜준다. => 최적의 해답을 찾아내는 것 Dynamic Programming 을 사용하기 위한 전제 조건 1. 최적 부분 구조가 존재하는가 2. 반복되는 하위 문제가 있는가 반복되는 하위 문제란? 한 문제를 더 작은 문제들로 나눌 수 있고, 그 조각들 중 일부가 재활용 가능하다는 말. ex) Fibonacci Sequence // Big O : O(2^n) function fib(n) { if (n B -> C -> D 가 아닐 수 있다는 것. D..

알고리즘 기초 1/2 200 - 자료구조 1 스택 단어 뒤집기 괄호 스택 수열 에디터 큐 조세퍼스 문제 덱 201 - 자료구조 1 (연습) 단어 뒤집기 2 쇠막대기 오큰수 오등큰수 203 - 자료구조 1 (참고) 후위 표기식2 후위 표기식 알파벳 개수 알파벳 찾기 문자열 분석 단어 길이 재기 ROT13 네 수 접미사 배열 300 - 수학 1 나머지 최대공약수와 최소공배수 최소공배수 소수 찾기 소수 구하기 골드바흐의 추측 팩토리얼 팩토리얼 0의 개수 조합 0의 개수 301 - 수학 1 (연습) GCD 합 숨바꼭질 6 2진수 8진수 8진수 2진수 -2진수 골드바흐 파티션 303 - 수학 1 (참고) 진법 변환 2 진법 변환 Base Conversion 소인수분해 400 - 다이나믹 프로그래밍 1 1로 만들기..

BFS /** * 2 ways of traversing a tree. * - Breadth First Search (BFS) * - Depth First Search (DFS) * * BFS (Steps - Iteratively) * - Create a queue(this can be an array) and a variable to store the values of nodes visited. * - Place the root node in the queue. * - Loop as long as there is anything in the queue. * > Dequeue a node from the queue and push the value of the node into the variable th..

/** * Kind of Tree * * - Trees * - Binary Trees * - Binary Search Trees * - ... * */ /** * Binary Serach Trees (BSTS) * * - Every parent node has at most 2 child. * - Every node to the left of a parent node is always less than the parent. * - Every node to the right of a parent node is always greater than the parent. * */ class Node { constructor(value) { this.value = value; this.left = null; th..