링크: https://www.acmicpc.net/problem/1516아이디어이전 일이 끝나야지만 다음 일을 할 수 있는 순서가 정해져있는 작업을 다루는 문제 -> 위상정렬을 사용하자아래 리스틀를 선언해두고 사용하자그래프진입 차수(사전에 진행되어야 하는 건물 개수)건물별 걸리는 시간 저장DP (사전 진행되어야 하는 건물 중 가장 늦게 건설되는 건물을 기준으로 코스트 계산)구현import sysfrom collections import dequeinput = sys.stdin.readline# 순서ㅇ가 있는 작업 -> 위상 정렬을 사용하자# 그래프 배열, 진입 차수 배열, 비용 배열, DP 배열 N = int(input())graph = [[] for i in range(N)]indegree = [0] ..
링크: https://www.acmicpc.net/problem/1717 아이디어초기에 n+1개의 집합이 존재하고, 합집합과 동일 집합 여부 판별 연산을 빠르게 처리해야 한다.입력의 개수가 최대 10만 개이고, 노드 수가 최대 100만 개이므로 DFS나 재귀는시간초과가 발생한다.집합 관리 알고리즘인 유니온 파인드 자료구조를 사용하자.경로 압축 기법을 함께 사용하면 거의 상수 시간 복잡도로 처리할 수 있도록 하자.배열을 만들어 각 원소의 부모 노드를 저장한다.find(x) 함수로 x의 루트를 찾고 경로 압축을 수행해 트리 깊이를 줄인다.union(a, b) 함수는 두 집합을 하나로 합친다.find(a) == find(b)이면 같은 집합에 속해 있다는 의미로 YES 출력구현import sysinput = s..
링크: https://www.acmicpc.net/problem/11286아이디어입력을 받을 때마다 자동정렬이 되는 힙 자료구조를 사용하자파이썬의 heapq를 사용튜플 자료형을 사용하여 우선순위로 사용할 절대값을 앞에 뒤에는 입력받은 값을 저장한다.이러면 절대값을 기준으로 자동 정렬이 되어 음수인지 양수인지도 알 수 있게된다.구현import sysimport heapqinput = sys.stdin.readlineN = int(input())heap = []for i in range(N): tmp = int(input()) if tmp != 0: heapq.heappush(heap, (abs(tmp), tmp)) else: if len(heap) == 0: ..
링크: https://www.acmicpc.net/problem/18870 아이디어입력된 리스트를 정렬한 형태의 리스트를 하나 더 선언enumerate() 함수로 인덱스와 값을 매칭시킨 딕셔너리 생성이러면 값의 크기순으로 순서가 매겨짐이를 기존 리스트의 값들을 순서대로 딕셔너리의 값을 불러오기구현N = int(input())li = list(map(int, input().split()))result = [0 for i in range(N)]tmp = sorted(set(li))rank = {num: i for i, num in enumerate(tmp)}print(*(rank[num] for num in li)) 마무리처음엔 enumerate()함수가 떠오르지 않아 반복문을 통해 구현했었다.하지만 N의 ..
링크: https://www.acmicpc.net/problem/2178 아이디어최단거리 -> BFS 사용입력받은 리스트를 수정하며 몇번째 방문인지 표시함과 동시에 방문 여부도 표시이동하기 이전 좌표의 값 + 1 한 값을 저장하며 진행그럼 (N, M) 좌표의 값을 출력하면 끝 구현from collections import dequeN, M = map(int, input().split())miro = [list(map(int, list(input().strip()))) for _ in range(N)]q= deque()q.append((0,0))dx = [1, 0, -1, 0]dy = [0, 1, 0, -1]while q: y, x = q.popleft() for i in range(4): ..
링크: https://www.acmicpc.net/problem/7569아이디어익은 토마토를 기준으로 주변으로 퍼지며 익는 현상이 이전에 바이러스 문제랑 비슷BFS를 활용해서 풀면 될듯함3차원 배열을 선언 후 익은 토마토의 위치틀을 큐에 저장큐를 기준으로 BFS를 진행6방향을 모두 탐색하며 진행한다익지않은 토마토를 발견하면 이전 토마토의 수에서 +1한 값을 저장해둔다.이는 며칠째 익은 토마토인지 확인 할 수 있는 지표가 됨BFS를 모두 마친 후 모든 토마토가 익었는지 판단익지 않은 토마토가 있으면 -1 반황그렇지 않으면 배열의 최대값을 반환해준다.구현from collections import dequeM, N, H = map(int, input().split())box = [[list(map(int,in..
링크: https://www.acmicpc.net/problem/10819 아이디어N의 크기가 3가능한 모든 경우의 수를 다 계산해도 (가능한 모든 수열)! *(비교횟수) = 8! * 8 = 얼추 32만 모든 경우를 다 보고 비교해도 충분할 것 같음.permutations 함수로 가능한 모든 수열을 다 구하고앞뒤 요소 합 연산 을 진행결과값을 이전 연산값과 비교하며 최대값을 찾자구현# 모든 경우를 다 비교해봐도 될듯# N의 최대 크기가 8이라 다 비교해도 8! * 8 는 얼추 32만번 임 충분from itertools import permutationsN = int(input())lis = list(map(int, input().split()))result = 0for li in permutations(..
링크: https://www.acmicpc.net/problem/16924 아이디어*로 십자가를 만드는게 요지가 아니였음십자가로 입력된 격자를 완성 할 수 있냐 없냐가 주 요구사항이다십자가로 만든 격자를 표시해야 할 리스트 하나를 만들고 가자* 위치를 1로 지정하고 나머지를 0으로 해두자이제 * 위치를 기준으로 만들 수 있는 십자가를 탐색하고 표시용 리스트애 표시하자size크기로 중간 기준 상 하 좌 우 좌표의 값이 유효한 위치인지 또한 *이 맞는지 판별아니라면 바로 return으로 함수 종료십자가가 완료됐다면십자가의 중심 좌표를 저장그 십자가 영역의 좌표를 표시 리스트에 표시 (1->0)size를 키워가며 모두 탐색check 리스트를 판단하고 모든 영역이 채워지지 않았으면 -1 출력 후 종료무두 채워..
링크: https://www.acmicpc.net/problem/2877 아이디어그냥 2진수 생각하면 너무 쉬울 거 같다4는 0 1은 7로 생각하고 풀어보자우선 몇자리수인지 판단하자1자리 - 2개2자리 - 4개3자리 - 8개이런 식의 규칙을 가진다 중복합을 통해 몇자리인지 판단해아할듯자릿수를 구한 후 그 자리수에서 몇번째의 수인지 한번 더 판단입력값 K에서 누적합을 진행합 값을 빼고 -1을 해준다-1을 해줘야 하는 이유는 0000과 같은 경우도 하나의 경우로 쳐야하기 때문몇번째 수인지 구했으면 이를 2진수 변환을 진행 자릿수도 구한 값으로 지정하여 생성변환된 2진수를 0을 4로 1을 7로 변환한다.그럼 끝~!구현# 뭐야 2진수로 생각하면 쉬울듯# 몇자린지 구하고 거기서 몇번째인지 판단하면 끝K = int..
