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

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))

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

풀이 과정

1. 일단 기본적으로 anta, tica라는 단어가 들어간다.
   
   • 여기서, 알파벳 ['a', 'n', 't', 'i', 'c']는 기본적으로 무조건 들어가야 된다는 점을 알 수 있음.
2. 따라서, K가 5보다 작은 경우는 불가능하므로 0을 출력해주면 되고, 5보다 큰 경우는 두가지로 나눌 수 있다.
   1. 기본적으로 ['a', 'n', 't', 'i', 'c']는 들어가야 함.
   2. (1)에서 제외한 알파벳들 중 (K-5)개를 뽑음.
   3. 1번과 2번을 합치면 하나의 케이스가 된다.
3. 각각의 케이스별로 총 몇개의 단어를 읽을수 있는지 체크하고, 최댓값을 갱신하면 된다.
4. 위 과정을 Set 자료구조로 하였는데.. 자꾸 메모리 초과가 나와서 풀이를 좀 찾아보니 비트 마스킹 기법을 사용한다고 한다. 알파벳 위치를 기준으로 비트 '1'을 이동시키는 방식
   • a인 경우 001, b인 경우 010, c인 경우 100, ...  , ab인 경우 011, ...
   • 전체 단어들에 대해 각 단어들을 알파벳 별로 미리 비트화를 시켜준다. 
     • hello의 경우, 알파벳이 h,e,l,o가 있으므로 대응되는 비트값을 1로 수정
   • 각각의 케이스 비교단계에서 케이스 또한 비트화를 시켜준 다음 and 연산자를 해준다.
     • 케이스에서 ['a', 'n', 't', 'i', 'c', 'k']를 뽑았다고 할 때,  단어가 antic인 경우 모두 공통적으로 a, n, t, i, c의 비트가 1로 조정되어 있으므로, and연산자를 해주면 a,n,t,i,c에만 1로 지정되어 있을 것이다.
   • and 연산자의 결과가 케이스의 비트와 같은 경우 읽을 수 있는 단어이므로 카운팅

비트 마스킹이 set보다는 빠르므로 set이 속도 문제로 안된다면, 고려해보아야 한다는걸 배우게 되었다..

소스 코드

import sys
from itertools import combinations

input = lambda: sys.stdin.readline().rstrip()
N, K = map(int, input().split())
words = [0] * N
base = ['a', 'n', 't', 'i', 'c']
for i in range(N):
    word = list(input())[4:-4]
    for ch in word:
        words[i] |= (1 << ord(ch) - ord('a'))
        
answer = 0
if K < 5:
    pass
else:
    alpha = 'bdefghjklmopqrsuvwxyz'
    append_case = list(combinations(list(alpha), K-5))
    for case in append_case:
        make_bit = 0
        for ch in base:
            make_bit |= (1 << ord(ch) - ord('a'))
        for ch in case:
            make_bit |= (1 << ord(ch) - ord('a'))

        count = 0
        for i in range(len(words)):
            if words[i] & make_bit == words[i]:
                count += 1
        
        answer = max(answer, count)
        
print(answer)

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

풀이 과정

1. 보면 N값과 M값이 굉장히 크기 때문에 전수조사 하게 되는 경우 시간초과가 100% 날거라 생각됨.
2. 따라서, 친구들이 심사를 받는데 걸리는 시간을 기준으로 이분탐색을 진행함.
3. 범위는 최소 0, 최대 1000000000 * 10^9를 잡아주어야 한다. 
   • 이유는 입국심사대에 1명이 있으며, 친구들이 1000000000명, 그리고 걸리는 시간이 10^9인 경우를 고려
4. 중간값을 기준으로 중간값일때 심사받는 친구의 수가 M보다 크거나 같으면 시간을 줄여야 하므로 정답 저장후 왼쪽 구간, M보다 작은 경우는 정답을 저장하진 말고 오른쪽 구간을 진행하면 된다.
5. 저장된 정답을 출력해 준다.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()
N, M = map(int, input().split())
T = [int(input()) for _ in range(N)]

