본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 2531 회전초밥 출처: https://www.acmicpc.net/problem/2531 Input 8 30 4 30 7 9 7 30 2 7 9 25 Output 5 - 슬라이딩 윈도우 기법을 이용해서 먹은 초밥 k를 갱신합니다. ex) [7 9 7 30 2 7 9 25] 초밥이 존재하고, 4개씩 먹을 때, 처음 [7 9 7 30] 상태에서 7 out / 2 in → [9 7 30 2] → 9 out / 7 in → [7 30 2 7] - 먹은 초밥의 종류는 check[3000 + 10]으로 처리합니다. 먹은 초밥 = [1 1 2 2] → check[1] = 2, check[2] = 2 → check = [0 2 2 ...] 이때, check[i] > 0인 경우 초밥의 종류(cnt)에 세어집니다. - 쿠폰은 적힌 숫자의.. 2021. 2. 20.
[BOJ] 백준 2805 나무 자르기 출처: https://www.acmicpc.net/problem/2805 Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com [탐색] Parametric Search [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다... 2021. 2. 20.
[BOJ] 백준 6549 히스토그램에서 가장 큰 직사각형 출처: https://www.acmicpc.net/problem/6549 참고 내용: https://www.acmicpc.net/blog/view/12 Input 7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0 Output 8 4000 히스토그램 특징을 이용하는 문제 ▶ [BOJ] 2571 색종이 - 3 [BOJ] 백준 2571 색종이 - 3 출처: https://www.acmicpc.net/problem/2571 Input 3 3 7 15 7 5 2 Output 120 완전 탐색방법으로 6중 for문을 이용할 수 있습니다. ① board[][] 배열에 『1』 로 표시된 모든 지점을 찾습니다. ② 찾은.. zoosso.tistory.com 이 문제에서 동일한 방식을 적용했을 경우 .. 2021. 2. 20.
[BOJ] 백준 2571 색종이 - 3 출처: https://www.acmicpc.net/problem/2571 Input 3 3 7 15 7 5 2 Output 120 완전 탐색방법으로 6중 for문을 이용할 수 있습니다. ① board[][] 배열에 『1』 로 표시된 모든 지점을 찾습니다. ② 찾은 지점에서 가로 길이 w, 세로길이 h를 조절해서 사각형 영역 설정 ③ 사각형 영역 내부가 모두 『1』 로 되어 있는지 확인합니다. → 영역 내부에서 모두 『1』 인 경우 너비를 비교해서 최대 넓이 값을 구합니다. [구현 코드] → O(N6) #define _CRT_SECURE_NO_WARNINGS #include int board[101][101]; int ans = 0; inline int max(int A, int B) { if (A > B.. 2021. 2. 20.
[BOJ] 백준 5639 이진 검색 트리 출처: https://www.acmicpc.net/problem/5639 Input 50 30 24 5 28 45 98 52 60 Output 5 28 24 45 30 60 52 98 50 [Jungol] 1716 이진트리 탐색와 비슷한 유형 노드를 얼마나 입력받는지 알 수 없으므로 아래와 같이 입력이 없어질 때까지 정점(노드)을 입력 받습니다. 이진 검색 트리가 형성되는 조건을 이용해서 왼쪽/오른쪽 서브트리를 확장해갑니다. 전위/중위/후위 순회에서 차이는 ( ① 왼쪽 서브 트리 ② 오른쪽 서브 트리 ③ ) 탐색 순서에서 Root Node ① ~ ③ 중에서 언제 방문하느냐 입니다. ① 전위 순회 ② 중위 순회 ③ 후위 순회 #define _CRT_SECURE_NO_WARNINGS #include usin.. 2021. 2. 20.
[BOJ] 백준 8983 사냥꾼 출처: https://www.acmicpc.net/problem/8983 Approach Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com ① 모든 동물에 대해 사격가능한 사대가 있는지 완전 탐색하는 경우 TLE 발생 → O(N × M) ② 특정 사대에서 사격가능한 동물을 표시하는 방법 사대의 위치를 X 라고 했을 때, 좌우로 사격가능한 범위는 1차로 [X-L, X+L]입니다. 해당 구간에서도 문제에서 정.. 2021. 2. 20.
[BOJ] 백준 15972 물탱크 출처: https://www.acmicpc.net/problem/15972 Input 2 3 5 1 -1 -1 3 2 -1 4 -1 2 -1 -1 4 3 -1 -1 -1 -1 Output 17 우선 순위 큐를 이용해서 물 높이가 낮은 칸 부터 처리합니다. 가장 외벽들로 부터 BFS 탐색을 시작합니다. (높이가 낮은것부터 처리하는 우선순위 큐 이용) (외벽 바깥에 구멍이 존재할 때, 물이 마지막 빠져나가는 곳이기 때문입니다.) 위와 같이 가장자리 외벽에 높이 2, 높이 3 구멍이 있다면 더 작은 높이로 시작 각 격자마다 구멍이 날 수 있는 곳은 최대 4개 입니다. 위(0), 오른쪽(1), 아래(2), 왼쪽(3) Q) BFS 탐색하면서 물의 높이는 어떻게 조정될까? 구멍으로 이어진(next) 칸의 물 높이는.. 2021. 2. 20.
[BOJ] 백준 1461 도서관 출처: https://www.acmicpc.net/problem/1461 Input 7 2 -37 2 -6 -39 -29 11 -28 Output 131 마지막에 모든 책을 놓는 순간을 제외하고는 0 지점에 돌아와서 갖다놓을 책을 들어야 합니다. 따라서 0 지점을 중심으로 접근할 수 있습니다. 가령, {-3, 1, 2}가 있다면 음수/양수를 구분해서 책을 갖다놓는 것이 이득입니다. → {-3}, {1, 2} 그렇다면 어떤 묶음을 마지막으로 갖다놓는 것이 이득일까? 제일 먼 거리에 위치한 묶음을 마지막으로 처리하면 다시 돌아올 필요가 없으므로 이득입니다. 따라서 {1, 2} → {-3} 으로 갖다 놓아서 걸음 거리 = (2*2) + (3) = 7 Test Case 분석 한번에 들 수 있는 책의 개수가 2개.. 2021. 2. 20.
[BOJ] 백준 1043 거짓말 출처: https://www.acmicpc.net/problem/1043 Input 4 3 0 2 1 2 1 3 3 2 3 4 Output 3 과장된 이야기를 하기위해서는 진실을 아는 사람이 아무도 없어야 합니다. 그렇다고 진실을 아는 사람이 없다고 무조건적으로 과장된 이야기를 하다보면 여러 파티 참석을 거듭하면서 거짓말쟁이로 알려지기 때문에 이러한 경우는 피해야 합니다. 즉, 과장된 이야기를 들은 사람이 추후에 진실된 이야기를 들어서는 안됩니다. 진실을 아는자 : {1} 파티 A = {5, 6} 파티 B = {4, 5} 파티 C = {3, 4} 파티 D = {2, 3} 파티 E = {1, 2} ex) 파티 D에서 과장된 이야기를 했다가 파티 E에서 진실된 이야기를 하게되면, 2번 사람을 통해 거짓말 쟁.. 2021. 2. 20.
[BOJ] 백준 5600 품질검사 출처: https://www.acmicpc.net/problem/5600 Input 2 2 2 4 2 4 5 0 2 3 6 0 1 4 5 0 2 3 5 1 Output 2 1 1 0 1 0 부품의 상태를 확신할 수 있는 경우는 언제일까? ① 검사 결과가 정상인 경우 → 3가지 부품이 모두 정상. ② 정상 + 정상 + x = 불합격 → x 부품 = 고장 상태 그 외의 경우에는 알 수가 없습니다. ex) 정상 + 고장 + x = 불합격 → x의 상태는 알 수 없습니다. ex) 고장 + 고장 + x = 불합격 → x의 상태는 알 수 없습니다. ex) 정상 + 정상 + x = 불합격 → x의 상태는 알 수 없습니다. 부품들의 상태를 알 수 없는 상태(= 2)로 초기화 합니다. 그 후, 검사 결과 = 합격인 부품.. 2021. 2. 20.
반응형

티스토리툴바