남남이루의 고군분투 🌳

다익스트라는, 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산한다. (출처: 책 알고리즘문제해결전략) 알고리즘 특징 우선순위 큐(파이썬에서는 heapq 사용)에 정점의 번호와 함께 지금까지 찾아낸 해당 정점까지의 최단 거리를 쌍으로 넣는다. 정점까지의 최단거리를 기준으로 정점을 배열함으로써 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾는 과정을 간단하게 한다. 유의할 점은, 각 정점까지의 최단 경로가 갱신될 수 있다는 점이다. 핵심 구조 import heapq g = [[] for _ in range(노드수 + 1)] for _ in range(노드수): 출발노드, 도착노드, 가중치 = map(int, input().split())..

2차원 DP를 푸는 게 아직 너무 어색하다, 어려웠던 점 누적합 데이터를 쌓아가는 부분 누적합 그래프를 바탕으로 일부 값을 계산하는 식을 짜는 부분 참고한 블로그 [python/파이썬] 백준 11660 구간 합 구하기 5 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경 sodehdt-ldkt.tistory.com [백준] 11660 구간 합 구하기 5 (python) - 누적 합 (2차원) 정리 문제 링크 : https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의..

메모리 초과 ➔ 정답처리 ➔ 개선 분석한 차이점 메모리 초과 케이스 (1차코드) : 56번쯤 라인에 바다 & 거리값 입력 안되어있으면 지금까지 온 거리 +1 이랑 기존 입력값이랑 min 비교하는데, 안해도 됨.. . BFS가 어떤 식으로 전개되는지 잘 안그려진다. 이 조건이 2차 코드에서 왜 없어도 되는지 이해가 잘 안간다. BFS는 칸마다 최단거리로 채워진다는 특징 때문인듯, 이미 방문했으면 굳이 안채워도 되나봐 secChecked 라고 구획을 그린 그래프를 별도로 두고, 이거로 visited도 판단함.. 그래프가 커질수록 부하가 걸렸나 => 메모리 초과의 원인인 듯 정답처리 된 케이스 (2차코드) : 섬 입력받은 표에 그대로 구획을 표시한거로 활용하고, visited True False 로 접근해서 ..

1. sorting 알고리즘 (정렬 알고리즘) : 배열의 아이템을 순서대로 정렬하는 알고리즘 1-1. 버블 정렬 (Bubble Sort) 가장 기본적인 정렬 알고리즘, 인접한 요소들이 순서에 맞지 않으면 반복적으로 교체한다. 1-2. 병합 정렬 (Merge Sort) 분할 정복 전략을 사용하는 알고리즘이다. 1-3. 퀵 정렬 (Quicksort) 평균적으로 n log n의 시간복잡도를 수행하는 가장 인기있는 정렬 알고리즘이다. 빠르고 효율적이다. 1-4. 힙 정렬 (Heap sort) 완벽한 이진 트리(:heap)로 시각화 되는 배열에 의해 작동한다. 2. Searching 알고리즘 (탐색 알고리즘) : 자료(data set)에서 요소를 찾기 위한 알고리즘 1-1. 이진 탐색 (Binary Search)..

문제 리스트에서 두 개 뽑아서 더한 값을 오름차순으로 정렬해라. 문제 바로가기 내 풀이 from itertools import combinations def solution(n): comb = set(map(sum,(combinations(n, 2)))) return sorted(list(comb)) 결과 비슷한데, map없이 쓴 다른 사람 풀이 (list comprehension) : 더 느림, 같은 결과를 가져온다는 점만 배우면 된다. from itertools import combinations def solution(numbers): return sorted(set(sum(i) for i in list(combinations(numbers, 2)))) 결과 반환값의 형태는 list여야 해서 lis..

문제 문제 | 지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 시도 방법1. 문자들을 다 숫자 코드로 바꿔서 일치하는 거 찾으려고 했음 결과 답은 맞으나,, 효율성에서 실패. 딕셔너리 썼는데, 각 utils를 고유값으로 해서 그런가봐 ㅍㅅㅍ ((문풀후 추가 : 딕셔너리까진 맞음, 치환도 괜찮을듯, 다만 점수 찾는 부분이 시간 오래걸리는 원인이었음)) # ''' # 조건에 맞는 지원자는 몇 명? => 탐색? # 언어 : cpp java ..

문제 from itertools import combinations def solution(orders, course): comb_dic = {long: {} for long in course} selected = set() for long in course: best_num = 2 for guest in orders: comb = list(map(sorted, combinations(guest, long))) comb = ["".join(arr) for arr in comb if len(arr) > 0] for e in comb: if not e: continue key = "".join(sorted(e)) if key in comb_dic[long].keys(): comb_dic[long][key] ..

[ 문제 바로가기 ] 수도코드 내 답안 def solution(users, report, k): report = set(report) report = [text.split() for text in report] history = {x[0]:[] for x in report} reported_cnt = {key:0 for key in users} reported_who = {key:[] for key in users} # block for content in report: whom = content[1] reported_cnt[whom] += 1 reported_who[whom].append(content[0]) blocked = [i for i, cnt in reported_cnt.items() if c..

아직 잘 모르겠는 문제, 외우고 쳐보는 것도 잘 안된다. 참고한 후, 답안 from collections import deque def solution(queue1, queue2): answer = 0 mid = sum(queue1) + sum(queue2) if mid % 2 != 0: return -1 tot //= 2 q1 = deque(queue1) q2 = deque(queue2) sum1 = sum(queue1) sum2 = sum(queue2) while q1 and q2: if sum1 > mid: tmp = q1.popleft() sum1 -= tmp sum2 += tmp elif sum1 < mid: tmp = q2.popleft() q1.append(tmp) sum1 += tmp su..

내 코드 from collections import Counter def solution(id_list, report, k): report = set(report) dic = {} for id in id_list: dic[id] = 0 reported = [x for x,y in Counter([r.split()[1] for r in report]).items() if y>= k] print(reported) answer = [0] * len(id_list) for r in report: a, v = r.split() if v in reported: idx = id_list.index(a) answer[idx] += 1 return answer 다른 사람 코드 def solution(id_list, re..