기술 블로그

※ 아래 문제도 풀어보자.(회의실 개수 최댓값 구하기) https://www.acmicpc.net/problem/1931 https://www.acmicpc.net/problem/11000 강의실 개수 최솟값을 구하는 문제이다. 시작시간 기준으로 오름차순 정렬한다. 우선순위 큐를 활용하여, 종료시간을 넣어주면서 시작시간을 활용한다. #include using namespace std; int N; vector v; int main() { //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin); cin.tie(0); scanf("%d", &N); int S, T; for (int i = 0; i < N; i++) { scanf("%d %..

https://hsdevelopment.tistory.com/772 배열이 주어지고, 배열의 구간에 수를 더하고 빼는 쿼리가 있다. 세그먼트 트리를 이용해도 되지만, 우리는 연산 중간에 배열의 값을 알 필요가 없고, 모든 쿼리(연산) 이후에 마지막 단 한 번만 구하면 되기 때문에, 누적합을 이용할 수 있다.

※ 이 문제는 1차원 배열에 대한 문제이고, 2차원 배열로 확장시킨 문제가 2021년 9월 11일 토요일 2022 카카오 블라인드 코딩테스트 6번에 출제됐다. ※ 이 글은 안즈님의 카카오 6번 문제 해설(누적합을 이용한 연산)을 참고하여 작성하였고, 제가 다시 편히 보기 위해 정리하였습니다. https://www.acmicpc.net/problem/19951 배열이 주어지고, 배열의 구간에 수를 더하고 빼는 쿼리가 있다. 세그먼트 트리를 이용해도 되지만, 우리는 연산 중간에 배열의 값을 알 필요가 없고, 모든 쿼리(연산) 이후에 마지막 단 한 번만 구하면 되기 때문에, 누적합을 이용할 수 있다. 문제에 대한 정답 코드는 맨 아래에 있다. 이 문제를 풀기 위한 누적합 연산 개념 설명(아래 사진)을 추가한다..

https://www.acmicpc.net/problem/1113 핵심은 높이를 2부터 입력된 최대 높이까지 각각 하나씩 채워주는 것이다. main() 함수 내의 for문 h의 의미는 "h보다 작은 곳을 찾아 높이를 딱 h까지 채우겠다."라는 의미로 해석하면 된다. 또한, dfs가 수행될 때, 바깥 쪽(행과 열이 0 또는 R - 1 또는 C - 1)일 때는 바깥 쪽으로 흘러내리므로, 이때는 답 구하는 연산에 셈하지 않는다.(bool형 변수인 stop 활용하였음) 1. 입력된 값들 중 최댓값 구하기(최대 높이 = H) 2. 2 ~ H 각각 수행 → h 3. h보다 미만인 곳을 찾아 vector에 넣어준다. 4. vector를 활용하여, dfs 수행 5. 바깥 쪽일 경우 답 구하는 연산에서 제외 6. 바깥 ..

https://www.acmicpc.net/problem/2665 처음에는 단순 queue로 구현했다가, 예제 1번의 답이 계속 5로 나왔다. 문제를 잘 읽어보면 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오. 라고 쓰여있는데, 이는 '검은 방'은 최대한 피해서 가야한다는 의미이다. 즉, 검은 방과 흰 방 중 우선순위가 더 높은 방은 흰 방이다. 이 부분에서 힌트를 얻어, queue말고 deque로 구현한다. 다음에 이동할 방이 검은 방 → deque의 맨 뒤(우선순위가 낮으므로) 다음에 이동할 방이 흰 방 → deque의 맨 앞(우선순위가 높으므로) #include using namespace std; #define MAX 55 int n, m[MAX][MAX]; int ..

https://www.acmicpc.net/problem/2810 핵심은 제일 끝 쪽(오른 쪽 끝)에 있는 사람은 오른쪽부터 먹는다. 그 이후이 사람은 왼쪽을 먹는다. "S"와 "LL" 파싱 없이 할 수 있을 것 같은데 그냥 파싱해봄 #include using namespace std; int n; string s; int main() { //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin); cin.tie(0); cin >> n >> s; int len = s.length(); string ps = ""; vector v; // "S"와 "LL"을 파싱하여 vector v에 담음. for (int i = len - 1; i >= 0..

https://www.acmicpc.net/problem/1525 문자열 처리 + bfs 방문처리는 문자열로 처리해준다. 문자열에 대한 방문처리는 set이 좋다. #include using namespace std; string s = "", goal = "123456780"; int dy[4] = { 1, 0, -1, 0 }; int dx[4] = { 0, 1, 0, -1 }; set st; int bfs() { queue q; q.push(s); st.insert(s); int ret = 0; while (!q.empty()) { int qs = q.size(); while (qs--) { string now = q.front(); q.pop(); if (now == goal) { return ret..

https://www.acmicpc.net/problem/2571 문제 풀이 1. 높이 누적합 2. 한 좌표(r, c)에 대해서 모든 경우의 수에 따른 사각형 넓이 구하기(simulation, getValue 함수) 3. 높이(세로)와 가로 길이 구할 때 조심. 높이는 항상 최솟값. 높이 : 그 열의 맨 아래에 있는 좌표값 + 1 - 자신의 현재 좌표 값 가로 : (r, c) ~ (r, j)에 해당 하는 단순 가로의 길이이므로, j - c + 1 #include using namespace std; #define MAX 101 int n, ans, p[MAX][MAX]; void draw(int r, int c) { for (int i = r; i < r + 10; i++) { for (int j = c..