티스토리
관련 서비스
  • Symbols스토리 홈바로가기바로가기
  • 브런치브런치스토리바로가기바로가기
  • 카카오스토리카카오스토리바로가기바로가기

mangu
검색하기
블로그 홈

블로그 홈

mangu

mangu.tistory.com/m

잘못된 정보가 있다면 댓글 달아주세요.

구독자
5
방명록 방문하기
공지 👨🏻‍💻Who am I? 모두보기

주요 글 목록

  • [백준] 23245 Similarity 문제 링크 http://icpc.me/23245 23245번: Similarity In modern application systems, a recommendation system is very widely used to recommend books, music, ads, items, etc. The recommendation system needs to attract other users by providing the most interested items to each user. One way of recommendation is www.acmicpc.net 문제 출처는 2021 icpc 온라인 예선이다. 풀이 (pi < pj < pk)&& (qi < qj < qk) 인 (i, j, k)를 구하면 되.. 공감수 0 댓글수 0 2022. 7. 5.
  • [백준] 2679 맨체스터의 도로 문제 링크 http://icpc.me/2679 2679번: 맨체스터의 도로 맨체스터에 있는 도로는 모두 일방 통행이다. 또한 이 도로는 모두 1시간에 지나갈 수 있는 차의 개수 제한이 있다. 길(경로)에도 차의 개수 제한이 있는데, 이것은 이 길에 있는 도로의 제한 중 www.acmicpc.net 풀이 네트워크 플로우를 기반으로 하고, 우선순위 큐를 이용한 풀이와 이분 탐색을 이용한 풀이가 있다. 차의 개수는 네트워크 플로우를 이용하면 쉽게 구할 수 있지만, 길 1개를 이용할 때의 최대 개수는 구하기 어렵다. 일반적인 네트워크 플로우처럼 경로를 고른다면, 경로를 고르는 순서에 따라 어떤 길에 한 번에 보낼 수 있는 최대를 보내지 않을 수 있다. 그렇기 때문에 다른 처리를 해줘야 한다. 우선순위 큐 풀이 .. 공감수 0 댓글수 0 2022. 6. 5.
  • [백준] 8916 이진 검색 트리 문제 링크 http://icpc.me/8916 8916번: 이진 검색 트리 각 테스트 케이스에 대해서, 입력으로 주어진 순열과 같은 트리를 만드는 순열의 개수를 9,999,991로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 3 2 5 4 1 6라는 예제가 있을 때 가장 앞에 나오는 3은 루트 노드로 순서가 바뀔 수 없다는 사실은 조금만 생각해본다면 알 수 있다. 그럼 2 5 4 1 6를 3의 왼쪽 트리와 3의 오른쪽 트리로 나눌 수 있다. 3보다 작은 2 1은 왼쪽 트리가 3보다 큰 5 4 6은 오른쪽 트리가 될 것이다. 그렇다면 재귀적으로 2 1과 5 4 6은 각각 트리가 되고, 첫 번째 수는 루트가 될 것이다. 여기서 조금 더 관찰해 본다면, 같은 모양의 트리가 나오기 위해서는 작은 .. 공감수 0 댓글수 0 2022. 5. 19.
  • [백준] 3878 점 분리 문제 링크 http://icpc.me/3878 3878번: 점 분리 평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 www.acmicpc.net 풀이 두 컨벡스 헐이 서로 만나지 않게 하면 된다. 검정 컨벡스헐을 구성하는 점을 A, 흰색 컨벡스 헐을 B라 하자. 두 컨벡스 헐이 만나지 않기 위해선 A의 점들 중 어떤 점도 B 내부에 있으면 안 된다. 또한 B의 점들도 A에 있으면 안 된다. 또한 두 컨벡스 헐을 이루는 모든 직선들끼리 서로 만나면 안 된다. 코드 #include using namespace std; using ll = long long; #de.. 공감수 0 댓글수 0 2022. 4. 27.
  • [백준] 1377 버블 소트 문제 링크 http://icpc.me/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 개인적으로 알고 나면 쉽지만 아이디어가 많이 어려운 문제인 것 같다. 문제를 잘 관찰을 해본다면 출력을 하는 수는 정렬이 끝난 다음 시점의 i값이다. 편의상 인덱스가 작은 방향을 왼쪽, 큰 방향을 오른쪽이라 하겠다. 정렬이 모두 끝난 시점을 알기 위해서는 왼쪽으로 밀려난 수 중 가장 많이 밀려난 수가 몇 번 왼쪽으로 밀려났는지를 알면 된다. 그 이유는 왼쪽으로 가야 하는 어떤 수는 한번 .. 공감수 0 댓글수 0 2022. 4. 12.
  • [백준] 2449 전구 문제 링크 http://icpc.me/2449 2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 풀이 오랜만에 되게 재밌게 푼 dp문제다. 3차원 dp로 풀었는데 다른 사람 코드 구경하면서 2차원 dp로 내 풀이보다 훨씬 쉽게 풀 수 있는 걸 발견했다. 이 글에선 3차원 풀이를 작성하겠다. 시간 복잡도는 O(N^3 * K)에 해결할 수 있다. dp[l][r][i] : 구간 [l, r]을 i로 만들었을 때 최소 경우의 수 a[i] : a번째 전구의 색 위와 같이 정의를 하면 세 가지 케이스로 점화식을 세.. 공감수 0 댓글수 0 2022. 4. 1.
  • [백준] 7620 편집 거리 문제 링크 http://icpc.me/7620 7620번: 편집 거리 가장 짧은 편집 스크립트를 출력한다. 한 명령을 한 줄에 하나씩 출력하며, 문제의 괄호에 나와있는 (a, d, m, c)중 하나를 출력하고, 그 명령을 수행하는데 사용한 글자를 출력한다. (출력할 글자 www.acmicpc.net 풀이 dp 역추적을 하는 문제다. 하지만 메모리를 특이하게 관리해야 하는 처음 보는 문제다. 역추적을 하기 위해서 dp테이블을 모두 가지고 있기엔 테이블의 크기가 17000 * 17000 * 4byte로 너무 크다. 그렇기 때문에 역추적을 위한 테이블을 17000 * 17000 * 2bit로 만들어 메모리를 최적화시켜야 한다. 역추적 테이블은 unsigned char 한 칸에 비트 연산을 이용하여 정보를 4개.. 공감수 0 댓글수 0 2022. 3. 24.
  • [백준] 1368 물대기 문제 링크 http://icpc.me/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 풀이 MST를 이용하여 풀 수 있다. 가상의 루트 노드를 하나 만들고, 어떤 물을 킬 때, 루트 노드에서 물을 끌어온다고 생각하면 쉽게 풀 수 있다. 물은 키는 행위는 루트 노드와 킬 노드를 연결시키는 것으로 매핑시키면 된다. 코드 #include using namespace std; struct T { int x, y, z; }; vector arr; int mat[302][302];.. 공감수 0 댓글수 0 2022. 3. 16.
  • [백준] 1126 같은 탑 문제 링크 http://icpc.me/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 풀이 dp문제다. dp인 것을 못 알아차리고 고민하다가 알고리즘 분류를 봤다. 처음 생각했던 점화식은 dp[i][a_size][b_size] : i번째 까지 봤을 때 a기둥의 사이즈와 b기둥의 사이즈로 dp를 정의하는 것이었다. 그러나 이 풀이는 52 * 5e5 * 5e5로 시간초과가 발생할 것이다. 그래서 a기둥과 b기둥의 높이를 더 컴팩트하게 정의할 수 있는 방법을 생각했다. 결론은 더 큰 기둥의.. 공감수 0 댓글수 0 2022. 2. 26.
  • [백준] 2662 기업투자 문제 링크 http://icpc.me/2662 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 풀이 배낭 문제라고도 불리는 웰노운인 knapsack문제다. dp를 이용하여 풀 수 있다. dp[i][j] = max(dp[i - 1][j - k] + arr[k][i]) (0 공감수 0 댓글수 0 2022. 2. 23.
  • [백준] 2481 해밍 경로 문제 링크 http://icpc.me/2481 2481번: 해밍 경로 길이가 같은 두 개의 이진수 코드 w1과 w2가 있다고 하자. 이 두 코드 사이의 해밍 거리(Hamming distance)는 w1과 w2의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 www.acmicpc.net 풀이 해밍 거리가 1인 경우는 비트 하나만 다른 것을 의미하기 때문에 비트가 하나만 다른 것들을 모두 그래프로 만든 후에 bfs를 돌리면 된다. 비트 하나만 바꿀 때는 XOR연산을 하면 된다. 그래프를 만들 때는 N개의 수에 k번 비트 연산을 하고 그 수가 존재하는지 map으로 확인하면 O(NKlogN)에 만들 수 있다. cf) 입력을 int형으로 받아서 2시간 가까이 뇌절을 했다. 30자리.. 공감수 0 댓글수 0 2022. 2. 17.
  • [백준] 1533 길의 개수 문제 링크 http://icpc.me/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net 풀이 본대 산책 2과 비슷한데 가중치가 있는 문제다. 가중치가 5 이하이기 때문에 정점을 늘려서 풀 수 있다. 정정 하나를 v0 v1 v2 v3 v4로 나누고 각 정점별 가중치를 1로 둔다. 이때 만약 u -> v의 가중치가 3이라면 u0 -> v2 -> v1 -> v0과 같은 방식으로 u -> v의 간선을 연결할 수 있다. 이렇게 그래프를 약간 변경하여 행렬제곱을 T제곱을 하면 O((5.. 공감수 0 댓글수 0 2022. 2. 3.
  • [백준] 12850 본대 산책 2 문제 링크 http://icpc.me/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 유배당한 불쌍한 정보대생을 위한 문제다.. 분할 정복을 이용한 O(logN) 행렬 제곱을 이용하여 풀었다. 이 글을 참고하여 풀었다. 행렬 곱셈식을 곱씹어본다면 왜 이렇게 풀이할 수 있는지 알 수 있다. Counting source to destination path of k length HERE author discusses three methods to count source to destination path of k length. I am not able to get the last method which is base.. 공감수 0 댓글수 0 2022. 1. 27.
  • [백준] 13977 이항 계수와 쿼리 문제 링크 http://icpc.me/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 모듈러 역원에 대해 알아야 하는 문제다. 모듈러 역원에 대한 내용은 여기를 참고하자. n!을 전처리하여 미리 구해두고, 각 쿼리마다 n! * ((n-r)! * r!)^(mod-2)을 구하면 된다. 이때 제곱은 분할정복을 이용하여 계산한다. 코드 #include using namespace std; using ll = long long; const ll mod = 1e9 + 7; const int N = 4e6 + 6.. 공감수 0 댓글수 0 2022. 1. 25.
  • [백준] 9465 스티커 문제 링크 http://icpc.me/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 dp문제다 dp[i][0] = max(dp[i-1][1], dp[i-2][1]) + arr[i][0] dp[i][1] = max(dp[i-1][0], dp[i-2][0]) + arr[i][1] 점화식은 위와 같다. 코드 #include using namespace std; const int N = 1e5 + 5; int arr[N][2], dp[N][2]; int main() { cin.tie(0)-.. 공감수 0 댓글수 0 2022. 1. 25.
  • [백준] 15824 너 봄에는 캡사이신이 맛있단다 문제 링크 http://icpc.me/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 수학 문제다. 각 수가 최댓값, 최솟값이 될 수 있는 경우의 수를 각각 잘 계산하면 된다. 정렬된 배열 arr에서 arr[i]가 최댓값이 될 수 있는 경우의 수는 arr[0]~arr[i-1]의 모든 조합의 수인 2^i 같고, arr[i]가 최솟값이 될 경우의 수는 arr[i+1]~arr[n-1]까지의 모든 조합의 수인 2^(n-i-1)이다. cf) 2^n을 미리 구해 놓을때 mod를 하지 않으면 시간 초과를 받을 수 있다. 파이썬에서 큰수 연산 곱하기의 시간복잡도가 O(n^1.585)라고 .. 공감수 0 댓글수 0 2022. 1. 25.
  • [백준] 2096 내려가기 문제 링크 http://icpc.me/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 메모리를 줄여서 사용해야 하는 dp문제이다. dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + arr[i][j] dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + arr[i][j] 위와 같은 점화식을 세울 수 있다. 점화식을 계산할 때 이전층까지의 정보만이 필요하기 때문에 전부 기억할 필요가 없다. 코드 #include u.. 공감수 0 댓글수 1 2022. 1. 25.
  • [백준] 3653 영화 수집 문제 링크 http://icpc.me/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 풀이 세그먼트 트리를 이용하여 풀 수 있다. 빼야 하는 dvd를 기준으로 위에 있는 dvd를 모두 세는 연산과 dvd를 하나 빼는 연산을 세그먼트 트리를 이용하여 할 수 있다. 이때 빼고 맨 위에 놓는 연산을 그냥 한다면 O(N)이 들기 때문에 배열을 M+N사이즈로 활용하여 아무것도 없는 곳은 0으로 dvd가 있는 곳은 1로 만들어 사용하며 특정 dvd의 인덱스는 따로 관리한다. 그렇기 때문에 dvd가 있는 .. 공감수 0 댓글수 0 2022. 1. 19.
  • 백준[1007] 벡터 매칭 문제 링크 http://icpc.me/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 풀이 수학 문제다. (a, b), (c, d) 점이 있을 때, (a-c, b-d) 또는 (c-a, d-b)인 두 벡터로 만들 수 있다. 위와 같은 성질을 이용하면 모든 점들 중 반절을 -를 곱하여 모두 더한 후 길이의 최솟값을 구하면 된다. 코드 #include using namespace std; using ll = long long; using pll = pair; bool positive[22]; ve.. 공감수 0 댓글수 0 2022. 1. 19.
  • 백준[14942] 개미 문제 링크 http://icpc.me/14942 14942번: 개미 자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너 www.acmicpc.net 풀이 LCA와 거의 유사한 느낌으로 풀었다. 각 노드별로 모두 위로 올라가며 갈 수 있는 최대를 구한다면 쿼리 하나당 O(N)이 들어 시간이 터질 것이다. 그렇기 때문에 sparse table을 이용하여 시간을 줄여야 한다. sparse table에는 dp[i][j]: 노드 j가 2^i만큼 조상 노드로 올라갔을 때의 비용과 조상 노드를 저장해놓는다. 이제 이 sparse table을 이용하면 쿼리당 시간.. 공감수 0 댓글수 0 2022. 1. 19.
  • 백준[13549] 숨바꼭질 3 문제 링크 http://icpc.me/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 다익스트라와 bfs로 풀 수 있다. 다익스트라로 풀고 다른 사람 코드를 구경하다가 그냥 bfs로도 풀 수 있는 것을 보고 다시 bfs로 풀어봤다. bfs로 풀이하려면 거리가 0인 부분, 1인 부분... 순서로 bfs를 돌려야 하기 때문에 큐에 미리 다 넣어놔야 한다. 코드 bfs코드 #include using namespace std; const int N = 1e5; int .. 공감수 0 댓글수 0 2022. 1. 18.
  • 백준[1865] 웜홀 문제 링크 http://icpc.me/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 플로이드 와샬을 이용하면 O(N^3)에 풀 수 있다. 플로이드 와샬을 돌린 후 dp[i][i]에 음수가 있는지 체크하면 된다. 코드 #include using namespace std; const int N = 502; const int INF = 1e8; int dp[N][N]; int main() { int tc; scanf("%d", &tc); while (tc--) { int n, m, w;.. 공감수 0 댓글수 0 2022. 1. 18.
  • 백준[7662] 이중 우선순위 큐 문제 링크 http://icpc.me/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 multiset을 이용하여 풀 수 있다. multiset은 정렬이 되어있는 균형 이진트리 형태로 구현돼있기 때문에 가장 큰 값과 가장 작은 값을 쉽게 구할 수 있다. 코드 #include using namespace std; int main() { int t; scanf("%d", &t); while (t--) { multiset ms; int n; scanf("%d", &n); while (n--) { c.. 공감수 0 댓글수 0 2022. 1. 14.
  • 백준[1238] 파티 문제 링크 http://icpc.me/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 다익스트라를 이용하여 풀 수 있다. 모든 점에 대해서 다익스트라를 돌려서 O(M^2logN)에도 풀 수 있지만, 관점을 약간 틀면 더 O(MlogN)에 풀 수 있다. 단방향 도로이기 때문에 순방향으로 x를 시작점으로 돌린다면 마을로 돌아가는 최간거리를 구할 수 있다. 그리고 역방향그래프를 x를 시작점으로 돌린다면 x까지 가는 최단거리를 구할 수 있다. 코드 #include usin.. 공감수 0 댓글수 0 2022. 1. 11.
  • 백준[1562] 계단 수 문제 링크 http://icpc.me/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 비트마스크 dp문제다. dp[자릿수][마지막 수][사용한 수]로 정의하면 dp[i][j][k | (1 공감수 0 댓글수 0 2022. 1. 9.
  • 백준[1208] 부분수열의 합 2 문제 링크 http://icpc.me/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 모든 조합을 뽑아서 확인해보면 O(2^40)이기 때문에 시간이 터진다. 그렇기 때문에 반절로 나눠서 모든 조합을 확인해봐야 한다. x + y = s를 이용하여 오른쪽 조합에서 하나를 뽑아 s - y가 왼쪽 조합에 몇 개 존재하는지 이분 탐색을 이용하여 확인하면 모든 경우를 확인할 수 있다. 이때 몇 개가 존재하는지 확인할 때 upper_bound - lower_bound를.. 공감수 0 댓글수 0 2022. 1. 9.
  • 백준[6086] 최대 유량 문제 링크 http://icpc.me/6086 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 풀이 네트워크 플로우로 풀 수 있다. 여기를 참고했다. 코드 #include #include #include #include using namespace std; struct Edge { int to, c, f; Edge *rev; Edge(int a, int b) : to(a), c(b), f(0), rev(nullptr) {} int spare() { return c - f; } void addFl.. 공감수 0 댓글수 0 2021. 12. 27.
  • 백준[1202] 보석 도둑 문제 링크 http://icpc.me/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 풀이 그리디로 풀 수 있다. 보석의 정보를 보석의 가격을 기준으로 내림차순으로 정렬한다. 그 후에 처음부터 가격이 높은 것부터 차례대로 무게보다는 크거나 같은 최소 가방을 찾으며 가방을 매칭 시켜주면 된다. 가방을 매칭시켜줄때는 lower_bound를 이용하면 된다. 또한 가방을 매칭시키고 바로 없애주기 위해 multiset 자료구조를 사용한다. cf) 모.. 공감수 0 댓글수 0 2021. 11. 24.
  • 백준[5719] 거의 최단 경로 문제 링크 http://icpc.me/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 다익스트라를 두 번 돌려서 풀 수 있다. 최단 경로로 오기 위한 모든 경로를 처음 다익스트라를 돌릴 때 prv 벡터에 어디서 온 건지 저장해놓는다. 이때 dist 값이 변경될 때 이차원 벡터를 초기화하고 그 벡터에 넣는 방식으로 구현했다. 그런 후 dfs를 통해 최단 경로들을 모두 없앤다. 이때 중복되는 dfs를 제거하지 않으면 최대 재귀 호출을 10^4만큼 시간 초과가 발생한다... 공감수 0 댓글수 0 2021. 11. 23.
  • 백준[15678] 연세워터파크 문제 링크 http://icpc.me/15678 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net 풀이 세그먼트 트리로 dp최적화를 하는 문제다. dp[i] = max(dp[i], max(dp[i - k]) + arr[i]) (1 1) using namespace std; using ll = long long; const int N = 1e5 + 5; ll dp[N]; ll tree[4 * N]; ll query(int node, int s, int e, int qs, in.. 공감수 0 댓글수 0 2021. 11. 23.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.