알고리즘매일매일

https://www.acmicpc.net/problem/1541

부호는 +와 -만 있고 값을 최소로 만들면 되므로 - 이후의 값들은 모두 괄호로 적절히 묶어서 -로 만들어 주면 된다. 

예를 들어 문제에 나온 예시인 55-50+40의 경우 55-(50+40) 이런 식으로 만들어줄 수 있다.

55-50+40-10 인 경우에는 55-(50+40)-10 이런 식으로 묶어준다고 생각하면 되므로 그냥 - 이후의 값들은 모두 음수 값으로 처리해준다.

음수 값으로 바꾸기 위해서 나는 flag라는 변수에 처음에 1을 넣어놓고 -가 나오기 전까지는 숫자가 들어올 때마다 flag를 곱해줬다. 그리고 - 부호가 들어오면 flag를 -1로 만들어서 더해지는 숫자가 마이너스 값이 되도록 했다.

구체적으로는 입력으로 들어오는 문자열의 각 문자에 대해서

+인 경우 / -인 경우 / 그 외의 경우(숫자)로 나눠서 각각 처리해주었다.

먼저 숫자인 경우에는 num 변수에 숫자를 저장해놨다가 +나 -가 나와서 숫자가 끝나면 num을 최종 값인 ans 변수에 더해주었다. 숫자가 연속으로 나올 수 있기 때문에 이전에 저장된 수에 10을 곱해준 후에 현재 문자를 숫자로 바꿔서 더해준다.

 55-50+40

문제의 예시를 다시 보면

5가 나오면 먼저 num에 5가 저장된다. 처음에 num에는 0이 저장되어 있으므로 10을 곱해주는 것은 상관없다.

그다음에 또 5가 들어오면 기존에 있던 5에 10을 곱해줘서 50으로 만들어주고 새로 들어온 5를 곱해준다.

그리고 -가 나오면 num에 있는 55를 ans에 더해준다. 뒤의 50과 40도 같은 방법으로 만들 수 있다.

+인 경우는 그냥 이전까지의 숫자(num)를 ans에 더해주고 num을 초기화해주면 된다.

-인 경우에는 위의 설명처럼 flag를 -1로 바꿔준다. 그리고 +와 마찬가지로 앞에서 숫자가 끝났으므로, 최종 값(ans)에 이전까지의 숫자(num)를 더해준다. 

https://www.acmicpc.net/problem/11729

하노이 탑 문제는 재귀 호출을 이용하여 풀 수 있는 대표적인 문제이다.

먼저 옮기는 횟수는 원판의 개수가 n 개라고 했을 때 2의n제곱-1 이므로 먼저 출력해주고 시작할 수 있다.

장대 세개가 각각 a, b, c  (각각 1, 2, 3)라고 했을 때, n개의 원판을 a에서 c로 옮기려고 한다.

규칙에 따라서 맨 밑에 있는 원판이 c에 가장 먼저 놓여야 하는데, 그러기 위해서는 맨 밑 원판을 제외한 나머지 n-1개의 원판을 다른 비어있는 장대(b)로 옮겨놓아야 한다. 그리고 맨 밑 원판을 c로 옮겼으면 아까 옮겨 놓았던 n-1개의 원판을 다시 c로 가져온다.

이 때, a에서 b로 옮겨진 n-1개의 원판들도 같은 규칙으로 옮길 것이기 때문에 위의 내용을 그대로 재귀 함수로 구현해주면 된다.

즉, n-1개의 원판을 a에서 b로 옮기려고 하는 경우에 대해서 새로 구해주는 것이다.

a는 1, b는 2라고 했을 때, c는 6 - a - b로 표현할 수 있다.

a + b + c = 6

(1 + 2 + 3) = 6

밑의 코드에서는 처음 넘겨지는 a는 1, b는 3이다. (첫 번째 장대에서 세 번째 장대로 옮길 것이므로)

https://www.acmicpc.net/problem/2447

문제에는 아래 그림과 같은 출력 결과를 주고 규칙을 찾아서 별을 찍으라고 나와있다. N은 항상 3의 제곱 꼴인 수라는 게 힌트다.

아래 그림은 N이 27인 경우인데 27인 경우 27*27 모양이고 빈칸이 비어 있는 모양인 것을 볼 수 있다.

