Doby's Lab

https://www.acmicpc.net/problem/1321 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net N번 부대에 필요한 사람 수만큼 사람을 1번부터 차례대로 집어넣는다. 어떠한 X번 군번이 주어졌을 때 이 사람은 어느 부대를 들어가야 하는지 알아내야 하는 문제다. 1번 부대부터 필요한 사람 수들을 더하면서 만족하는 범위 안에 들어가면 답을 도출할 수 있다. 하지만, 쿼리는 M개 부대의 수는 N개로 O(N * M) >> O(N * M), 500,000 * 10,000이 되어 시간 초..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 들어가기 앞서 어느 날 보니 다른 기초 알고리즘들은 최소 한 개라도 포스팅이 있는데 그리디만 없었다. 어떻게 보면 코테나 좋은 PS를 위해서 구현, 그리디, DP, 문자열 등은 완전 마스터해야 한다고 생각하는데 (주관적인 생각으로 다른 알고리즘들은 기법이자 프레임이지 위에 언급한 키워드들은 모두 생각에 의존을 많이 하기 때문이다.) 그렇다고 아예 그리디 문제를 안 풀었던 건 ..

https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 갑자기 프로그래머스 생각나서 오랜만에 들어가 봤다가 확실히 프로그래머스 문제는 문자..

https://www.acmicpc.net/problem/5590 5590번: 船旅 入力の 1 行目には2つの整数 n, k (1 ≦ n ≦ 100, 1 ≦ k ≦ 5000) が書かれている． これは，島の数が n 島で，入力が k + 1 行からなることを表す． i + 1 行目 (1 ≦ i ≦ k) には， 3 個または 4 個の www.acmicpc.net 파파고 돌려서 번역했다. 다익스트라 문제였다. 0 b c: b에서 c로 가는 최단 경로를 구하라. 갈 수 없다면 -1 1 b c d: 는 b와 c를 이어주는 가중치가 d인 양방향 경로가 생긴다. [AC 코드] #include #include #include #include #define pii pair #define MAX (100 + 1) #define INF ..

https://www.acmicpc.net/problem/13116 13116번: 30번 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1 www.acmicpc.net 이진 트리라서 treeSet 함수에서 세그먼트 트리처럼 구현해주었다. void treeSet(int node, int pnode) { level[node] = level[pnode] + 1; parent[node] = pnode; if (node * 2 + 1 < MAX) { treeSet(node * 2, node); treeSet(node * 2 + 1, node..

https://www.acmicpc.net/problem/1306 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net 이번 문제는 문제에서 "가장 강렬한 빛의 광고판만이 눈에 들어온다."라는 말에서 구간 최댓값 세그 트리를 짜주면 되는 문제였다. 다만 어떤 구간인지에 관해서는 "슬라이딩 윈도우"라는 알고리즘(?)이 튀어나왔었다. 잠깐 구글링 해봤는데 알고리즘이라 하긴 그렇고, 테크닉(?) 같은 느낌이다. 따로 설명은 하지 않겠다. (나중에 어려움을 겪으면 그때 정리하겠다.) 시야 M이 주어..

https://www.acmicpc.net/problem/18436 18436번: 수열과 쿼리 37 길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다. 3 l r: l ≤ i ≤ www.acmicpc.net 이번 문제에서 포인트는 3가지라고 생각한다. (그냥 2가지 + 개인적인 1가지) 홀수 세그 트리, 짝수 세그 트리 둘 다 만들 필요 없다. 홀수 세그 트리로 만드는 게 더 편하다. update를 전처리 함수를 차용해서 만들었다. [홀수 세그 트리, 짝수 세그 트리 둘 다 만들 필요 없다.] 처음엔 둘 다 만들어야 하나 생각했지만 하나..

https://www.acmicpc.net/problem/6218 6218번: Balanced Lineup For the daily milking, Farmer John's N cows (1 1; return maxTree[node] = max(maxInit(start, mid, node * 2), maxInit(mid + 1, end, node * 2 + 1)); } int maxQuery(int start, int end, int node, int left, int right) { if (start > right || end q; for (int i = 1; i > arr[i]; } minInit(1, n, 1); maxInit(1, n, 1); f..