전체 글 (6) 썸네일형 리스트형 BOJ 1689 겹치는 선분 https://www.acmicpc.net/problem/1689 1689번: 겹치는 선분 첫째 줄에는 선분의 개수(1 ≤ N ≤ 1,000,000)가 입력으로 들어온다. 그 다음 N개의 줄에 선분의 시작 좌표 s와 끝나는 좌표 e (s < e)가 입력으로 들어온다. 선분의 좌표는 절댓값이 10억보다 작거나 www.acmicpc.net https://driip.me/65d9b58c-bf02-44bf-8fba-54d394ed21e0 누적합의 확장, imos법 imos법에 대해 알아보자. driip.me imos법이라고 불리는 트릭을 이용하는 문제입니다. 메모리 초과를 안 받는 선에서 imos법을 위한 출/입 배열을 잡을 수 있는 문제는 간단히 해결가능 합니다. 그런데 이런 문제처럼 좌표의 범위가 10억에 .. BOJ 2533 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 트리 DP 문제입니다. 트리의 어떤 노드 $N$에 대해, $dp[N][0] = N$을 루트로 하는 트리에서, $N$이 얼리어답터가 아닐 때 이 트리의 모든 사람에게 아이디어가 전파되기 위한 최소 얼리어답터의 수. $dp[N][1] = N$을 루트로 하는 트리에서, $N$이 얼리어답터 일 때 이 트리의 모든 사람에게 아이디어가 전파되기 위한 최소 얼리어답터의 수. .. BOJ 19700 수업 https://www.acmicpc.net/problem/19700 19700번: 수업 키가 188cm, 154cm인 학생들을 한 팀으로, 키가 180cm, 161cm인 학생들을 한 팀으로, 키가 172cm인 학생을 혼자 팀으로 묶으면 총 3개의 팀을 구성할 수 있다. 더 적은 갯수의 팀으로 학생들을 묶을 수 있 www.acmicpc.net 이진검색트리(multiset)을 이용해서 푼 문제입니다. 이진검색트리에 삽입되는 원소는 각 팀의 인원 수 입니다. 즉, 현재 각 팀에 있는 사람의 구체적인 키를 저장하지 않아도 문제를 해결할 수 있습니다. 그 이유는, 키가 가장 큰 사람부터 팀 배정을 하면 되기 때문입니다. 그렇게 한다면, 현재 키가 K번째로 큰 사람의 팀을 배정해야 한다고 할 때, 현재 존재하는 모.. BOJ 1202 보석 도둑 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 웰노운이라 예전부터 풀고 싶은 문제였는데, knapsack DP로 접근하다가 잘 안돼서 놔두었던 문제입니다. 결국 바킹독님의 이진검색트리 알고리즘 강의를 듣고 해결하였습니다. 지금까지 C++에서 set 자료구조를 쓰면서 lower/upper_bound 함수를 쓸 수 있는 지 몰랐는데, 이 기능이 된다는 것을 배우고 난 뒤에 이를 많은 문.. BOJ 12865 평범한 배낭과 냅색 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 냅색(배낭 문제)라는 개념을 모르면 문제를 해결하기 어려운 경우가 많습니다. 냅색은 꽤나 유명한 다이나믹 프로그래밍의 응용입니다. 문제의 예제 입력1로 dp테이블을 만들면 아래와 같습니다. 테이블의 각 열에 적힌 숫자는 준서가 버틸 수 있는 배낭 무게의 한계입니다. 또한 행에는 각 물품이 적혀 있습니다. 여기서 중요한 점이 있습니다.. BOJ 9466 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 그래프에서 사이클이나 루프를 이루지 않는 노드의 개수를 세면 되는 문제입니다. 문제를 읽고 이걸 파악하는 것은 어렵지 않지만, 시간초과가 뜨지 않게끔 구현하는 것은 꽤 까다롭다고 할 수 있습니다. 각 학생을 vertex라고 하고, 학생이 프로젝트를 같이 하고 싶어하는 다른 학생을 방향성 있는 edge로 표현하여 그래프를 만들 수 있습니다. 위와 같은 그래프가 있다고 해봅시다. 학생1은 학생2를 선호하고.. 이전 1 다음