N이 9였다면 아래 그림과 같이 9*9 크기의 빨간 네모 부분이 출력됐을 거다. 여기서도 마찬가지로 가운데 부분이 비어있다는 것을 알 수 있다. N이 3인 경우에도 왼쪽 맨 위쪽 끝부터 3*3크기를 보면 가운데 비어있는 모양인 것을 볼 수 있다.

결국 이 문제는 처음에 27을 입력받았다면 3으로 나눠서 각각 9*9로 이루어진 9칸을 다시 9칸을 모두 각각 3으로 나눠서 3*3인 칸에 대해서 별을 찍으면 된다. 즉 재귀를 이용하여 분할 정복(Divide and Conquer)으로 풀 수 있다.

n이 1이 될때까지 계속 3으로 나눠서 재귀 호출을 한다. 호출에서 재귀 호출은 총 8번 일어난다.

가운데 빈칸을 제외하고 총 위쪽 3개, 아래쪽 3개, 가운데 2개를 별을 찍어줘야하기 때문이다.

별은 n이 1이 될때까지 분할한 후에 찍어준다.

예를 들어 n이 9인 경우 아래 그림에서 빨간 네모 부분과 같은 3*3 만큼씩 각각 8번 호출하게 된다. (가운데 부분은 호출하지 않기 때문)

처음에 (0,0)에서 시작했다면 그다음은 (0,3)에서 시작하고 그다음은 (0,6)에서 호출한다.

다시 그다음은 중간 시작점인 (3,0)이고 그다음 (3,3)은 가운데 이므로 호출하지 않고 넘어간다. 이런 식으로 재귀 호출을 진행하면

각 호출에서는 다시 3*3 에 대해서 다시 8번 호출을 하여 1*1이 되어서 별을 찍게 된다.

(배열의 크기는 문제에서 주어진 최대 값이 3의 8 제곱보다 큰 수 2200으로 잡았다)

https://www.acmicpc.net/problem/1655

값이 계속 들어올 때마다 중간값을 출력해주어야 하기 때문에 매번 정렬을 해서 가운데 값을 출력해주면 시간 초과가 발생한다. 따라서 이 문제는 최대 힙(Max heap)과 최소 힙(Min heap) (우선순위 큐)을 사용하여 풀 수 있다.

1. 최소 힙의 값들은 모두 최대 힙보다 크도록하고

2. 최대 힙의 크기가 최소 힙의 크기보다 1 크거나 같도록 유지하며 값을 넣는다.

3. 값을 넣어준 후 최대 힙과 최소 힙의 top 값을 비교해서 최소 힙의 top보다 최대 힙의 top이 더 크다면 값을 교환해준다.

그러면 최대 힙의 top값이 중간값이 된다.

문제의 예제 중 마지막 값인 5를 6으로 수정해서 예를 들어봤다.

1 5 2 10 -99 7 6

위와 같은 값들을 순차적으로 입력받는다고 하면

처음에 들어온 1은 max heap에 들어간다. 중간 값은 1

max heap : 1

min heap : 

다음에 5가 들어오면 max heap의 크기가 더 크므로 min heap에 값이 들어간다.

max heap : 1

min heap : 5

이때, max heap의 top보다 min heap의 top이 크므로 값의 변경은 일어나지 않고, 중간값은 max heap의 top인 1이다.

그다음에 2가 들어오면 크기가 같으므로 max heap에 들어가고 2는 5보다 작으므로 값의 변경은 일어나지 않는다.

max heap의 top인 2가 중간 값이다.

max heap : 1, 2

min heap : 5

다음으로 10이 들어오면 min heap의 크기가 더 작으므로 min heap에 들어가고 중간 값은 max heap의 top값인 2이다.

max heap : 1, 2

min heap : 5, 10

-99는 두 heap의 사이즈가 같으므로 max heap에 들어가고 중간 값은 2이다.

max heap : -99, 1, 2

min heap : 5, 10

7은 min heap으로 들어간다. 중간 값은 그대로 2이다.

max heap : -99, 1, 2

min heap : 5, 7, 10

마지막으로 6은 두 heap의 사이즈가 같으므로 max heap에 들어간다.

max heap : -99, 1, 2, 6

min heap : 5, 7, 10

이때, max heap의 top인 6이 min heap의 top인 5보다 크므로 두 값을 교환해주어야 한다.

max heap : -99, 1, 2, 5

min heap : 6, 7, 10

교환해주고 나면 max heap의 top인 5가 중간값이 된다.

