그냥 코딩하는 사람의 블로그

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

풀이 과정

1. 시작점, 대포 위치, 도착점을 노드로 잡고 걸리는 시간을 행렬로 구해준다.
   • 시작점 -> 0, 대포들 -> (1 ~ N) 도착점 -> N+1
   • [i][j] => 노드 i에서 노드 j까지의 최소 시간
   • 시작점부터 각 노드의 걸리는 시간을 구하는 경우, 대포를 사용할수 없으며 달려가는 케이스밖에 없으므로 [0][j]는 시작점 ~ 도착점 거리를 구한 다음 5로 나누어주면 된다.
   • 이외의 경우에서는 대포를 사용할 수 있으므로
     1. 달려가는 케이스(거리 / 5)
     2. 거리가 50 초과일 때 대포 + 앞으로 달려가기 (2 + (거리-50)/5)
     3. 거리가 50 미만일 때 대포 + 뒤로 달려가기 (2 + (50-거리)/5)
     4. 거리가 50일 때 2
   • 위 네가지 케이스들을 맞추어서 최솟값을 구해서 행렬을 채워주면 된다.
2. 시작점을 0으로 두고, 다익스트라 알고리즘을 사용한다.
   • 현재 최소 거리인 노드를 잡고, 이동 가능한 모든 노드를 이동해 보면서, 거리를 갱신하는 경우 거리 갱신 및 최소 히프에 거리 저장
   • 따라서, 최소 히프를 사용하면 좀 더 빠르게 구현 가능하다.
3. N+1 노드까지의 최소 거리를 출력한다.

일반 다익스트라 알고리즘보다 어려운거 같은데 정답률은 높음.. 뭐지..?

소스 코드

import sys
import heapq
import math

input = lambda : sys.stdin.readline().rstrip()

def calculate_distance(src, dest):
    return math.sqrt((src[0]-dest[0]) ** 2 + (src[1]-dest[1]) ** 2)

myX, myY = map(float, input().split())
targetX, targetY = map(float, input().split())
N = int(input())

points = [list(map(float, input().split())) for _ in range(N)]
points = [[myX, myY]] + points + [[targetX, targetY]]

time_matrix = [[0] * (N+2) for _ in range(N+2)]

for i in range(len(points)):
    for j in range(i+1, len(points)):
        if i == 0:
            time_matrix[i][j] = calculate_distance(points[i], points[j]) / 5
        else:
            distance = calculate_distance(points[i], points[j])
            time_matrix[i][j] = distance / 5
            if distance > 50.0:
                time_matrix[i][j] = min(time_matrix[i][j],
                                        2 + (distance-50) / 5)
            elif distance == 50.0:
                time_matrix[i][j] = 2.0
            else:
                time_matrix[i][j] = min(time_matrix[i][j],
                                        2 + (50-distance) / 5)
        time_matrix[j][i] = time_matrix[i][j]
        
INT_MAX = int(10e9)
distance = [INT_MAX] * (N+2)
distance[0] = 0
heap = [[0, 0]]

while heap:
    time, next_node = heapq.heappop(heap)
    if distance[next_node] != time:
        continue

    for i in range(len(points)):
        if next_node == i:
            continue
        if distance[i] > time + time_matrix[i][next_node]:
            distance[i] = time + time_matrix[i][next_node]
            heapq.heappush(heap, [distance[i], i])

print("%.6f"%(distance[N+1]))

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

풀이 과정

1. Union-find 알고리즘을 응용하는 문제이다.
   • find(i)가 의미하는게 게이트 번호가 i일 때 넣을 게이트의 다음 위치라고 보면 된다.
2. 입력받은 게이트의 부모 노드를 찾고(find), 부모노드와 부모노드 - 1 노드를 union 해준다.
   • 부모 노드에는 비행기를 넣었으므로 다음 위치는 (부모노드-1)의 부모노드이기 때문이다.
   • 이 때, Union 연산을 할 때, i 이하의 게이트를 찾아야 하므로 두 점 중에서 큰 번호의 부모를 수정해야 한다.
3. 부모 노드를 찾았을 때, 부모 노드가 0이라면 어느 게이트에도 도킹할 수 없는 것이므로 루프를 중지한다.
4. 결괏값을 출력시켜 준다.

소스 코드

import sys

input = sys.stdin.readline

sys.setrecursionlimit(10**5)

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 < p2:
        parent[p2] = p1
    else:
        parent[p1] = p2

G = int(input().rstrip())
P = int(input().rstrip())
parent = [i for i in range(G+1)]
answer = 0

for i in range(P):
    ap = int(input().rstrip())
    where = find(parent, ap)
    if where == 0:
        break
    union(parent, where, where-1)
    answer += 1

print(answer)

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

풀이 과정

