백준[1208] 부분수열의 합 2
2022. 1. 9. 21:06
Algorithm/BOJ
문제 링크 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를..
2021년 회고
2022. 1. 1. 23:12
끄적
2022년이 된 기념으로 2021년 회고를 해보려고 한다. 하고 싶은 일을 찾기 위해 최대한 많은 경험을 하려 노력했지만 그렇게 많은 경험을 해보진 못한 것이 아쉽다. 지금까지 해본 개발이 모두 재밌긴 했지만 아직 못해본 분야들이 많기 때문에 다 해보고 정하고 싶다. 2021년에는 전반적으로 학교 공부와 PS 공부를 하며 개발 공부를 틈틈이 했다. 학점도 2학년만 평균 내면 4.0 이상으로 나쁘지 않다. 블로그 쓰기 시작한 것과 PS 공부를 한 것이 올해 한 일중에 가장 잘한 것 같다. 깃헙 잔디를 채우려고 의도하면서 커밋을 한건 아닌데 이 정도면 그래도 볼만하게 채워진 거 같다. 나름 열심히 살았을지도,,? PS 2021년에 처음으로 PS공부를 시작해서 글을 쓰는 시점까지 381문제를 풀었고 solve..
백준[6086] 최대 유량
2021. 12. 27. 15:05
Algorithm/BOJ
문제 링크 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..
백준[1202] 보석 도둑
2021. 11. 24. 13:11
Algorithm/BOJ
문제 링크 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) 모..
백준[5719] 거의 최단 경로
2021. 11. 23. 16:50
Algorithm/BOJ
문제 링크 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만큼 시간 초과가 발생한다...
백준[15678] 연세워터파크
2021. 11. 23. 15:04
Algorithm/BOJ
문제 링크 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..
백준[1671] 상어의 저녁식사
2021. 11. 18. 22:20
Algorithm/BOJ
문제 링크 http://icpc.me/1671 1671번: 상어의 저녁식사 어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크 www.acmicpc.net 풀이 이분 매칭을 이용하여 풀 수 있다. 먹을 수 있는 상어들을 이분 매칭으로 최대 매칭을 구하면 되는데 문제는 같은 상어끼리 먹고 먹히는 경우다. 모든 수치가 같다면, 서로 먹히고 먹을 수 있는데 이 경우를 예외 처리해줘야 한다. 수치가 같은 상어들이 있다면 이미 서로 먹지 못하게 자기보다 인덱스가 작은 상어는 먹지 못하도록 한다. 코드 #include #include struct shark { int..
백준[11376] 열혈강호 2
2021. 11. 18. 17:31
Algorithm/BOJ
문제 링크 http://icpc.me/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, www.acmicpc.net 풀이 이분 매칭으로 풀 수 있다. 2명과 연결을 하기 위해서 dfs함수를 두 번 호출시키면 된다. 코드 #include #include #include using namespace std; const int N = 1003; vector v[N]; bool visited[N]; int B[N]; bool dfs(int a) { visited[a] = true; for (auto b : v[a]) { if ..
백준[1017] 소수 쌍
2021. 11. 17. 15:32
Algorithm/BOJ
문제 링크 http://icpc.me/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net 풀이 이분 매칭과 에라토스테네스의 체를 이용하여 풀 수 있다. 우선 2000이하의 모든 소수를 에라토스테네스의 체를 이용하여 판별해놓는다. 그 후에 첫번째 수와 소수를 만들 수 있는 수 k를 하나 잡고 나머지 수들을 모두 소수 쌍으로 만들 수 있는 k들을 모두 구하면 된다. 나머지 수들을 모두 소수 쌍으로 만들 때 이분 매칭을 이용한다. 간선을 연결할 때는 소수 쌍을..
백준[2243] 사탕상자
2021. 11. 17. 14:31
Algorithm/BOJ
문제 링크 http://icpc.me/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 풀이 백준 12899 데이터 구조 이 문제와 거의 동일한 문제다. 세그먼트 트리를 이용하여 k번째 수를 빠르게 구하는 문제다. 업데이트는 일반 세그먼트 트리 업데이트와 비슷하게 하고, 쿼리를 약간 다르게 구현한다. k번째 수를 구할 때, 왼쪽 자식 노드의 값은 L이라 한다면, k L이라면 오른쪽 자식 중 k - L번째 수를 구하는 ..
백준[16927] 배열 돌리기 2
2021. 11. 16. 20:47
Algorithm/BOJ
문제 링크 http://icpc.me/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 풀이 구현 문제다. 위의 그림과 같이 돌려야 하는 수들을 미리 덱에 저장해 두고, 덱의 맨 앞에 맨 뒤의 수를 집어넣는 것을 R번 하면 된다. 그런데 이때 R이 10^9으로 매우 크기 때문에 그냥 돌리면 시간 초과가 난다. 그렇기 때문에 덱의 크기만큼 돌리면 다시 덱이 초기의 상태랑 똑같아지기 때문에 R % (덱의 크기)만..
백준[5446] 용량 부족
2021. 11. 16. 13:52
Algorithm/BOJ
문제 설명 http://icpc.me/5446 5446번: 용량 부족 팀포2 덕후 연수는 팀포2를 다운받던 도중 하드 용량이 부족하다는 것을 알았다. 이때는 침착하게 팀포2를 하지 말거나 하드를 새로 사면 되지만 불가능했고, 결국 하드에서 쓸모없는 파일을 지 www.acmicpc.net 풀이 트라이를 이용해서 풀 수 있다. 트라이에 문자열을 삽입할 때, 지워야 하는 문자열이 끝날 때, 지워야 하는 문자인지, 지우면 안 되는 문자인지를 체크하며 삽입을 한다. 그럼 어떠한 한 노드의 상황 3가지이다. 1. 지워야 하고, 지워도 되는 상황 -> 자식 노드까지 한 번에 지워버린다 2. 지우면 안 되면서, 어떤 지워야 하는 문자열의 마지막 문자인 상황 -> *없이 rm abc와 같이 지운다 3. 지워야 하지만 지..
백준[17831] 대기업 승범이네
2021. 11. 15. 18:05
Algorithm/BOJ
문제 링크 http://icpc.me/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net 풀이 트리에서 dp를 통해 풀 수 있다. dp[i][0] : 노드 i가 멘티가 아닐 때, 최댓값 dp[i][1] : 노드 i가 멘티일 때, 최댓값이라 하자. dp[i][0] = max(dp[i의 자식 노드][0], dp[i의 자신노드][1] + cost[i] * cost[i의 자식노드)의 총합 (이때, 멘티는 최대 1명만 선택 가능) dp[i][1] = dp[i의 자식 노드][0]의 총..
백준[19581] 두 번째 트리의 지름
2021. 11. 15. 13:27
Algorithm/BOJ
문제 링크 http://icpc.me/19581 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net 풀이 bfs/dfs를 이용하여 풀 수 있다. 임의의 점을 하나 잡고, 그 점에서 가장 먼 점을 구한다. 그때 이 가장 먼 점을 a라고 하자. a에서 가장 먼 점을 구한다. 그때 이 점을 b라고 하자. 그럼 이때 a, b의 거리가 트리의 지름이 되고, 이 두 점이 트리에서 가장 먼 두 점이다. 그럼 이제 이 두 점 사이 거리를 제외한 가장 먼 거리를 찾아야하기 때문에, a에서 b를 제외한 가장 먼 거리를 ..
백준[16978] 수열과 쿼리 22
2021. 11. 13. 23:20
Algorithm/BOJ
문제 링크 http://icpc.me/16978 16978번: 수열과 쿼리 22 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. www.acmicpc.net 풀이 세그먼트 트리를 이용하여 풀 수 있다. 쿼리를 입력받은 순서대로 하지 않고, i번째 1번 쿼리를 하기 전에 k n; for (int i = 1; i > ipt; update(1, 0, N, ipt, i); } vector a; vector b; int t = 0; int q; cin >> q; for (int i = 0; i < q; i++) ..