c++에서 우선순위 큐는 기본적으로 최대 힙이기 때문에 최대 힙은 그냥 우선순위 큐를 하나 만들어주면 되고

최소 힙은 functionl을 include 해준후

 priority_queue<int, vector<int>, greater<int>> minheap;

이런 식으로 greater를 이용해서 만들어주면 된다.

처음에는 minheap에 값이 없으므로 top값을 가져올 수 없으므로 maxheap에만 값을 추가하고 다시 다른 값을 입력받도록 처리해주어야 한다. 아니면 top값을 비교할 때 minheap이 비어있는지를 검사해줘도 된다.

https://programmers.co.kr/learn/courses/30/lessons/17679

백준의 Puyo Puyo문제나 SWEA의 벽돌 깨기 문제와 비슷한 문제다.

이 문제에서는 네 칸만 확인해주면 되므로 모든 (i, j) 칸이 바로 오른쪽(j+1, i), 바로 아래쪽(i+1, j), 대각선 아래(i+1, j+1)와 같은지 확인해주면 된다. 이때 범위를 넘어가지 않도록 i는 m-1보다 작을 때까지, j는 n-1보다 작을 때까지만 검사한다. 그리고 지워진 칸에 대해서는 검사하지 않는다.

네 칸이 모두 같을 때, 해당 칸이 이미 다른 칸으로부터 지워질 수도 있기 때문에 바로 answer값을 증가시키지 않는다. 위의 그림에서 라이언 하나가 중복되어 있는 경우다. check배열을 사용하여 false인 경우에만 answer값을 증가시킨고 check배열의 값을 true로 바꿔준다.

모든 칸에 대해서 검사를 하는동안 한 번이라도 지워지는 게 있다면 flag변수가 true값을 갖는다.

검사가 끝난 후에 flag변수가 false값을 가지고 있다면 지워지는 게 없다는 뜻이므로 검사를 종료한다.

true값을 가지고 있다면 지워져야하는 블록들이 있다는 뜻이므로 check배열의 값이 true인 블록들을 빈칸으로 만드어준다.

지워진 블록들이 있다면 이제 떠있는 블록들을 아래로 내려줘야한다.

모든 열에 대해서 각 행들을 밑에서부터 검사해준다. 밑에서부터 빈칸을 찾은 후에 그 빈칸보다 위쪽에 떠있는 블록을 찾아서 해당 빈칸으로 내려주면 된다. ok변수를 사용해서 발견한 빈칸보다 위쪽 칸들이 모두 빈칸일 경우에는 떠있는 블록이 없다는 뜻이므로 다음 열의 검사로 넘어간다.

https://programmers.co.kr/learn/courses/30/lessons/17682

다트 게임은 총 3번의 기회만 있으므로 각 게임에서의 점수를 저장할 int 배열

arr[3]을 만들어서 마지막에 answer에다가 arr배열의 값(arr[0] , arr[1], arr[2])을 모두 더해줬다.

점수의 계산해주기 위해서 dartResult의 문자를 하나하나 아래와 같은 경우로 나눠서 검사했다.

S인 경우 / D인 경우 / T인 경우 / *인 경우 / #인 경우 / 그 외인 경우(숫자)

S인 경우

앞에 나온 점수 그대로이므로 다음 문자를 검사하기 위해 index만 증가시킨다.

D인 경우

점수의 제곱을 해주어야 하므로 현재 점수에 다시 현재 점수를 곱해준 값을 저장하고 다음 문자를 검사하기 위해 index를 증가시킨다.

T인 경우

점수의 세제곱이므로 앞의 점수의 세제곱 해준 값을 점수에 다시 저장하고 index를 증가시킨다.

*인 경우

현재 점수와 바로 이전의 점수를 2배로 만들어주면 되는데

앞의 보너스(S, D, T)에서 index를 증가시켜버렸으므로 index-1번째(현재 점수)와 index-2번째(이전의 점수)의 값에 2를 곱해주면 된다. 이전의 점수에 2를 곱해줄 때는, 현재 점수가 첫 번째 게임인 경우 이전의 점수가 없으므로 index-2가 0보다 크거나 같은지 검사를 해주고 나서 계산해주어야 한다.

(밑의 코드에서 곱하기 연산 대신에 shift연산을 사용하였다. 곱하기 연산을 해줘도 되지만 shift연산이 더 빠르기도 하고 그냥 연습할 겸 사용하였다)

#인 경우

