본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 17615 볼 모으기 출처: https://www.acmicpc.net/problem/17615 Input 9 RBBBRBRRR Output 2 ① 각 색깔의 개수를 센다. (빨간색 볼, 파란색 볼의 개수) → 더 적은 개수의 색깔을 지닌 공을 옮기는 것이 효율적입니다. ② 왼쪽부터 연속된 색깔의 개수를 세어서 그만큼 해당색의 전체개수에서 뺀다. → 기존의 답보다 작으면 갱신 (나머지 볼을 왼쪽으로 옮기는 경우) ③ 오른쪽부터 연속된 색깔의 개수를 세어서 그만큼 해당색의 전체개수에서 뺀다. → 기존의 답보다 작으면 갱신 (나머지 볼을 오른쪽으로 옮기는 경우) R B B B R B R R R ① 빨간색볼이 5 개, 파란색볼이 4 개로 정답 후보는 4 이다. ② 왼쪽부터 연속한 볼은 빨간색 1 개이다. → 빨간색볼이 총 5 개이.. 2021. 2. 25.
[BOJ] 백준 2450 모양 정돈 출처: https://www.acmicpc.net/problem/2450 Input 8 1 3 3 2 1 1 3 2 Output 2 정돈된 최종 모양은 총 6가지 입니다. order[] = [1 2 3] / [1 3 2] / [2 1 3] / [2 3 1] / [3 1 2] / [3 2 1] 위의 경우 [동그라미, 네모, 세모]로 [3 2 1] 구성으로 모여있다고 볼 수 있습니다. 각각의 경우를 구성하기 위해 바꾸기 횟수를 구해보면 됩니다. ① 6가지 경우 중 order[]를 하나 정해놓고 ② 해당 위치에 있는 다른 모양의 개수를 세어서 교환해야 하는 횟수를 계산 시뮬레이션 배치하고자하는 순서 order[] = [3 2 1]일 때, arr[] = [1 3 3 2 1 1 3 2] → cnt[] = [3 2.. 2021. 2. 25.
[BOJ] 백준 10709 기상캐스터 출처: https://www.acmicpc.net/problem/10709 Input 3 4 c..c ..c. .... Output 0 1 2 0 -1 -1 0 1 -1 -1 -1 -1 [구름의 움직임] ① 처음 구름이 있는 위치를 『0』 구름이 없는 위치를 『-1』 ② 한 행씩 오른쪽으로 탐색하면서 구름이 처음 있었던 위치이면 continue 구름이 없는 위치라면 왼쪽 지점에서 구름이 보이는 시점 + 1 처리 #define _CRT_SECURE_NO_WARNINGS #include char map[100][100]; int W, H, board[100][100]; int main() { // freopen("input.txt", "r", stdin); int i, j; scanf("%d %d", &W,.. 2021. 2. 25.
[BOJ] 백준 2641 다각형 그리기 출처: https://www.acmicpc.net/problem/2641 Input 10 1 4 1 1 4 3 3 3 2 2 3 3 2 2 1 4 1 1 4 3 3 1 4 4 3 3 3 2 1 1 2 4 4 1 1 1 2 3 3 2 3 Output 2 3 2 2 1 4 1 1 4 3 3 4 4 1 1 1 2 3 3 2 3 문제에서 모양수열은 한 개의 다각형을 그리기에 출발점만 다를 뿐 그려지는 모양은 같습니다. - 점 A에서 출발하는 다각형 (2): 1 4 1 1 4 3 3 3 2 2 - 점 B에서 출발하는 다각형 (3): 3 2 2 1 4 1 1 4 3 3 그렇기에 이차원 배열에 따로 다각형 모양을 그려서 비교하지 않고, 주어지는 모양수열 원소를 하나의 출발점으로 생각하며 똑같은 경로를 그리는지 확인합.. 2021. 2. 25.
[BOJ] 백준 5582 공통 부분 문자열 출처: https://www.acmicpc.net/problem/5582 Input ABRACADABRA ECADADABRBCRDARA Output 5 DP[i][j] = A 문자열의 i번째 문자와 B문자열의 j번째 문자가 공통 부분 문자열의 마지막 문자로 하는 공통부분문자열의 최대 길이 if (A[i] == B[j]) D[i][j] = D[i - 1][j - 1] + 1; #include const int LM = 4002; int an, bn, D[LM][LM], ans; char A[LM], B[LM]; int main() { scanf("%s %s", A + 1, B + 1); for (int i = 1; A[i]; ++i) { for (int j = 1; B[j]; ++j) { if (A[i] .. 2021. 2. 25.
[BOJ] 백준 3653 영화 수집 출처: https://www.acmicpc.net/problem/3653 Input 2 3 3 3 1 1 5 3 4 4 5 Output 2 1 0 3 0 4 처음 DVD가 놓인 위치를 M+1 ~ N까지 『1』로 표시합니다. 그리고 각 DVD의 위치를 pos[] 배열에 저장합니다. Q) 4번째(= pos[4]) 놓인 DVD 위에 쌓여있는 DVD의 개수는? ▶ 1 ~ (7-1)까지 구간의 합 = 3개입니다. Q) 선택된 4번째 DVD를 어디로 옮기면 될까? ▶ 처음 M부터 해서 시작해서 1번째까지 입니다. (next = M) (그렇기 때문에 N 크기 앞에 M만큼 배열 크기 할당) Q) 여기서 4번째(pos[4] = 3) DVD 위에 놓인 DVD 개수는? 구간 [1, 3-1]까지의 구간합 = 0 + 0 = 0.. 2021. 2. 25.
[BOJ] 백준 3006 터보소트 출처: https://www.acmicpc.net/problem/3006 Input 3 2 1 3 Output 1 0 0 ① 1의 교환횟수 arr = [5 4 3 7 1 2 6] tree = [1 1 1 1 1 1 1] ← 단말 노드만 표시 Bubble Sort와 같이 교환(swap)하기 때문에 결국, 『1』 앞에 몇개의 숫자가 존재하는지 필요합니다. 세그먼트 트리에서 첫번째 부터 현재 숫자 『1』 앞 위치까지의 구간 합이 필요합니다. → [1, pos[1]-1] = [1, 4] = 4 『1』은 이동하였기 때문에 『0』으로 표시하면 다음 구간합을 구할 때 제외처리 할 수 있습니다. ② 7의 교환횟수 arr = [5 4 3 7 1 2 6] tree = [1 1 1 1 0 1 1] ← 단말 노드만 표시 『7.. 2021. 2. 25.
[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 출처: https://www.acmicpc.net/problem/11053 Input 6 10 20 10 30 20 50 Output 4 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com LIS (Longest Increasing Subsequence) subsequence은 연속하지 않아도 되는 부분 수열입니다. 따라서 subsequence의 개수는 N2 입니다. 완전 탐색 방법으로 접근할 경우 T.. 2021. 2. 25.
[BOJ] 백준 12015 가장 긴 증가하는 부분 수열 2 출처: https://www.acmicpc.net/problem/12015 Input 6 10 20 10 30 20 50 Output 4 [BOJ] 11053 가장 긴 증가하는 부분 수열 제의 경우는 N이 최대 1000이기 때문에 DP로 해결가능하였지만 N의 최대 크기가 증가하였기에 구간의 최대값을 가지는 세그먼트 트리 이용 DP에서는 i 번째 숫자가 입력될 때, 0 ~ i-1번째 숫자 중에서 자기보다 작은 j번째 숫자를 찾아 DP[j]의 최대값을 구하는 것이었습니다. 세그먼트 트리에서는 i 번째 숫자 입력될 때, DP[j]의 최대값을 for문으로 탐색하지 않고 구간의 최대값 세그먼트 트리를 이용하는 것입니다. 즉, tree[]의 단말 노드에는 i번째가 숫자가 입력되었을 때, 0 ~ i-1까지 최대값 +.. 2021. 2. 25.
[BOJ] 백준 2792 보석상자 출처: https://www.acmicpc.net/problem/2792 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. 25.
반응형

티스토리툴바