left = 0
right = (1000000000 * int(10e9)) + 1
answer = 0
while left <= right:
    mid = (left + right) // 2

    # 중간값일때, 심사받는 사람의 수 구함
    evaluated_people_count = 0
    for time in T:
        evaluated_people_count += (mid // time)

    # 심사받는 사람의 수가 M보다 작으면 시간을 늘려야 하므로 오른쪽 구간
    # M보다 크거나 같으면 시간을 줄여야 하므로 왼쪽 구간
    if evaluated_people_count >= M:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

print(answer)

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

풀이 과정

1. A지점, B지점, C지점에서 시작해서 다익스트라 알고리즘 적용
   • 그러면.. A지점에서 각 지점까지의 거리, B 지점에서 각 지점까지의 거리, C 지점에서 각 지점까지의 거리가 따로 나오게 된다.
2. 각각의 지점에서 A지점, B지점, C지점까지의 거리의 최솟값을 구한다.
   1. A, B, C를 다익스트라 알고리즘으로 구해진 거리, A[i]는 A지점에서 i지점까지의 거리
   2. 예시로 2번 지점이라고 할때, min(A[2], B[2], C[2])를 해주면 된다.
3. (2)의 최댓값이 나올 때의 지점 번호를 구해서 출력해주면 된다. 지점 번호의 경우 최솟값이 같은 경우 번호가 작은걸 출력해주라 하였으므로 지점 번호를을 왼쪽(1)에서 오른쪽(n)으로 진행하면서 갱신한다.

소스 코드

import sys
import heapq

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

N = int(input())
A, B, C = map(int, input().split())

graph = [[] for _ in range(N+1)]
M = int(input())

for _ in range(M):
    D, E, L = map(int, input().split())
    graph[D].append([E, L])
    graph[E].append([D, L])

def dijkstra(graph, start):
    INT_MAX = int(10e9)
    distance = [INT_MAX] * len(graph)
    distance[start] = 0
    heap = [[0, start]]
    while heap:
        dist, node = heapq.heappop(heap)
        if distance[node] != dist:
            continue

        for next_node, next_dist in graph[node]:
            if dist + next_dist < distance[next_node]:
                distance[next_node] = dist + next_dist
                heapq.heappush(heap, [distance[next_node], next_node])

    return distance

max_size = 0
answer = 0
dist_a = dijkstra(graph, A)
dist_b = dijkstra(graph, B)
dist_c = dijkstra(graph, C)

for i in range(1, N+1):
    if max_size < min(dist_a[i], dist_b[i], dist_c[i]):
        max_size = min(dist_a[i], dist_b[i], dist_c[i])
        answer = i
        
print(answer)

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

풀이 과정

1. 지름길 데이터를 정리한다.
   
   1. 시작점과 도착점이 같은데 이동 거리가 다른 지름길이 있을 수 있으므로 최소 거리로 해주어야 한다.
   2. 최소 거리로 조정한 다음, 딕셔너리를 사용하여 [시작점] = [[도착점, 이동거리], ... ] 형식으로 데이터를 저장한다. 
2. BFS를 진행한다.
   1. 시작점과 이동거리를 a, b라고 할 때, 두가지 경우가 존재한다. 
   2. 현재 지점의 다음 지점을 큐에 삽입한다. (a+1, b+1)
   3. 만약 현재 지점에 대응하는 키가 딕셔너리에 존재한다면(지름길이 존재한다면) 지름길로도 이동해보면 된다. (도착점, b+지름길 이동 거리)
   4. 현재 지점이 D라면, 정답을 갱신시켜 준다. 이 때 유의할 점은, 일방통행이므로 D를 넘게 되면 정답 처리가 되지 않음에 유의한다.
3. 정답을 출력한다.

문제의 분류는 다익스트라 알고리즘이었으나.. 처음 떠오른 방식이 BFS라 BFS로 풀이함. BFS가 아니더라도 다익스트라 알고리즘이나 DP로도 풀수 있다고 생각한다.

소스 코드

import sys
from collections import defaultdict, deque

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

N, D = map(int, input().split())
temp = defaultdict(lambda:int(10e9))

for _ in range(N):
    s, e, d = map(int, input().split())
    temp[(s, e)] = min(temp[(s, e)], d)

shortcut = defaultdict(lambda:[])
for (s, e), d in temp.items():
    shortcut[s].append([e, d])

queue = deque()
queue.append([0, 0])

answer = int(10e9)
while queue:
    current, movement = queue.popleft()
    if current > D:
        continue
    if current == D:
        answer = min(answer, movement)
        continue
    if shortcut.get(current) != None:
        for e, d in shortcut[current]:
            queue.append([e, movement + d])    
    queue.append([current+1, movement+1])
    
print(answer)

https://www.acmicpc.net/submit/14938

풀이 과정

1. 사실 이 문제는 다익스트라 알고리즘보다는 플로이드 알고리즘으로 풀이하는게 훨씬 쉽고 간단하게 풀린다. 다익스트라 알고리즘을 연습하고자 사용하였음..
2. 시작점을 1~n까지 각각의 지점에서 다익스트라 알고리즘을 적용한다.
   1. 최소 히프를 사용하여, 현재 갈수있는 노드 중 길이가 최소인 노드를 방문한다.
   2. 현재 노드를 거쳐갈때의 거리로 인접 노드들의 거리를 갱신할 수 있으면 갱신 후 히프에 해당 노드를 넣어준다.  
   3. 1-2를 반복하다 보면 히프에 같은 노드가 쌓일수도 있다. 따라서 히프에 저장된 길이와 현재 저장된 길이를 비교해준 다음, 다른 경우는 최솟값이 갱신된 경우이므로 그냥 넘어간다.
3. 다익스트라 알고리즘이 종료되면 거리가 m 이내인 지점의 모든 아이템의 개수를 더한 후, 최대 아이템 개수를 갱신한다.
4. 최대 아이템 개수를 출력한다.

소스 코드

import sys
import heapq

INT_MAX = int(10e9)
input = lambda: sys.stdin.readline().rstrip()

n, m, r = map(int, input().split())
item_count = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n+1)]