1. 최소 생명력을 1, 최대 생명력을 넉넉하게 10^16정도 잡아두고 최소를 찾는 것이므로 크다고 문제가 되는건 아니니까 이진 탐색을 진행한다. 
2. 범위의 중간값을 기준으로, 던전을 끝까지 클리어할 수 있는지 시뮬레이션 해본다.
   1. 몬스터인 경우, 몬스터의 체력 // 현재 공격력만큼 전투를 해야 한다.
   2. 따라서 몬스터의 공격력 x (몬스터의 체력 // 현재 공격력) 만큼 현재 hp에서 빼주면 된다. 단, 이 때 나누어 떨어지는 경우는 전투가 딱 맞춰서 끝나는 경우이므로 몬스터의 공격력 x (몬스터의 체력 // 현재 공격력 - 1)을 빼준다.
   3. 포션인 경우는 공격력은 그냥 올려주고, 체력의 경우 최대 체력까지만 올라갈 수 있도록 처리해 준다.
3. 던전의 끝까지 클리어할 수 있다면 최대 체력의 최솟값을 구해야 하므로 정답 저장 후 왼쪽 구간을 진행하고, 클리어할수 없다면 최대 체력을 올려야 하므로 오른쪽 구간을 진행한다.
4. 정답을 출력한다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()

N, Hatk = map(int, input().split())

dungeons = [list(map(int, input().split())) for _ in range(N)]

left = 1
right = int(10e16)
answer = 0
while left <= right:
    mid = (left + right) // 2
    current_HP = mid
    current_ATK = Hatk
    status = True
    for dungeon in dungeons:
        t, a, h = dungeon
        if t == 1:
            step = h // current_ATK
            if h % current_ATK == 0:
                step -= 1
            current_HP -= a * step
            if current_HP <= 0:
                status = False
                break
        elif t == 2:
            current_HP = min(current_HP+h, mid)
            current_ATK = current_ATK + a
        
    if status:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

print(answer)

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

풀이 과정

1. 입력받은 우주신들의 좌표를 사용하여 서로 다른 우주신들 사이의 거리를 모두 구해서 최소히프에 넣어준다.
   • (1->2, 1->3, ..., N-1->N)
   • 최소 히프에는 거리 기준으로 최소 히프에 넣을거기 때문에 (거리, 시작점, 끝점) 순으로 넣어준다. 
2. 미리 연결된 우주신들에 대해서는 Union 연산을 미리 해준다.
3. 이후 히프에서 하나씩 꺼내면서 연결된 점이 같은 집합에 속해있는지 검사한다.(find) 속해있지 않다면 해당 간선을 사용해야 하므로 union 연산을 해주고, 거리는 따로 더해둔다.
4. 따로 더해둔 거리를 출력시켜 준다.

같은 kruskal 알고리즘을 사용하더라도 응용해야 되는 문제들이 풀기가 좀 어렵다. 이번 문제에서는 간선 정보가 주어지지 않고, 푸는 사람이 직접 만들어야 했기 때문에 더 그랬던 것 같음.

소스 코드

import sys
import heapq
import math

input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())

def union(parent, a, b):
    pa = find(parent, a)
    pb = find(parent, b)

    if parent[pa] != parent[pb]:
        parent[pa] = parent[pb]

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])

    return parent[a]

pos = [[0, 0]]

parent = [i for i in range(N+1)]

for _ in range(1, N+1):
    x, y = map(int, input().split())
    pos.append([x, y])

for _ in range(M):
    a, b = map(int, input().split())
    if find(parent, a) != find(parent, b):
        union(parent, a, b)

heap = []

for i in range(1, N+1):
    for j in range(1, i):
        distance = math.sqrt((pos[i][0] - pos[j][0]) ** 2 + (pos[i][1] - pos[j][1]) ** 2)
        heapq.heappush(heap, [distance, i, j])

answer = 0
while heap:
    dist, i, j = heapq.heappop(heap)
    if find(parent, i) != find(parent, j):
        answer += dist
        union(parent, i, j)
    else:
        continue

print("%.2f"%answer)

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

풀이 과정

1. 1차원 DP로도 풀 수 있겠지만, 2차원 DP로 풀이하는 편이 훨씬 직관적이고 보기 편하다.
2. DP[i][j]를 j개의 숫자를 써서 i를 만드는 경우의 수라고 할 때,
   1. DP[i][j]의 값은 DP[i][j-1]~DP[0][j-1]의 합과 같다.
   2. DP[i][j-1]의 케이스에서 숫자 0을 사이사이에 더해주면 되고, 비슷하게 DP[i-1][j-1]의 경우는 숫자 1, ... 숫자 i를 더해줄 때는 DP[0][j-1]이므로 (1)과 같다.
   3. DP[i][j]를 구하고 나서 나머지 연산을 같이 해주어야 속도가 빨라진다.
