Dev_Diary

https://www.acmicpc.net/problem/17436포함 배제의 원리 문제입니다. 포함 배제의 원리는 여러 집합의 합집합의 원소의 개수를 구할 때 교집합을 처리하는 방법 이라고 생각해도 될 것 같습니다.결론적으로 모든 집합의 합집합의 원소의 수는 모든 집합의 수를 모두 더하고모든 2 개의 교집합의 수를 빼고모든 3 개의 교집합의 수를 더하고...모든 2n 개의 교집합의 수를 빼고모든 2n+1 개의 교집합의 수를 더하고... 이 됩니다.import sysfrom itertools import combinationsfrom math import prodinput = sys.stdin.readlinedef solution(N, M, primes): # 총 카운트 total_cnt = ..

https://www.acmicpc.net/problem/1013정규 표현식 문제입니다. 파이썬 언어와는 별개로 모든 언어에서 공통적으로 채용하고 있는 '문자에 대한 공통 정규 표현식' 이 있는데, 이를 알면 굉장히 간단히 풀 수 있는 문제입니다. 파이썬에서 정규 표현식을 사용하기 위해서는 re 모듈을 사용합니다.해당 문제에서 나오는 정규식을 간단히 설명하자면 '+' 는 해당 문자의 앞에 있는 식이 1번 이상 반복된다는 뜻입니다. 비슷한 식으로는 '*' 가 있는데 이는 앞에 있는 식이 0번 이상 반복된다는 뜻입니다.'|' 는 앞의 식 혹은 뒤의 식 이라는 뜻으로, 둘 중 무엇이라도 올 수 있다는 뜻입니다.'()' 는 그루핑 식으로 'abc+' 와 같이 사용하면 해당 식에서의 '+' 는 'abc', 'ab..

https://www.acmicpc.net/problem/17472구현 + 최소 스패닝 트리 문제입니다. 구현 때문에 귀찮은 부분이 많을 뿐 사실 최소 스패닝 트리의 정석과 같은 문제입니다.해당 문제의 풀이는 크게 세 부분으로 나누어집니다. 1. 섬의 구분2. 섬 사이의 연결 탐색3. 최소 스패닝 트리 형성 1. 섬의 구분 같은 경우에는 DFS 나 BFS 혹은 Union-Find 등 그래프 탐색을 이용해 연결되어 있는 땅을 찾아주면 됩니다. 2. 섬 사이의 연결 탐색의 경우 섬의 모든 부분에서 네 방향으로 뻗어나가는 탐색 경로를 짜 가장 먼저 탐색되는 땅이 다른 섬인 경우 [현재 섬의 그룹, 다른 섬의 그룹, 거리] 의 형식으로 엣지를 형성해 기록해 줍니다. 3. 최소 스패닝 트리는 2 에서 만든 엣지를..

https://www.acmicpc.net/problem/28324그리디 알고리즘 문제입니다. 순서대로 진행할 때 '올리는 건 제한이 없지만 내릴 때는 1씩 밖에 못내린다 / 시작과 마지막은 0 이어야 한다' 라는 사실상 올릴 수 있는 한계가 동적이라는 말을 하고 있습니다. 그렇다면 반대로 진행해보겠습니다.'올릴 때는 1씩 밖에 못올리지만 내리는 건 제한이 없다 / 시작과 마지막은 0 이어야 한다' 로 조건이 바뀌면 상당히 편해집니다. 시작은 0 으로 시작하면 되고, 마지막은 그냥 마지막 속도를 전부 빼주면 됩니다. 그냥 최대 제한에 맞춰 1씩 더해주고 제한만큼 내려주고를 반복해주면 풀 수 있습니다.import sysinput = sys.stdin.readlinedef solution(N, limits)..