for _ in range(r):
    a, b, l = map(int, input().split())
    graph[a].append([b, l])
    graph[b].append([a, l])

answer = 0

# 전체 지점에서 시작해본 다음, 아이템을 몇개 구할수 있는지 구한다.
# 이후 최대 아이템의 개수 갱신
for start in range(1, n+1):
    distance = [INT_MAX] * (n+1)
    distance[start] = 0
    heap = []
    heapq.heappush(heap, [0, start])

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

        for next_node, next_distance in graph[node]:
            if distance[next_node] > distance[node] + next_distance:
                distance[next_node] = distance[node] + next_distance
                heapq.heappush(heap, [distance[next_node], next_node])
    
    total_item_count = sum([item_count[i] for i in range(1, n+1) if distance[i] <= m])
    answer = max(answer, total_item_count)

print(answer)

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

풀이 과정

1. 근처에 있는 음식물끼리 뭉칠수 있으므로, BFS를 진행하면 된다.
2. 우선 크기가 (N+1, M+1)인 배열을 하나 만들고, 모든 초깃값을 0으로 둔다.
3. 음식물이 떨어진 좌표의 값을 1로 수정한다.
4. 왼쪽 위에서 오른쪽 아래로 검사하면서, 값이 1인 경우 BFS를 진행한다.
   1. BFS를 진행하면서, 방문하는 좌표의 값을 0으로 수정한다.
   2. 현재 좌표 기준으로 상,하,좌,우 확인하여 값이 1인 경우 해당 좌표 큐에 저장(다음에 방문할 좌표)
   3. BFS를 종료할 때, 방문한 좌표의 수를 리턴하여 정답 갱신 (최댓값으로)

소스 코드

import sys
from collections import deque

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

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

matrix = [[0] * (M+1) for _ in range(N+1)]

def bfs(matrix, x, y):
    count = 1
    matrix[x][y] = 0
    queue = deque([[x, y]])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            nx, ny = a + dx[i], b + dy[i]
            if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]) and \
               matrix[nx][ny] == 1:
                matrix[nx][ny] = 0
                count += 1
                queue.append([nx, ny])

    return count

for _ in range(K):
    a, b = map(int, input().split())
    matrix[a][b] = 1

answer = 0
for i in range(1, N+1):
    for j in range(1, M+1):
        if matrix[i][j] == 1:
            answer = max(answer, bfs(matrix, i, j))

print(answer)

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

풀이 과정

1. s의 문자들로 구성된 큐를 생성한다.
2. t의 문자들을 왼쪽에서 오른쪽으로 순서대로 비교
   1. 큐의 맨 앞 요소가 t의 문자와 같다면 제거 후 다음 문자 진행
   2. 큐의 맨 앞 요소가 t의 문자와 같지 않다면 그냥 다음 문자 진행
3. 큐가 비어있다면 부분 문자열이고, 큐가 비어있지 않다면 부분 문자열이 아닌 것으로 볼 수 있다. 

소스 코드

import sys
from collections import deque

while True:
    try:
        s, t = input().split()
        queue = deque(list(s))

        for c in t:
            if queue and c == queue[0]:
                queue.popleft()

        if queue:
            print('No')
        else:
            print('Yes')
    except:
        break