3. DP[N][M]을 출력시켜준다.

DP 점화식 고민할 때 너무 문제를 크게 잡고 고민하지 말고 작게 고민해야 함.. ㅜㅜ

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
dp = [[0] * (M+1) for i in range(N+1)]

for i in range(M+1):
    dp[0][i] = 1

for i in range(1, N+1):
    for j in range(1, M+1):
        for k in range(0, i+1):
            dp[i][j] += dp[k][j-1]
        dp[i][j] = dp[i][j] % 1000000000

print(dp[N][M])

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

풀이 과정

1. 던전의 수가 최대 8개까지밖에 없으므로 모든 조합을 다 해보는게 제일 쉬울것이라 판단
2. 배열의 인덱스가 2까지 있다고 하면 가능한 케이스는
   1. (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)
   2. 위 케이스를 하나씩 해보면서 탐험 가능한 최대 던전 수를 갱신하는 방식으로 풀이를 진행하면 된다.
   3. 초기 피로도를 k로 잡고, 현재 던전의 최소 필요 피로도보다 현재 피로도가 클 때, 던전의 수를 하나 늘리고 현재 피로도에서 현재 던전의 소모 피로도를 빼주는 방식으로 진행한다. 물론 최소 필요 피로도가 더 크다면 생략
3. recursion으로 구현하여도 되지만, 파이썬의 permutations 함수를 사용하는것이 가장 간편하다고 생각됨.

소스 코드

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    total_index = [i for i in range(len(dungeons))]
    total_case = list(permutations(total_index, len(dungeons)))
    
    for each_case in total_case:
        fatigue = k
        dungeon_count = 0
        
        for dungeon_idx in each_case:
            if fatigue >= dungeons[dungeon_idx][0]:
                dungeon_count += 1
                fatigue -= dungeons[dungeon_idx][1]
        
        answer = max(answer, dungeon_count)
    
    return answer

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

풀이 과정

1. 왼쪽 구간을 왼쪽에서 오른쪽으로 진행하면서 최대 높이가 되기 전까지 높이가 높아질때마다 스택에 넣어준다.
   • 구간을 구해주어야 하므로, 스택의 맨 마지막에는 최대 높이가 될 때의 지점도 저장해 준다.
2. 오른쪽 구간을 오른쪽에서 왼쪽으로 진행하면서 최대 높이가 되기 전까지 높이가 높아질때마다 스택에 넣어준다.
   
   • 구간을 구해주어야 하므로, 스택의 맨 마지막에는 최대 높이가 될 때의 지점도 저장해 준다.
3. (1)번과 (2)번 스택을 활용하여 왼쪽 구간과 오른쪽 구간의 넓이를 구해준다.
4. 마지막으로, 최대 높이 구간 넓이를 구해서 더해준다.
   1. 왼쪽 -> 오른쪽으로 찾았을때의 최대 높이가 되는 지점
   2. 오른쪽 -> 왼쪽으로 찾았을 때의 최대 높이가 되는 지점
   3. (2)에서 (1)을 빼준 값에 1을 더한 값이 최대 높이에서의 구간 합이다.

소스 코드

import sys
from bisect import bisect_left, bisect_right

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
block = []

for _ in range(N):
    L, H = map(int, input().split())
    block.append([L, H])

def rfind(arr, a):
    for i in range(len(arr)-1, -1, -1):
        if arr[i] == a:
            return i
    return -1

def lfind(arr, a):
    for i in range(len(arr)):
        if arr[i] == a:
            return i
    return -1

block.sort(key=lambda x:x[0])
block_value = list(map(lambda x:x[1], block))
max_block_value = max(block_value)
left = []
right = []
p = 0

# 왼쪽 구간 저장
while p < len(block) and block[p][1] != max_block_value:
    if not left:
        left.append(block[p])
    elif left and left[-1][1] <= block[p][1]:
        left.append(block[p])
    p += 1
    
left.append(block[p])

# 오른쪽 구간 저장
p = len(block)-1
while p >= 0 and block[p][1] != max_block_value:
    if not right:
        right.append(block[p])
    elif right and right[-1][1] <= block[p][1]:
        right.append(block[p])
    p -= 1

right.append(block[p])
right.sort(key = lambda x:x[0])

area = 0
# 왼쪽 구간 너비 합
for i in range(1, len(left)):
    area += left[i-1][1] * (left[i][0] - left[i-1][0])

# 오른쪽 구간 너비 합
for i in range(1, len(right)):
    area += right[i][1] * (right[i][0] - right[i-1][0])

# 높이가 가장 큰 부분의 너비 합
lindex = lfind(block_value, max_block_value)
rindex = rfind(block_value, max_block_value)
area += max_block_value * (block[rindex][0] - block[lindex][0] + 1)

print(area)

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

풀이 과정