https://www.acmicpc.net/problem/3151이분 탐색 문제입니다. 두 개의 수를 고르는 문제였다면 가볍게 투포인터로 풀 수있지만 세 개의 수를 고르는 문제이기에 경우의 수가 기하급수적으로 늘어나 같은 방식으로는 풀 수 없습니다. 그렇다면 세 개의 수를 두 개의 수로 줄여주면 됩니다.제한시간이 4초이기 때문에 최악의 경우 10000 개의 수를 2중 반복하기에도 시간이 넉넉합니다.그렇다면 두 개의 수를 모두 계산한 뒤 나머지 하나의 수를 찾아주면 됩니다. 다만 중복이 발생할 수 있기 때문에 조치를 취해야 합니다.두 개의 수를 먼저 고른 뒤 나머지 하나의 수를 고를 때, 먼저 고른 두 개의 수 사이에서만 고르게 정한다면 중복은 발생하지 않고 보다 편하게 코드를 짤 수 있습니다.import..

https://www.acmicpc.net/problem/14567역시 전형적인 위상정렬 문제입니다.위상정렬 리스트를 만들어 순회를 하되, 순회가 가능해도 한번에 순회하는 것이 아닌 학기마다 끊어서 가능한 수업을 모두 큐에 넣어주어야 합니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, M, subjects): # 위상정렬 리스트 / [[들어오는 노드], 이수한 학기, [나가는 노드]] topol_list = [[set(), 0, set()] for _ in range(N+1)] for A, B in subjects: topol_list[A][2].add(B) top..

https://www.acmicpc.net/problem/2056전형적인 위상정렬 문제입니다.들어오는 노드와 나가는 노드를 정리해준 뒤 시간을 누적하며 들어오는 노드를 모두 탐색한 노드를 탐색하면 됩니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, works): # 위상정렬 그래프 / [[들어오는 노드들], 소요 시간, [나가는 노드들]] topol_graph = [[[], 0, []] for _ in range(N+1)] for w in range(len(works)): # 소요 시간 topol_graph[w+1][1] = works[w][0] # 입..

https://www.acmicpc.net/problem/1414문제자체는 단순한 최소 스패닝 트리 문제입니다.다만 입력을 숫자로 치환하는 과정이 추가된 문제입니다.import sysinput = sys.stdin.readline## Union-Find# Uniondef Union(node1, node2, group_list): # 각 노드의 그룹 group1 = Find(node1, group_list) group2 = Find(node2, group_list) # 두 그룹이 같으면 if group1 == group2: # 병합하지 않음 return False, group_list # 두 그룹이 다르면 # 작은 쪽으로 병합 if..

https://www.acmicpc.net/problem/2250중위순회 문제입니다. 트리를 인덱스에 기록하는 규칙을 살펴보면 트리를 순회하는 방법 중 중위순회의 순서와 일치함을 알 수 있습니다.따라서 중위순회를 하며 레벨과 인덱스를 기록하고 너비를 비교해주면 됩니다. 코드에서는 dataclass 를 사용해 노드를 정리했지만 노드를 정리하지 않고 리스트로 풀이해도 문제 없습니다.import sysfrom dataclasses import dataclassfrom collections import defaultdictinput = sys.stdin.readline# 노드@dataclassclass Node: level: int left: int right: int# 중위 순회def inor..

https://www.acmicpc.net/problem/1245그래프 순회 문제입니다. 그래프를 순회하며 현재 탐색하고 있는 높이보다 높고 인접한 위치가 존재하는지 탐색해주면 됩니다.다만 주의해야 할 점이 두 가지 있습니다. 첫 번째는 임의의 인덱스에서 탐색할 위치가 상 하 좌 우 네 방향이 아닌 좌상 좌하 우상 우하 를 합친 여덟 방향이라는 점 입니다.두 번째는 탐색시에 방문 목록을 작성하며 중복하지 않게 탐색할텐데 자신보다 낮은 위치나 높은 위치를 탐색할 때에도 방문 체크를 한다면 다음 높이를 탐색할 때 해당 위치를 탐색하지 않아 정확하게 탐색할 수 없다는 점입니다. 자신과 같은 위치만 방문 체크를 하며 탐색해야 합니다.import sysfrom collections import dequeinput..