전체 글

푼 날짜 : 2024.12.26푼 문제 : [14621] / 나만 안되는 연애사용한 언어 : python알고리즘 : 최소 스패닝 트리(MST)   접근방식 :일반적인 MST 알고리즘을 사용했다.추가적으로 성별을 다르게 번갈아 가며 연결하기 위해 heap에 성별을 추가 요소로 적용했다. 문제의 조건은 다음과 같다.사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다.시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다.따라서 W면 M과 연결 M이라면 W와 연결하도록 구현했으며 이 과정에서 최단 거리를 계산할 수 있도록 구현했다..

푼 날짜 : 2024.12.25푼 문제 : [21924] / 도시 건설사용한 언어 : python알고리즘 : 최소 스패닝 트리(MST)   접근방식 :일반적인 MST 알고리즘을 사용했다.절약 비용을 계산하기 위해 초기 비용을 계산하고 최소 연결 비용을 계산하여 절약 금액을 도출했다.   코드 :import sysimport heapqinput = sys.stdin.readlineN, M = map(int, input().split())graph = [[] for _ in range(N+1)]visited = [0 for _ in range(N+1)]# 초기 비용을 계산하기 위함init_cost = 0for _ in range(M): A, B, C = map(int, input().split()) ..

푼 날짜 : 2024.12.24푼 문제 : [16398] / 행성 연결사용한 언어 : python알고리즘 : 최소 스패닝 트리(MST)  접근방식 :일반적인 MST 알고리즘을 사용했다.다만 평소에 리스트로 구현을 했기 때문에 행렬을 리스트로 변환하는 과정을 추가해주었다.  코드 :import sysimport heapqinput = sys.stdin.readlineN = int(input())graph = [[] for _ in range(N)]visited = [0 for _ in range(N)]# 행렬을 리스트로 변환하는 과정for i in range(N): lst = list(map(int, input().split())) for j in range(len(lst)): if..

푼 날짜 : 2024.12.23푼 문제 : [1647] / 도시 분할 계획사용한 언어 : python알고리즘 : 최소 스패닝 트리(MST)  접근방식 :문제의 요구조건을 보면  두 개의 분리된 마을로 분할마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할(각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다) => 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 위와 같은 조건을 만족하기 위해 내가 생각한 방법은 우선 전체를 연결한 비용을 계산한 후 비용이 가장 크게 드는 길을 끊어주는 것이다.  이를 위해서는 전체 비용을 계산한 후 비용이 가장 큰 길의 값을 빼주면 된다! MST 알고리즘 중 Prim 방식을 활..

푼 날짜 : 2024.12.22푼 문제 : [1922] / 네트워크 연결사용한 언어 : python알고리즘 : 최소 스패닝 트리(MST)  접근방식 :전형적인 MST 알고리즘으로 풀이했다.파이썬의 heapq를 사용하면 자동으로 최소 힙 형태로 정렬이 되기 때문에 해당 모듈을 사용하여 구현했다.   코드 :import sysimport heapqinput = sys.stdin.readlineN = int(input())M = int(input())graph = [[] for _ in range(N+1)]visited = [0 for _ in range(N+1)]for _ in range(M): a, b, c = map(int, input().split()) graph[a].append((c, b..

오랜만에 포스팅~~   푼 날짜 : 2024.12.20푼 문제 : [22116] / 창영이와 퇴근사용한 언어 : python알고리즘 : 다익스트라(dijkstra)  접근방식 :처음 문제를 풀 때 실수했던 것은 최대라는 말을 빼먹구 코드를 짠 것.. 창영이가 지날 수 있는 최대 경사의 최솟값을 알아야만 한다.  "최대 경사" 를 구하는 문제이다.따라서 경사가 없다고 그냥 0을 출력하면 안된다는 얘기...  백준 게시판에서 주워온 반례를 첨부한다.320 15 205 10 202 1 0 답은 0이 아니라 5다.5 따라서 최대 경사 max를 구하면서 그 값이 가장 작은 수를 구하는 코드를 짜야한다!   코드 :import sysimport heapqinput = sys.stdin.readlineINF = fl..

푼 날짜 : 2024.12.10푼 문제 : [5568] / 카드 놓기사용한 언어 : python알고리즘 : 백트래킹   접근방식 :백트래킹 방식으로 하나씩 추가했다가 뺐다가 하는 방식으로 풀이했다.이때 사용 유무를 확인하기 위해 visited배열을 선언하여 인덱스로 확인했을 때 사용한 카드라면 넘기고 사용하지 않은 카드를 확인하며 추가하도록 구현했다.    코드 :import sysinput = sys.stdin.readlinen = int(input())k = int(input())num_list = []for _ in range(n): num = int(input()) num_list.append(num)# 카드 중복 사용을 체크하기 위한 배열vistied = [0 for _ in rang..

푼 날짜 : 2024.12.09푼 문제 : [5430] / AC사용한 언어 : python알고리즘 : 문자열, 파싱, 덱  접근방식 :처음에는 배열을 수행 값 마다 변경해서 시간 초과가 났다.따라서 인덱스 위치와 방향 값만 체크 후 그에 따라 출력을 해주었다.   코드 :import sysinput = sys.stdin.readlineT = int(input())for _ in range(T): p_list = list(input().rstrip()) n = int(input()) n_list = list(input().rstrip()) lst = [] # 문자열로 받은 숫자 처리를 위함 now_str = '' for i in n_list: if ..