안 쓰던 블로그

1202 보석 도둑 처음엔 보석 값대로 sort하고 가방 sort해서 무게 들어가는 거 넣는 방법으로 했는데 당연히 시간초과 github.com/proqk/Algorithm/blob/master/greedy/1202%20%EB%B3%B4%EC%84%9D%20%EB%8F%84%EB%91%91_%EC%8B%9C%EA%B0%84%EC%B4%88%EA%B3%BC.cpp 여기서 두 sort를 한 이유는, 가격이 높은 보석부터 차례대로 가방 허용 무게에 가장 가까운 보석을 찾기 위해서이다 다르게 말하면 가방 무게 x보다 큰 보석 중에 가장 작은 수를 찾는다 = Lower Bound 그리고 찾은 값을 삭제한다 이진 탐색 트리BST를 사용하면 이 탐색 및 삭제 연산을 O(NlogK)에 할 수 있다 BST로 구현된 C+..

5639 이진 검색 트리 평소에 트리를 읽는 순서인 전위순회대로 주어지는 입력값으로 이진 트리를 만들고, 후회순회를 돌리면 된다 첫 값인 root를 기준(now)으로 잡고 왼쪽 오른쪽 값을 비교한다 만약 노드가 없으면 주어진 값으로 새로운 노드를 만들고, 아니면 그 노드를 now로 두고 다시 탐색 돌아간다 이진 탐색 트리 구현은 전에 썼던 글이 있다 AVL트리 foxtrotin.tistory.com/191 이진 탐색 트리 foxtrotin.tistory.com/190 그리고 입력의 끝이 주어지지 않을 때 c++에서는 while(cin>>num){} 이렇게 하면 된다 while문으로만 EOF처리가 되기 때문에 저렇게 썼는데도 런타임 에러가 난다면 배열 크기나 벡터 초기화나 다른 곳을 살펴본다 github...

신년맞이 작심20일 boj 챌린지 -하루에 정해진 분량만큼 문제 풀이(계획서 참고) -각 문제별 간단 해결 방법+깃헙 링크 블로그 정리 1967 트리의 지름 day1에서 했던 트리의 지름 문제처럼 정점 1에서 가장 멀리 있는 정점을 dfs로 구한뒤, 그 정점에서부터 다시 가장 먼 노드를 찾으면 트리의 지름이 된다 github.com/proqk/Algorithm/blob/master/Tree/1967%20%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EC%A7%80%EB%A6%84(2).cpp 2805 나무 자르기 나무를 세워두고 케이크 자르듯이 칼로 쓰윽 자른다고 생각한다 자른 짜투리의 길이를 전부 더해서 너무 많이 잘랐으면 덜 자르고, 너무 적게 잘랐으면 더 자르는 식으로 조절한다 1. 나무를..

신년맞이 작심20일 boj 챌린지 -하루에 정해진 분량만큼 문제 풀이(계획서 참고) -각 문제별 간단 해결 방법+깃헙 링크 블로그 정리 1991 트리 순회 전: 루트->왼->오 중: 왼->루트->오 후: 왼->오->루트 전: 출력->왼 탐색->오 탐색 중: 왼 탐색->출력->오 탐색 후: 왼 탐색->오 탐색->출력 탐색은 어차피 같으므로 출력만 나누면 한 번에 한 함수에 때려넣을 수 있다 github.com/proqk/Algorithm/blob/master/Tree/1991%20%ED%8A%B8%EB%A6%AC%EC%88%9C%ED%9A%8C(3).cpp 2250 트리의 높이와 너비 1. 트리 만들기 2. 중위순회 돌면서 몇 번 노드가 몇 번째 레벨에 있는지 저장 3. 2번을 하면서 레벨마다 최소, 최대..

www.acmicpc.net/problem/6603 n개 중에 6개를 뽑는 모든 경우의 수 구하기 몇개를 뽑는지 정해져 있다면 순열을 이용할 수 있다 뽑는 6개에 대해 1이라고 하고, n-6에 대해 0이라고 한 순열을 만들고 모든 순열을 돌면서 1인 경우의 값을 출력한다 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; while (1) { cin >> n; vector a(n), d; if (n == 0) break; for (int i = 0; i > a[i]; for (int i = 0; i < n - 6; i++) d.pu..

순열 next_permutation()과 prev_permutation() 직접 구현하기 다음 순열, 이전 순열, 모든 순열 순열 크기 n이 3인 수열을 사전순으로 나열하면 다음과 같다 123 132 213 231 312 321 n=3인 수열은 총 6개가 있다 여기서 먼저 알 수 있는 사실은 크기가 n인 순열을 총 n!개 존재한다는 것이다 첫 번째 오는 수를 n가지 중에서 선택, 그 다음 수를 n-1가지 중에서 선택, 그 다다음 수를 n-2가지 중에서 선택..을 반복하기 때문에 총 가지 수는 n*(n-1)*(n-2)*...*2*1 즉, n!이다 또 알 수 있는 사실은 첫 순열은 오름차순, 마지막 순열은 내림차순이라는 것이다 그러므로 중간 순열을 구하고 싶다면 첫 순열에서 다음, 다음, 다음으로 넘어가서 ..

합이 n이고 길이가 최소 l인 연속된 수열을 구하는 문제 합이 n인 연속된 수열을 $x+(x+1)+(x+2)...(x+L-1)$ 로 두고 x에 대한 식으로 바꾸면 위에 풀이처럼 된다 l이 100까지라고 했으니까 l~100 사이에서 조건에 맞는 x를 찾으면 끝 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long n; int l, res = -1, index = 0; cin >> n >> l; for (int i = l; i = 0) { //나눠 떨어지고, 길이가 맞으면 찾음 res = (n - k) / i; index = i; break; } } if (re..