알고리즘 과목평가

240129 min max

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    num_lst = list(map(int, input().split()))

    mn = num_lst[0]
    for i in num_lst:
        if i <= mn:
            mn = i

    mx = num_lst[0]
    for j in num_lst:
        if j >= mx:
            mx = j

    result = mx - mn

    print(f'#{tc} {result}')

240129 구간합

T = int(input())

for tc in range(1, T+1):
    N, M = map(int, input().split())  # N: 정수의 개수 / M: 구간의 개수
    num_lst = list(map(int, input().split()))
    sum_lst = []

    for i in range(N-M+1):
        sum_lst.append(sum(num_lst[i:i+M]))

    result = max(sum_lst) - min(sum_lst)

    print(f'#{tc} {result}')

240129 Gravity

T = int(input())

for tc in range(1, T+1):
    N = int(input()) #방의 가로 길이
    box_lst = list(map(int, input().split())) #상자의 길이 정보
    max_v = 0 #최대 낙차

    for i in range(N):
        cnt = 0
        for j in range(i+1, N):
            if box_lst[i] > box_lst[j]:
                cnt += 1

        if max_v < cnt:
            max_v = cnt

    print(f'#{tc} {max_v}')

240130 간단한 소인수분해

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    div_lst = [2, 3, 5, 7, 11]
    cnt_lst = [0] * 5

    for i in range(len(div_lst)):
        while N % div_lst[i] == 0:
            N //= div_lst[i]
            cnt_lst[i] += 1

    print(f'#{tc}', *cnt_lst)

240130 삼성시의 버스노선

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    station = [0] * 5000

    for i in range(N):
        A, B = map(int, input().split())
        for j in range(A, B+1):
            station[j] += 1

    P = int(input())
    result_lst = []

    for _ in range(P):
        num = int(input())
        result_lst.append(station[num])

    print(f'#{tc}', *result_lst)

240130 연속한 1의 개수

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    num = input()

    check = '1'
    cnt = 0

    for _ in num:
        if check in num:
            check += '1'
            cnt += 1

    print(f'#{tc}', cnt)

240130 숫자 카드

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    num = list(map(int, input()))

    cnt_lst = [0] * 10

    for i in num:
        cnt_lst[i] += 1

    idx = []

    mx = cnt_lst[0]
    for i in range(len(cnt_lst)):
        if cnt_lst[i] >= mx:
            mx = cnt_lst[i]
            idx.append(i)

    print(f'#{tc}', max(idx), mx)

240130 전기버스

T = int(input())

for tc in range(1, T+1):
    # K: 한번 충전으로 갈 수 있는 정류장 수
    # N: 0번 정류장에서 N번 정류장까지 이동
    # M: 충전소가 있는 정류장 수
    K, N, M = map(int, input().split())
    charge_station = list(map(int, input().split()))

    current = 0
    cnt = 0

    while current + K < N:
        flag = False
        for i in range(K, 0, -1):
            if current + i in charge_station:
                current += i
                cnt += 1
                flag = True
                break

        if flag == False:
            cnt = 0
            break

    print(f'#{tc}', cnt)

240130 View

T = 10

for tc in range(1, T+1):
    N = int(input())  #건물의 개수
    buildings = list(map(int, input().split()))

    cnt = 0

    for i in range(2, N-2):
        cur_height = buildings[i] #현재 빌딩
        
        #현재 빌딩을 기준으로 양옆 두 칸의 빌딩들 중 가장 높이가 높은 빌딩
        mx_sur_height = max(buildings[i-2], buildings[i-1], buildings[i+1], buildings[i+2])
        
        #현재 빌딩이 양옆 두 칸의 빌딩들 중 가장 높은 빌딩보다 높다면,
        if cur_height > mx_sur_height:
            #그 차이를 cnt에 할당
            cnt += cur_height - mx_sur_height
    
    print(f'#{tc} {cnt}')

240131 Flatten

for test_case in range(1, 11):
    M = int(input())
    boxes = list(map(int, input().split()))

    for _ in range(M):
        boxes.sort()
        
        # 최고점과 최저점의 높이 차가 1 이하라면, 반복을 중지
        if boxes[-1] - boxes[0] <= 1:
            break
        
        boxes[-1] -= 1
        boxes[0] += 1

    print(f'#{test_case} {max(boxes) - min(boxes)}')

240131 어디에 단어가 들어갈 수 있을까

T = int(input())

for tc in range(1, T+1):
    N, K = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]

    result = 0
    for i in range(N):
        row_cnt = 0
        for j in range(N):
            if arr[i][j] == 1:
                row_cnt += 1

            if arr[i][j] == 0 or j == N-1:
                if row_cnt == K:
                    result += 1
                row_cnt = 0

    for i in range(N):
        col_cnt = 0
        for j in range(N):
            if arr[j][i] == 1:
                col_cnt += 1

            if arr[j][i] == 0 or j == N-1:
                if col_cnt == K:
                    result += 1
                col_cnt = 0

    print(f'#{tc}', result)

