JH 개발 블로그

def make_u_v(s):
    cnt1 = cnt2 = 0
    for i in s:
        if i == '(':
            cnt1 += 1
        else:
            cnt2 += 1
        if cnt1 == cnt2: break
    return s[:cnt1 + cnt2], s[cnt1 + cnt2:]

def is_right(s):
    cnt1 = cnt2 = 0
    for i in s:
        if i == '(':
            cnt1 += 1
        else:
            cnt2 += 1
        if cnt2 > cnt1: return False
    return True

def solution(p):
    if p == '':
        return p
    answer = ''
    u, v = make_u_v(p)
    if is_right(u):
        answer += u
        answer += solution(v)
    else:
        answer += '(' + solution(v) + ')' + ''.join(')' if x == '(' else '(' for x in u[1:-1])
    return answer

u를 뒤집은거와 u[::-1]이 같을거라고 생각해버리는 오류를 범했다..

문제에서 구현 하라는대로만 구현 하면 되는 문제였다.

def solution(s):
    answer = len(s)
    for step in range(1,len(s)//2+1):
        temp = [s[i:i+step] for i in range(0,len(s),step)]
        ans = 0
        cnt = 0
        for i in range(len(temp)-1):
            cnt += 1
            if temp[i] == temp[i+1]:
                continue
            else:
                ans += len(temp[i]) + (len(str(cnt)) if cnt > 1 else 0)
                cnt = 0
        cnt += 1
        ans += len(temp[-1]) + (len(str(cnt)) if cnt > 1 else 0)
        answer = min(answer,ans)
    return answer

dir = ((-1,0),(0,1),(1,0),(0,-1))

def A_turn(ar,ac,br,bc,cnt,board):
    if board[ar][ac] == 0:
        return (1,cnt)
    winner = []
    loser = []
    flag = False
    for dr,dc in dir:
        nr,nc = ar+dr,ac+dc
        if 0<=nr<len(board) and 0<=nc<len(board[0]) and board[nr][nc] == 1:
            flag = True
            temp = [row[:] for row in board]
            temp[ar][ac] = 0
            iswin,turn = B_turn(br,bc,nr,nc,cnt+1,temp)
            if iswin:
                winner.append(turn)
            else:
                loser.append(turn)
    if flag:
        if winner:
            return (0,min(winner))
        else:
            return (1,max(loser))
    else:
        return (1,cnt)


def B_turn(br,bc,ar,ac,cnt,board):
    if board[br][bc] == 0:
        return (1,cnt)
    winner = []
    loser = []
    flag = False
    for dr,dc in dir:
        nr,nc = br+dr,bc+dc
        if 0<=nr<len(board) and 0<=nc<len(board[0]) and board[nr][nc] == 1:
            flag = True
            temp = [row[:] for row in board]
            temp[br][bc] = 0
            iswin,turn = A_turn(ar,ac,nr,nc,cnt+1,temp)
            if iswin:
                winner.append(turn)
            else:
                loser.append(turn)
    if flag:
        if winner:
            return (0,min(winner))
        else:
            return (1,max(loser))
    else:
        return (1,cnt)


def solution(board, aloc, bloc):
    ar,ac,br,bc = aloc[0],aloc[1],bloc[0],bloc[1]
    answer = A_turn(ar,ac,br,bc,0,board)[1]
    return answer

미니맥스트리란 1:1 게임에서 쓰일 수 있는 알고리즘이다. 나와 상대방은 항상 최선을 다하기 때문에, 실수하지 않고 매번 최선의 방법만 택한다. 따라서 내가 고른 최선은 상대방에겐 최악이 되고 상대방이 고른 최선은 나에겐 최악이 된다.

이 문제에서는 이기는 사람은 최단경로로 이기려 하고, 지는 사람은 최대경로로 지려고 한다.

따라서 재귀를 돌때 만약 이길 수 있다면, 최단경로를 리턴해주고 만약 진다면 최대경로를 리턴해준다.

def solution(board, skill):
    R,C = len(board),len(board[0])
    imos = [[0]*(R+1) for _ in range(C+1)]
    for type,r1,c1,r2,c2,degree in skill:
        if type == 1:
            imos[r1][c1] -= degree
            imos[r1][c2+1] += degree
            imos[r2+1][c1] += degree
            imos[r2+1][c2+1] -= degree
        if type == 2:
            imos[r1][c1] += degree
            imos[r1][c2+1] -= degree
            imos[r2+1][c1] -= degree
            imos[r2+1][c2+1] += degree

    for i in range(len(imos)):
        for j in range(1,len(imos[0])):
            imos[i][j] += imos[i][j-1]

    for i in range(len(imos[0])):
        for j in range(1,len(imos)):
            imos[j][i] += imos[j-1][i]

    answer = 0

    for i in range(R):
        for j in range(C):
            board[i][j] += imos[i][j]
            if board[i][j] > 0:
                answer += 1

    return answer

imos 알고리즘을 이용한 풀이

imos 알고리즘 자체를 몰랐다. 일차원 누적합을 구하는 방법은 알고 있었지만, 이러한 알고리즘이 있는건 몰랐다.

imos는 누적합을 일차원뿐만 아니라 차원을 확장해서 풀 수 있다. 

2021 카카오 광고삽입 문제에서는 일차원 누적합을 한번 더 누적합을 만들어서 문제를 풀었다.

이 문제는 imos 알고리즘을 이용해서 이차원 누적합을 쉽게 구해서 풀 수 있었다.

가로로 휩쓴 후 세로로 휩쓴다.

from collections import deque

def solution(info, edges):
    tree = [[] for _ in range(len(info))]
    for a,b in edges:
        tree[a].append(b)
    q = deque([(1,0,tuple([1]+[0]*(len(info)-1)))])
    visited = set()

    while q:
        s,w,visit = q.popleft()
        if s == w:
            continue
        if (s,w,visit) in visited:
            continue
        visited.add((s,w,visit))

        for i in range(len(info)):
            if visit[i] == 1:
                for j in tree[i]:
                    if not visit[j]:
                        temp = list(visit)
                        temp[j] = 1
                        if info[j] == 0:
                            q.append((s+1,w,tuple(temp)))
                        else:
                            q.append((s,w+1,tuple(temp)))
    return max(visited)[0]

이 문제에서 트리는 이동한 경로를 다시 되돌아가 방문하지 않은 곳을 방문할 수 있습니다.

따라서 현재 양, 늑대의 수, 방문한 경로를 visited에 저장합니다.

현재 방문한 노드들에서 이동가능한 방문하지 않은 노드가 있다면, 이동합니다. 

def dfs(n, info, k, apeach, lion, temp):
    if n == 0:
        global max_val, answer
        if lion - apeach > max_val:
            max_val = lion - apeach
            answer = temp[:]

        elif lion - apeach == max_val and max_val != 0:
            for i in range(10, -1, -1):
                if temp[i] > answer[i]:
                    answer = temp[:]
                    break
                elif temp[i] < answer[i]:
                    break
        return

    for i in range(k, 11):
        if n > info[i]:
            temp[i] = info[i] + 1
            if info[i] > 0:
                dfs(n - temp[i], info, i + 1, apeach - (10 - i), lion + (10 - i), temp)
            else:
                dfs(n - temp[i], info, i + 1, apeach, lion + (10 - i), temp)
            temp[i] = 0
        else:
            if i == 10:
                temp[i] = n
                dfs(0, info, i + 1, apeach, lion, temp)
                temp[i] = 0
            else:
                dfs(n, info, i + 1, apeach, lion, temp)


def solution(n, info):
    global max_val, answer
    apeach = 0; answer = [0] * 11; max_val = 0
    for i in range(11):
        if info[i] > 0:
            apeach += 10 - i
    dfs(n, info, 0, apeach, 0, [0] * 11)
    if answer == [0] * 11:
        answer = [-1]
    return answer

dfs로 풀었습니다.

k점 과녁에 어피치와 같거나, 더 적게 맞히면 점수를 얻을 수 없습니다.

따라서 어피치보다 한발 더 쏘거나, 아예 맞히질 말아서 화살을 아껴야 합니다.

남은 화살의 개수가 0이 되면 라이언과 어피치의 점수 차이를 구합니다. 이때 기존값보다 점수 차이가 크다면, 새롭게 값을 갱신해줍니다. 만약 기존값과 같다면, 가장 낮은 점수를 더 많이 맞힌 경우로 갱신합니다.