Algorithm/BOJ

[BOJ] - python 경찰차 (빡구현 + dp + dfs)

https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 오늘은 그냥 스프란드-그런디 게임이론중에 대표문제인 님게임 시리즈를 둘러보더가, 좀 재밌는 dp문제 없나 싶어서 인터넷을 보다가 KOI 중등 2번을 발견하고 바로 풀게 되었습니다. 예전에는 KOI 초등부 문제에도 벽을 느껴서 잘 풀지 못하는 나였는데, 벌써 중등부 문제를 차근차근 풀고 있다니 너무 대견했다. 문제를 처음 보니, 빡구현 + dfs + dp문제 같았습니다. 전형..

[BOJ] - python 수열과 쿼리 21, 22 ( lazy propagation segment tree, offline query ) + Fenwick Tree

https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 이전에 공부한 느리게 전파되는 세그먼트 트리와 관련된 문제입니다. 사실 이 문제는 lazy propagation을 사용하지 않고도 해결할 수 있다. 바로 펜윅트리인데요 펜윅트리란..? https://www.acmicpc.net/blog/view/21 펜윅 트리 (바이너리 인덱스 트리) 블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를..

[BOJ] - python 열혈강호 (최대유량 + 이분매칭)

https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 그냥 갑자기 에드몬드 카프 알고리즘이 떠올라서,,,? class7 도장깨기 하고 있는데, 이분매칭 간단한 문제가 있길래 풀어봤다. import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) ans = 0 def dfs(n): for i in task[n]: if check[i]: continue check[i] = 1 if not..

[BOJ] - python 스터디 그룹 (정렬 + 그리디 + 투포인터)

https://www.acmicpc.net/problem/14572 14572번: 스터디 그룹 첫 줄에 학생의 수 N, 알고리즘의 수 K, 문제에 설명한 D가 주어진다. (1 ≤ N ≤ 105, 1 ≤ K ≤ 30, 0 ≤ D ≤ 109) 이어 N명의 학생에 대한 정보가 아래와 같이 주어진다. M d (0 ≤ M ≤ K, 0 ≤ d ≤ 109): 해 www.acmicpc.net 문제는 이러하다, 보자마자 오,, 쉽겠는데? 하고 풀었다가 거진 5시간을 버린 문제이기도 해서 정리해본다. 우선 문제를 보자마자 $E$ = (그룹 내의 학생들이 아는 모든 알고리즘의 수 - 그룹 내의 모든 학생들이 아는 알고리즘의 수) * 그룹의 수라고 하길래 그룹의 수를 가장 올리면 그 나머지 항은 자연스럽게 올가갈 것이라 생각..