BOJ 문제풀이 (W22)

10806 부분합

투포인터를 사용하여 답을 갱신해주면 됩니다.

다만 이 문제에서 중요한 점은 후에 따로 글로도 쓸 주제이지만 loop invariant입니다.

각각의 원소에 대해서 그 원소를 끝으로 할 때, 합이 s이상이 되게하는 가장 인덱스가 큰 시작지점을 찾아 주는 반복문을 하나 넣어 loop invariant를 설정하면 됩니다.

    while (start+1<=end && sum-arr[start]>=s) {
            sum-=arr[start];
            start++;
        }

1992 쿼드 트리

대표적인 분할정복 문제입니다.

주어진 배열을 4등분하여 분할정복을 돌아주면 됩니다.

인덱스 슬라이싱 할 때 거리를 따로 구해서 슬라이싱해야하는 점이 구현의 팁입니다.

 

17626 four squares

1개일때, 2개일때, 3개일때 까지는 그냥 반복문으로 처리해주면 됩니다.

4개일때가 문제인데 이는 주어진 정수에서 3개로 만들 수 있는 값을 빼고 이렇게 구한 값이 배열에 있는지 이분탐색을 통해 찾아주었습니다.

 

7662 이중 우선순위 큐

저는 진짜 우선순위 큐를 2개 만들어서 구현하려 했는데 실패했고🏳️ set을 통해 구현했습니다.(🙋🏻‍♂️ 도움!)

 

10830 행렬 제곱

역시 대표적인 분할정복 문제입니다.

이전에 풀었던 제곱연산 문제와 같습니다.

저는 행렬 구조체와 행렬 곱 연산을 따로 만들어서 문제를 해결했습니다.

 

9095 1,2,3 더하기

loop dp를 이용하여 문제를 해결했습니다.

다만 3+1과 1+3이 각각 카운팅된다는 점을 유의하여 dp[n]= dp[n-1]+dp[n-2]+dp[n-3] 이라는 점에 유의하면 쉽게 해결 할 수 있습니다.

 

11724 연결 요소의 개수

유니온 파인드를 이용해 카운팅 했습니다.

 

11723 집합

배열의 크기를 20으로 잡고 해당 인덱스가 1이면 있고 0이면 없다는 식으로 비트연산을 이용해 문제를 풀었습니다.

 

2579 계단오르기

그냥 대표적인 dp문제인 만큼 정해를 써서 풀었습니다.

지금 n개의 계단을 올랐고 여기까지 연속된 i개의 계단을 밝았을때 얻는 최대 점수(i=0,1,2)

이렇게 배열을 잡아 채웠습니다.