240131 파리퇴치

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]
    fly = []

    for i in range(N-M+1):
        for j in range(N-M+1):
            result = 0
            for a in range(M):
                for b in range(M):
                    if i + a in range(N) and j + b in range(N):
                        result += arr[i+a][j+b]
            fly.append(result)

    print(f'{tc}', max(fly))

240131 색칠하기

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = [[0] * 10 for _ in range(10)]
    cnt = 0

    for _ in range(N):
        x1, x2, y1, y2, color = map(int, input().split())

        for i in range(x1, y1+1):
            for j in range(x2, y2+1):
                if color == 1:
                    arr[i][j] += color
                if color == 2:
                    arr[i][j] += color

    for i in range(10):
        for j in range(10):
            if arr[i][j] >= 3:
                cnt += 1

    print(f'#{tc}', cnt)

240131 부분집합의 합

# arr = [3, 5, 2, 6]
# N = 4
#
# for i in range(1 << N):
#     for j in range(N):
#         if i & (1 << j):
#             print(arr[j], end=', ')
#     print()
# print()

T = int(input())

for test_case in range(1, T + 1):
    N, K = map(int, input().split())  # [3, 6]
    A = [i for i in range(1, 13)]  # [1, 2, ..., 12]
    cnt = 0

    # 부분 집합 만드는 코드
    # 12개의 요소를 가지고 있는 집합 A에서 부분집합 만들기!
    for i in range(1 << 12):  # 2^12
        # 해당 i의 j번째 비트가 1인지 확인
        subset = []  # 부분집합의 임시 리스트
        for j in range(12):
            if i & (1 << j):
                # 해당 i의 j번째 비트가 1이라면... 부분집합의 요소가 됨
                subset.append(A[j])

        # 부분집합의 요소의 갯수가 N개라면...
        if len(subset) == N:
            # 부분집합의 요소의 합이 K이라면...
            if sum(subset) == K:
                # 카운트를 해준다!
                cnt += 1

    print(f'#{test_case}', cnt)

240131 풍선팡2

T = int(input())

for test_case in range(1, T+1):
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]
    # 현재 - 오 - 아 - 왼 - 위
    di = [0, 0, 1, 0, -1]
    dj = [0, 1, 0, -1, 0]
    cnt = 0
    for i in range(1, N-1):
        for j in range(1, M-1):
            total = 0
            for k in range(5):
                ni = i + di[k]
                nj = j + dj[k]
                total += arr[ni][nj]
            if cnt < total:
                cnt = total
                
    print(f'#{test_case} {cnt}')

240201 Sum

for test_case in range(1, 11):
    input()
    lst = [list(map(int, input().split())) for _ in range(100)]

    sum = [0] * 202
    for i in range(100):
        sum[200] += lst[i][i]  # 대각선1
        sum[201] += lst[i][99 - i]  # 대각선2
        for j in range(100):
            sum[i] += lst[i][j]  # 가로
            sum[i + 100] += lst[j][i]  # 세로

    print(f'#{test_case} {max(sum)}')

240201 달팽이 숫자

T = int(input())

# 오 아 왼 위
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

for tc in range(1, T+1):
    N = int(input())
    arr = [[0]*N for _ in range(N)]

    cnt = 1
    i = 0
    j = 0
    dr = 0

    while True:
        arr[i][j] = cnt

        if cnt == N*N:
            break

        ni = i + dx[dr]
        nj = j + dy[dr]

        if ni < 0 or N <= ni or nj < 0 or N <= nj or arr[ni][nj] != 0:
            dr = (dr + 1) % 4
            continue

        i, j = ni, nj
        cnt += 1

    print(f'#{tc}')
    for i in range(N):
        print(*arr[i])

240201 숫자 배열 회전

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    lst = [list(map(int, input().split())) for _ in range(N)]
 
    lst_90 = [[0]*N for _ in range(N)]
    lst_180 = [[0] * N for _ in range(N)]
    lst_270 = [[0] * N for _ in range(N)]
 
    for i in range(N):
        for j in range(N):
            lst_90[i][j] = lst[N-1-j][i]
 
    for i in range(N):
        for j in range(N):
            lst_180[i][j] = lst_90[N-1-j][i]
 
    for i in range(N):
        for j in range(N):
            lst_270[i][j] = lst_180[N-1-j][i]
 
    print(f'#{test_case} ')
    for i in range(N):
        for x in range(N):
            print(lst_90[i][x], end='')
        print(end=' ')
        for y in range(N):
            print(lst_180[i][y], end='')
        print(end=' ')
        for z in range(N):
            print(lst_270[i][z], end='')
        print()

240201 풍선팡

T = int(input())

for test_case in range(1, T + 1):
    N, M = map(int, input().split())
    arr = []
    arr = [list(map(int, input().split())) for _ in range(N)]

    total_lst = []
    for i in range(N):
        for j in range(M):
            result = arr[i][j]
            for k in range(1, result + 1):
                if i - k >= 0:
                    result += arr[i - k][j]

                if i + k <= N - 1:
                    result += arr[i + k][j]

                if j - k >= 0:
                    result += arr[i][j - k]

                if j + k <= M - 1:
                    result += arr[i][j + k]

                total_lst.append(result)

    print(f'#{test_case}', max(total_lst))

