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

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

풀이 과정

구현 문제 겁나 어렵네

1. 풀이 이후 다른 사람들의 해결 방법을 보니 여러 해결방법이 있는것 같다.. 일단 본인은 직선 단위로 풀이를 진행함.
2. 각각의 직사각형을 4개의 직선으로 나누어서 저장.
3. 직선을 저장할 때, 다른 직선과의 교점이 발생할 경우, 해당 직선을 교점을 기준으로 나누어서 저장
   1. 교점 기준으로 왼쪽, 오른쪽, 위, 아래 총 네개의 직선이 나온다.
   2. 나누어진 직선이 또 다른 직선과의 교점이 발생할 수 있으므로 이 과정은 recursion으로 진행
4. 직선들 중 직선이 도형 내부에 존재하는 경우를 빼준다.
5. 시작점에서부터 BFS를 진행하여 도착 지점까지의 최소 거리를 구해준다.
6. 최소 거리를 리턴해주면 된다.

말은 쉽게 했지만.. 과정 하나하나 직접 코딩할 때 생각보다 시간이 훨씬 많이 걸려 3시간정도 걸린것 같다. 물론 이것도 변이 겹치는 경우가 없어서 위같이 풀이를 할 수 있었음. 구현 문제 연습을 조금 더 많이 해야할 것 같다..

소스 코드

"""
	nbalance97.tistory.com
"""

import sys
from collections import defaultdict, deque

sys.setrecursionlimit(10**5)

def get_cross_point(lineA, lineB):
    p1_x, p1_y, p2_x, p2_y = lineA
    p3_x, p3_y, p4_x, p4_y = lineB
    
    # 평행인 경우
    if (p1_x == p2_x and p3_x == p4_x) or (p1_y == p2_y and p3_y == p4_y):
        return ()
    
    if p1_x == p2_x: 
        # 세로 직선인 경우
        if (p3_x < p1_x and p1_x < p4_x and p1_y < p3_y and p3_y < p2_y):
            return (p1_x, p3_y)
    else: 
        # 가로 직선인 경우
        if (p3_y < p1_y and p1_y < p4_y and p1_x < p3_x and p3_x < p2_x):
            return (p3_x, p1_y)
    
    return ()

def division(currentline, addline, deleteline, new_line):
    for exist_line in currentline:
        point = get_cross_point(new_line, exist_line)
        if point:
            deleteline.append(exist_line)
            x, y = point
            division(currentline, addline, deleteline, (new_line[0], new_line[1], x, y))
            division(currentline, addline, deleteline, (x, y, new_line[2], new_line[3]))
            division(currentline, addline, deleteline, (exist_line[0], exist_line[1], x, y))
            division(currentline, addline, deleteline, (x, y, exist_line[2], exist_line[3]))
            return

    addline.append(new_line)
        
def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    line = set()
    
    for x1, y1, x2, y2 in rectangle:
        make_lines = [(min(x1, x2), y1, max(x1, x2), y1), (x2, min(y1, y2), x2, max(y1, y2)), 
                      (min(x1, x2), y2, max(x1, x2), y2), (x1, min(y1, y2), x1, max(y1, y2))]
        for new_line in make_lines:
            delete_line = []
            add_line = []
            
            division(line, add_line, delete_line, new_line)
                    
            for delete in delete_line:
                line.remove(delete)
            
            for add in add_line:
                line.add(add)

    delete_candidate = []
    # 사각형 내부에 직선이 포함되는지 확인
    for x1, y1, x2, y2 in line:
        for r_x1, r_y1, r_x2, r_y2 in rectangle:
            if x1 == x2:
                # 세로
                if r_x1 < x1 and x1 < r_x2 and r_y1 <= y1 and r_y2 >= y2:
                    delete_candidate.append((x1, y1, x2, y2))
                    break
            else:
                # 가로
                if r_y1 < y1 and y1 < r_y2 and r_x1 <= x1 and r_x2 >= x2:
                    delete_candidate.append((x1, y1, x2, y2))
                    break
    
    for candidate in delete_candidate:
        line.remove(candidate)
    
    graph = defaultdict(lambda:[])
    queue = deque()
    visited = set()
    for x1, y1, x2, y2 in line:
        if x1 <= characterX and characterX <= x2 and y1 <= characterY and characterY <= y2:
            queue.append([x1, y1, abs(x1-characterX) + abs(y1-characterY)])
            queue.append([x2, y2, abs(x2-characterX) + abs(y2-characterY)])
            visited.add((x1, y1))
            visited.add((x2, y2))
            
        graph[(x1, y1)].append((x2, y2))
        graph[(x2, y2)].append((x1, y1))
    
    # 이동 파트
    answer = int(10e9)
    while queue:
        x, y, dist = queue.popleft()
        for n_x, n_y in graph[(x, y)]:
            if min(x, n_x) <= itemX and itemX <= max(x, n_x) and \
               min(y, n_y) <= itemY and itemY <= max(y, n_y):
                answer = min(answer, dist + abs(itemX - x) + abs(itemY - y))
                continue
                
            if (n_x, n_y) not in visited:
                queue.append([n_x, n_y, dist + abs(n_x - x) + abs(n_y - y)])
                visited.add((n_x, n_y))
                        
    return answer

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://programmers.co.kr/learn/courses/30/lessons/87377

