배열 B의 값 - BOJ

배열 B의 값 - BOJ

문제 예시의 4X4 배열을 예시로 든다면
0, 1, 2, 3행에서 1,2 행을 바꿔도 최대값이 바뀌지 않을 것임.
따라서 (중간 행 중에서 최소값)과 (0행 or 마지막 행) 중에 행을 하나 교환하거나
열에서도 똑같은 작업을 해서 최대값을 구하면 된다.

def calculate(board):
    _sum = 0
    for i in range(N - 1):
        for j in range(M - 1):
            _sum += board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i][j + 1]
    return _sum

def newmap(x, y, rc): # rc -> r인지 c인지
    b = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            b[i][j] = a[i][j]
    if rc:
        for c in range(M):
            b[x][c], b[y][c] = a[y][c], a[x][c]
    else:
        for r in range(N):
            b[r][x], b[r][y] = a[r][y], a[r][x]
    return b

N, M = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
row = [0] * N
col = [0] * M
r_min = float('inf')
c_min = float('inf')
min_col, min_row = -1, -1

ret = calculate(a)

# 각 행열 합 계산
for i in range(N):
    for j in range(M):
        row[i] += a[i][j]
        col[j] += a[i][j]

# 최소 크기 행
for r in range(1, N - 1):
    tr = row[r] * 4
    tr -= 2 * (a[r][0] + a[r][M - 1])
    if r_min > tr:
        r_min = tr
        min_row = r

# 최소 크기 열
for c in range(1, M - 1):
    tc = col[c] * 4
    tc -= 2 * (a[0][c] + a[N - 1][c])
    if c_min > tc:
        c_min = tc
        min_col = c

if min_row > 0:
    new = newmap(0, min_row, 1)
    ret = max(ret, calculate(new))
    new = newmap(N - 1, min_row, 1)
    ret = max(ret, calculate(new))

if min_col > 0:
    new = newmap(0, min_col, 0)
    ret = max(ret, calculate(new))
    new = newmap(M - 1, min_col, 0)
    ret = max(ret, calculate(new))

print(ret)

Two Dots - BOJ

Two Dots - BOJ

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def dfs(x, y, cnt):
    global tx, ty, flag
    if flag: return
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= N or ny >= M or a[nx][ny] != a[tx][ty]: # 범위 벗어나지 않고, 색깔이 같을 때만 하도록
            continue
        if not visit[nx][ny]:
            visit[nx][ny] = True # 방문처리 했다가
            dfs(nx, ny, cnt + 1)
            visit[nx][ny] = False # 안한 걸로
        else:
            if cnt >= 4 and tx == nx and ty == ny: # 4번 이상이고 위치가 같을 때 -> 사이클
                flag = True
                return

N, M = map(int, input().split())
a = [list(input()) for _ in range(N)]
visit = [[False] * M for _ in range(N)]
flag = False

for i in range(N):
    for j in range(M):
        if not visit[i][j]:
            tx, ty = i, j
            visit[i][j] = True
            dfs(i, j, 1)
        if flag:
            print("Yes")
            exit(0)

print("No")

적록색약 - BOJ

적록색약 - BOJ

from collections import deque
from copy import deepcopy

dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

def a_bfs(i, j):
    cnt = 0
    q1 = deque()
    q1.append((i, j))
    a_visit[i][j] = True
    while q1:
        x, y = q1.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or ny < 0 or nx >= N  or ny >= N or a_visit[nx][ny]:
                continue
            if a[nx][ny] == a[i][j]:
                a_visit[nx][ny] = True
                q1.append((nx, ny))


def b_bfs(i, j):
    cnt = 0
    q2 = deque()
    q2.append((i, j))
    b_visit[i][j] = True
    while q2:
        x, y = q2.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or ny < 0 or nx >= N or ny >= N or b_visit[nx][ny]:
                continue
            if b[nx][ny] == b[i][j]:
                b_visit[nx][ny] = True
                q2.append((nx, ny))


N = int(input())
a = [list(input()) for _ in range(N)]
b = deepcopy(a)
for i in range(N):
    for j in range(N):
        if b[i][j] == 'G':
            b[i][j] = 'R'

a_visit = [[False] * N for _ in range(N)]
b_visit = [[False] * N for _ in range(N)]

a_cnt = 0
b_cnt = 0

for i in range(N):
    for j in range(N):
        if not a_visit[i][j]:
            a_bfs(i, j)
            a_cnt += 1
        if not b_visit[i][j]:
            b_bfs(i, j)
            b_cnt += 1