T = int(input())
for test_case in range(1, T + 1):
    N, M = map(int, input().split())

    balloons = [list(map(int, input().split())) for _ in range(N)]
    di = [1, -1, 0, 0]
    dj = [0, 0, 1, -1]

    max_burst = 0
    for i in range(N):
        for j in range(M):
            burst = balloons[i][j]
            for k in range(1, burst + 1):
                for d in range(4):
                    if 0 <= i + k * di[d] <= N - 1 and 0 <= j + k * dj[d] <= M - 1:
                        burst += balloons[i + k * di[d]][j + k * dj[d]]
            max_burst = max(max_burst, burst)

    print(f'#{test_case} {max_burst}')

240201 이진탐색

def binary_search(p, key):
    left = 1
    right = p
    cnt = 0

    while left <= right:
        mid = int((left + right) / 2)
        if mid == key:
            return cnt
        elif key > mid:
            left = mid
            cnt += 1
        else:
            right = mid
            cnt += 1


T = int(input())

for test_case in range(1, T+1):
    P, A, B = map(int, input().split())
    A = binary_search(P, A)
    B = binary_search(P, B)

    if A > B:
        result = 'B'
    elif A < B:
        result = 'A'
    else:
        result = 0

    print(f'#{test_case} {result}')

240201 특별한 정렬

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = list(map(int, input().split()))

    for i in range(N-1):
        mx_nm = i
        if i % 2 == 0:
            for j in range(i+1, N):
                if arr[mx_nm] < arr[j]:
                    mx_nm = j

        else:
            for j in range(i+1, N):
                if arr[mx_nm] > arr[j]:
                    mx_nm = j

        arr[i], arr[mx_nm] = arr[mx_nm], arr[i]
        result = arr[0:10]

    print(f'#{tc}', *result)

240202 Ladder1

for test_case in range(1, 11):
    tc = int(input())
    arr = [list(map(int, input().split())) for _ in range(100)]
    i, j = 99, arr[99].index(2)
    path = [[0] * 100 for _ in range(100)]

    while i != 0:
        path[i][j] = 1
        if j - 1 >= 0 and arr[i][j - 1] and path[i][j - 1] == 0:
            j -= 1
            continue
        elif j + 1 <= 99 and arr[i][j + 1] and path[i][j + 1] == 0:
            j += 1
            continue
        else:
            i -= 1

        result = j

    print(f'#{tc} {result}')

240202 현주의 상자 바꾸기

T = int(input())
for tc in range(1, T + 1):
    N, Q = map(int, input().split())
    cnt_lst = [0 for _ in range(N + 1)]

    for i in range(1, Q + 1):
        L, R = map(int, input().split())
        for j in range(L, R + 1):
            cnt_lst[j] = i

    print(f'#{tc}', *cnt_lst[1:])

240299 풍선 다트 게임

T = int(input())
 
for test_case in range(1, T+1):
    n = int(input()) # 다트 가로세로길이
    dart = [list(map(int, input().split())) for _ in range(n)]
 
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
 
    mx_score = 0   # score 중에 젤 낮을 수 있는 점수 : 0
    for i in range(1, n-1):  # 1~n-2
        for j in range(1, n-1): # 1~1-2
            score = - dart[i][j]  # score에 첨부터 본인자신 빼놓고 시작)
            for delta in range(4):
                score += dart[i+dx[delta]][j+dy[delta]]  # 상하좌우 더하기
            if score < 0:
                score = 0
            elif score % 2 == 0:
                score = score * 2
 
            mx_score = max(mx_score, score)   # 젤 높은점수 mx_score 구하기
 
    print(f'#{test_case} {mx_score}')

T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    p_lst = [list(map(int, input().split())) for _ in range(N)]
    result_lst = []

    for i in range(1, N - 1):
        for j in range(1, N - 1):
            current = p_lst[i][j]
            current = p_lst[i - 1][j] + p_lst[i + 1][j] + p_lst[i][j - 1] + p_lst[i][j + 1] - p_lst[i][j]

            if current % 2 == 0:
                current *= 2

            if current < 0:
                current = 0

            result_lst.append(current)

    print(f'#{tc}', max(result_lst))

240299 완전 탐색 연습

1. 완전탐색에 대해 아는대로 서술하시오. (단, 장단점을 반드시 포함할 것)
   완전탐색이란, 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 방식이다.
   장점: 해답을 찾지 못할 확률이 적다. 알고리즘이 단순하여 구현이 쉽다. 배열이나 연결리스트 등 순차구조의 자료구조에서 원하는 항목을 찾을 때 유용하다.
   단점: 수행속도가 느리다.

2. 완전탐색의 방법으로 베이비진 문제를 푸는 방법을 서술하시오.
   6개의 숫자로 만들 수 있는 모든 숫자를 나열한다. (중복 포함)
   앞의 3자리와 뒤의 3자리를 잘라, run와 triplet 여부를 테스트하고 최종적으로 베이비진 여부를 판단한다.