풀이 과정

1. 각각의 선분들의 교점을 따로 저장해 둔다.
   1. 문제 아래의 수식을 기반으로 ad - bc가 0일때는 일치하거나 교점이 없는 경우이므로 생략하고 0이 아닐때만 교점 x,y를 구해준다.
   2. 교점 x, y가 정수가 아닌 경우는 저장하지 않아야 함 
      • 나머지 연산 사용
   3. x, y가 정수인 경우, 나중에 필요하기 때문에 최소 x,y 와 최대 x,y를 갱신시켜 준다.
2. 따로 1000 x 1000 배열을 만들어 둔 다음, 각각의 교점에서 최소 x, 최소 y를 빼준 지점에 * 표시를 해준다.
   • 교점들의 시작점을 모두 (0, 0)으로 설정한다고 생각하면 됨.
3. 이제 y의 범위를 (최대 y - 최소 y) ~ 0까지의 배열을 저장해주면 된다.
   • x의 범위는 (0 ~ 최대 x - 최소 x) 까지

• 헤맸던 점은.. 우선 교점 x,y가 정수가 아닌 경우도 고려해서 틀렸었고 다음으로 최댓값의 경우 초기값을 1000000000으로 해두어서 괜찮았는데, 최솟값을 0으로 두었다가 계속해서 틀린 문제점이 있었다. 최솟값도 -1000000000으로 두어 해결함.

소스 코드

def check(a, b, c, d):
    return (a*d) - (b*c) != 0

def get_xy(a, b, e, c, d, f):
    if ((b * f) - (e * d)) % ((a * d) - (b * c)) != 0 or \
       ((e * c) - (a * f)) % ((a * d) - (b * c)) != 0:
            return (-int(10e9), -int(10e9))
    
    x = ((b * f) - (e * d)) // ((a * d) - (b * c))
    y = ((e * c) - (a * f)) // ((a * d) - (b * c))
    
    return (x, y)

def solution(line):
    answer = []
    point_set = set()
    matrix = [['.'] * 1001 for _ in range(1001)] 
    min_x, max_x = int(10e9), -int(10e9)
    min_y, max_y = int(10e9), -int(10e9)
    
    for i in range(len(line)):
        for j in range(i):
            if check(line[i][0], line[i][1], line[j][0], line[j][1]):
                x, y = get_xy(line[i][0], line[i][1], line[i][2],
                             line[j][0], line[j][1], line[j][2])
                
                if x == -int(10e9):
                    continue
                
                if (x, y) not in point_set:
                    min_x, max_x = min(min_x, x), max(max_x, x)
                    min_y, max_y = min(min_y, y), max(max_y, y)
                    point_set.add((x, y))
    
    for x, y in point_set:
        if y - min_y <= 1000 and x - min_x <= 1000:
            matrix[y-min_y][x-min_x] = '*'
        
    max_y = max_y - min_y
    max_x = max_x - min_x
    
    for i in range(max_y, -1, -1):
        answer.append("".join(matrix[i][:max_x+1]))
        
    return 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

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

풀이 과정

1. 이분 탐색으로 나누어 줄 과자의 길이를 찾는다.
   • 과자의 길이가 구간의 중간값일 때, 과자를 나누어줄 수 있는지 확인한다.
   • 확인하는 방법은 모든 과자의 길이를 중간값으로 나눗셈한 값의 합이 나누어주어야 하는 인원 수보다 많거나 같은 경우 나누어줄 수 있는것이며, 반대인 경우 나누어줄 수 없는 경우이다.
     • 예시로는.. (1, 3, 5, 7, 9)라고 하고 중간값이 3이라고 하면, 3, 5일때는 1명이고 7일때는 2명, 9일때는 3명 나누어줄 수 있으므로 총 6명 나누어줄 수 있다. 
   • 나누어줄 수 있다면 과자의 길이의 최댓값을 구해야 하므로 정답을 저장하고 중간값 기준 오른쪽 구간에 대해서 진행하고, 나누어줄 수 없다면 왼쪽 구간에 대해서 진행한다.
2. 구한 과자의 길이를 출력한다.

• 구간의 초기값을 문제를 보고 잘 조정해주어야 한다.. 처음에는 단순하게 1000000으로 했다가 틀렸는데, 문제를 다시 보니 과자의 길이가 1000000000까지이므로 최대 1000000000까지 나올 수 있으므 맞추어서 조정해 주었다.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()
M, N = map(int, input().split())
snacks = list(map(int, input().split()))

def test(snacks, target, target_people_count):
    people_count = 0

    if target == 0:
        return False
    
    for snack in snacks:
        people_count += (snack // target)

    if people_count >= target_people_count:
        return True
    else:
        return False

left, right = 0, int(10e9)+1

answer = 0
while left <= right:
    mid = (left + right) // 2
    if test(snacks, mid, M):
        answer = mid
        left = mid+1
    else:
        right = mid-1

print(answer)