1. 입력받은 문자열을 왼쪽에서 오른쪽으로 하나의 문자씩 진행한다.
2. 문자의 개수를 카운팅하다가 문자의 개수가 0이 아닌 3의 배수가 된다면, 다음에 나와야 하는 문자는 해당 문자가 되어야 한다.
3. 따라서, 따로 플래그를 두어 개수가 3의 배수가 될 때의 문자를 저장해 두고, 바로 다음 문자가 해당 문자인지 체크하면 된다.
4. 맨 마지막이 3의 배수가 딱 될때의 케이스는 따로 빼서 처리해 준다.
5. 경우에 따라 OK, FAKE 출력

소스 코드

import sys
from collections import defaultdict

input = lambda: sys.stdin.readline().rstrip()
n = int(input())
for i in range(n):
    M = input()
    counter = defaultdict(lambda: 0)

    check = True
    next_flg = False
    next_chr = ''
    for ch in M:
        if not check:
            break
        if next_flg:
            if ch != next_chr:
                check = False
            next_flg = False
            continue
        counter[ch] += 1
        if counter[ch] % 3 == 0:
            next_flg = True
            next_chr = ch
    # 다음에 문자가 하나 더 나와야 하는 경우
    if next_flg:
        check = False
    
    if check:
        print("OK")
    else:
        print("FAKE")

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

풀이 과정

1. 다른때와 다르게, 최단 경로를 저장하는 distance를 2차원 배열로 지정해주어야 해서 특이한 경험이었음.
2. [0, 0]에서 시작하여 현재 이동할 수 있는 좌표 중 가장 최소로 벽을 부수어야 하는 좌표로 먼저 이동하여 갱신한다.
   • 상,하,좌,우로 이동하면서 거리 갱신이 가능한 경우 최소 히프에 넣어주는 방식으로 구현
   • 벽이 있는 경우는 1을 더해주고, 벽이 없는 경우는 0을 더해주는데, 그냥 입력 배열에 저장되어있는 값을 더해준다.
3. 마지막에, distance[N-1][M-1]을 출력해준다.
4. 원래 이런 문제는 BFS로만 풀었었는데 다익스트라 알고리즘으로도 풀리네..  BFS로 풀면 중복이 훨씬 많이 일어나서 비효율적이긴 할듯.

소스 코드

import sys
import heapq

input = lambda: sys.stdin.readline().rstrip()

M, N = map(int, input().split())

matrix = [list(map(int, list(input()))) for _ in range(N)]
distance = [[int(10e9)] * M for _ in range(N)]
distance[0][0] = 0

heap = []
heapq.heappush(heap, [0, 0, 0])

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

while heap:
    dist, x, y = heapq.heappop(heap)
    if distance[x][y] != dist:
        continue

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx and nx < N and 0 <= ny and ny < M:
            if distance[nx][ny] > dist + matrix[nx][ny]:
                distance[nx][ny] = dist + matrix[nx][ny]
                heapq.heappush(heap, [distance[nx][ny], nx, ny])


print(distance[N-1][M-1])

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

풀이 과정

1. 처음엔 그냥 무턱대고 BFS로 풀이를 진행하였으나.. 큐에 데이터가 너무 많이 들어가게 되서 그런지 메모리 초과가 계속해서 발생하였다ㅜㅜ
2. 그래서 BFS처럼 큐에 데이터가 가득 쌓이지는 않으니까 DFS로 풀이를 바꾸어서 진행하였다.
   1. 현재 위치에서 동,서,남,북으로 다음 위치로 이동할 때, 다음 위치에 있는 말이 이전까지 방문한 알파벳에 포함되어있지 않다면 DFS 진행
   2. 재귀함수를 호출하면서 다음 방문 위치와 현재 방문한 알파벳들도 같이 넘겨주어야 한다.
   3. DFS를 진행하면서 최대 이동 거리를 계속해서 갱신시켜준다. 
3. 큐에 데이터가 많이 쌓이게 되면 메모리 초과가 발생하니 BFS뿐 아니라 DFS로도 풀이를 해야 하는걸 배움. 또한 방문처리 할때 set 자료구조에 너무 의존하지 말고, 알파벳은 최대 26개이니까 방문 알파벳들을 문자열로 쭉 연결한 다음 set 연산자가 아닌 in 연산자를 사용하여도 크게 문제될 건 없어보임.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
R, C = map(int, input().split())

matrix = [list(input()) for _ in range(R)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0

def solve(visited_str, x, y):
    global R, C
    skip = True
    answer = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < R and 0 <= ny and ny < C:
            if matrix[nx][ny] not in visited_str:
                skip = False
                answer = max(answer,
                             1 + solve(visited_str + matrix[nx][ny], nx, ny))

    if skip:
        return 1
    else:
        return answer

print(solve(matrix[0][0], 0, 0))