print(a_cnt, b_cnt)

최대상금 - SWEA

최대상금 - SWEA

문제

퀴즈 대회에 참가해서 우승을 하게 되면 보너스 상금을 획득할 수 있는 기회를 부여받는다.

우승자는 주어진 숫자판들 중에 두 개를 선택에서 정해진 횟수만큼 서로의 자리를 위치를 교환할 수 있다.

예를 들어, 다음 그림과 3, 2, 8, 8, 8 의 5개의 숫자판들이 주어지고 교환 횟수는 2회라고 하자.

처음에는 첫번째 숫자판의 3과 네 번째 숫자판의 8을 교환해서 8, 2, 8, 3, 8이 되었다.

다음으로, 두 번째 숫자판 2와 마지막에 있는 8을 교환해서 8, 8, 8, 3, 2이 되었다.

정해진 횟수만큼 교환이 끝나면 숫자판의 위치에 부여된 가중치에 의해 상금이 계산된다.

숫자판의 오른쪽 끝에서부터 1원이고 왼쪽으로 한자리씩 갈수록 10의 배수만큼 커진다.

위의 예에서와 같이 최종적으로 숫자판들이 8,8,8,3,2의 순서가 되면 88832원의 보너스 상금을 획득한다.

여기서 주의할 것은 반드시 횟수만큼 교환이 이루어져야 하고 동일한 위치의 교환이 중복되어도 된다.

다음과 같은 경우 1회의 교환 횟수가 주어졌을 때 반드시 1회 교환을 수행하므로 결과값은 49가 된다.

94의 경우 2회 교환하게 되면 원래의 94가 된다.

정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 계산해보자.

[입력]

가장 첫 줄은 전체 테스트 케이스의 수이다.

최대 20개의 테스트 케이스가 표준 입력을 통하여 주어진다.

각 테스트 케이스에는 숫자판의 정보와 교환 횟수가 주어진다.

숫자판의 정보는 정수형 숫자로 주어지고 최대 자릿수는 6자리이며, 최대 교환 횟수는 10번이다.

[출력]

각 테스트 케이스마다, 첫 줄에는 “#C”를 출력해야 하는데 C는 케이스 번호이다.

같은 줄에 빈 칸을 하나 사이에 두고 교환 후 받을 수 있는 가장 큰 금액을 출력한다.

풀이

• dfs를 이용해서 모든 경우의 수를 비교하였다.
• 64321 1 의 테스트케이스 경우와 같이 계속 감소하는 값이 input으로 들어올 경우
  잘못된 값이 출력되는 경우가 있어, 해당 경우에 nums[-2]의 값과 nums[-1]의 값을 계속 swap해주는 로직을 추가해주었다.

def dfs(d, cnt):
    global ret
    if cnt == n:
        ret = max(int("".join(nums)), ret)
        return
    for i in range(d, l):
        for j in range(i + 1 , l):
            if nums[i] <= nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
                dfs(i, cnt + 1)
                nums[i], nums[j] = nums[j], nums[i]

T = int(input())

for test_case in range(1, T + 1):
    nums, n = input().split()
    nums = list(nums)
    numbers = nums[:]
    n = int(n)
    l = len(nums)
    ret = 0
    flag = 0
    if len(nums) == 2 or nums == sorted(nums, reverse=True):
        cnt = 0
        while cnt != n:
            numbers[-1], numbers[-2] = numbers[-2], numbers[-1]
            cnt += 1
        flag = int("".join(numbers))
    cnt = 0
    dfs(0, cnt)
    if ret == 0:
        ret = flag
    print("#" + str(test_case) + " " + str(ret))

https://nuatmochoi.github.io/algopress/

위 주소의 깃 블로그에 알고리즘 풀이 작성하고 있습니다!

1. 예증법 : 특정한 사례들을 나열한 뒤 그 안에서 일반적인 규칙을 찾는다.

2. 패턴 매칭 : 풀어야 할 알고리즘과 비슷한 문제를 생각해내고 비슷한 문제의 풀이법을 수정하여 풀어야 할 알고리즘을 만들어낸다.

3. 단순화와 일반화 : 문제를 단순화하여 푼 뒤, 알고리즘이 구해지면 일반화

4. 초기 사례로부터의 확장 : n=1, n=2, n=3,... 식으로 확장하여 규칙을 찾아낸다. 보통 재귀 알고리즘으로 구현된다.

5. 자료구조 브레인스토밍 : 자료구조들을 차례차례 적용해보고 해결되는지 본다.