*과 마찬가지로 앞의 보너스에서 index를 증가시켜버렸으므로 index-1번째가 현재 점수이다.

index-1번째 값을 마이너스 값으로 만들어주면 된다.

그 외의 경우는 점수(숫자)인 경우이다.

문자 - '0'을 해줘서 문자를 int형으로 바꿔준다.

여기서 점수의 범위가 0에서 10이므로 10인 경우를 잘 처리해주어야 한다.

1 자릿수인 경우에는 그냥 index번째에 점수를 더해주면 되지만 10인 경우는 1이 먼저 저장되어 있으므로 기존의 값에 10을 곱해주고 0을 다시 더해줘서 10으로 만들어준다.

10이 아닌 경우라도 기존의 값이 0이기 때문에 10을 곱해주고 현재 점수를 더해줘도 상관없다.

dartResult 문자열에 대한 처리가 모두 끝났다면 arr배열에 저장되어 있는 점수들을 모두 answer에 더해준다.

https://programmers.co.kr/learn/courses/30/lessons/17681

이 문제는 비트 마스크를 이용해서 쉽게 풀 수 있다.

전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.

라는 문제의 조건에서 두 지도를 OR 연산한 결과가 전체 지도라는 것을 알 수 있다.

지도 1과 지도 2의 각 행을 OR연산한 후에 1이 있는 곳에는 '#' (벽)을, 0이 있는 곳에는 ' ' (공백)을 문자열에 추가하여 answer벡터에 넣어준다. 1이 있는 곳은 shift연산을 통해서 알아낼 수 있다.

예를 들어 첫 번째 예제에 나와있는 전체 지도의 3번째 줄은 11101이 되는데

(1<<j)  (0<=j, j < n)한 값과 (지도 1과 2의 OR 연산한 결과)를 AND 연산해줬을 때, 0이 아닌 값이 나오면 1이 있다는 뜻이다.

이 예제의 경우

11101 & 10000 = 10000 (0이 아니므로 벽#)

11101 & 01000 = 01000 (0이 아니므로 벽#)

11101 & 00100 = 00100 (0이 아니므로 벽#)

11101 & 00010 = 00000 (0이므로 공백)

11101 & 00001 = 00001 (0이 아니므로 벽#)

위와 같은 결과가 나와서 문자열은 "### #" 이 된다.

이런 식으로 모든 행에 대해서 전체 지도를 구해줄 수 있다.

https://programmers.co.kr/learn/courses/30/lessons/42889

게임의 실패율을 구하고 실패율이 높은 스테이지 번호를 순서대로 출력하는 문제이다.

실패율이 같다면 스테이지 번호가 작은 순으로 출력한다.

실패율은 다음과 같은 식으로 구한다.

실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

나는 먼저 주어지는 stages벡터를 정렬해주었다.

문제에서 주어진 첫 번째 예제(위의 표)를 예로 들어보면 stages를 정렬해줬을 때

1, 2, 2, 2, 3, 3, 4, 6 이 될 것이다.

그러면 스테이지 수만큼 for문을 돌면서 스테이지 번호와 현재 도전 중이 스테이지 번호가 같은 애들 사용자들에 대해서 순차적으로 처리해줄 수 있기 때문이다.

즉, i번째 스테이지 일 때, stages의 값이 i인 사용자들(해당 스테이지에 도전 중인 사용자, 클리어하지 못한 사용자)의 수를 스테이지에 도달한 플레이어 수로 나눠주면 된다. 그리고 현재 스테이지에 도전 중인 사용자들은 다음 스테이지에는 도달하지 못하므로 도전중인 사용자수에서 빼준다. 그리고 실패율을 해당 스테이지의 번호와 함께 벡터에 넣어준다.

여기서 실수할 수 있는 부분은 문제에서 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의한다라는 문제의 조건

을 잘 처리해주어야 한다. i번째 스테이지에 도전 중인 사용자나 클리어한 사용자가 모두 없다면 실패율은 0이 될 것이고 i번 이후의 스테이지들의 실패율도 모두 0이 될 것이다.

각 스테이지의 실패율을 모두 구했으면 정렬해주어야 한다.

실패율은 내림차순으로 그 실패율이 같다면 스테이지 번호를 오름차순으로 정렬해주기 위해서 비교 함수를 따로 구현(comp)하였다.

정렬이 끝났다면 정렬된 벡터의 두 번째 값(스테이지 번호)을 answer 벡터에 추가한다.