Algorithm/Python9 [백준] 1655 가운데를 말해요 (python) - 중앙값 힙(Median Heap) 1️⃣ 문제 링크 https://www.acmicpc.net/problem/1655 2️⃣ 기억해야 했던 개념들 - 매번 median 값을 어떻게 빠르게 구할 수 있을까? (python 기준 0.6초)- 정렬을 매번 하면 O(N² log N)이므로 10⁵ 데이터면 시간초과. - 정렬을 하지 않고, 중앙값을 찾을 수 있는 방법을 생각 -> 중앙값 힙(Median Heap) 개념을 이용한다. 3️⃣ 풀이 과정두 그룹으로 나누기중앙값보다 작거나 같은 값 → 왼쪽 그룹 (MAX HEAP)중앙값보다 큰 값 → 오른쪽 그룹 (MIN HEAP)MAX_HEAP의 크기 = MIN_HEAP 크기 + 1 로 유지한다.들어오는 값이 현재 중앙값이 작거나 같으면 MAX HEAP에 넣고 아니면 MIN HEAP에 넣는다.만약 크.. 2025. 10. 29. [프로그래머스] 등산코스 정하기 (python) 1️⃣ 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/118669 2️⃣ 기억해야 했던 개념들 - 기본 다익스트라 개념- 다익스트라의 시작 정점은 여러 개일 수 있다. 3️⃣ 풀이 과정문제를 요약하면, 여러 개의 출입구 중 하나의 출입구에서 시작하여 여러 개의 산봉우리 중 하나의 산봉우리에 방문하고 다시 동일한 출입구로 내려올 때까지의 Intensity를 최소화해야 한다.이때, intensity는 출입구 -> 쉼터 -> 산봉우리를 이동할 때 휴식 없이 이동해야 하는 가장 긴 시간을 말한다. 1. 다익스트라를 써야하는 건 알겠는데.. 각 출입구마다 다 돌면서 다익스트라로 돌면 안 되나?안 된다. 정점의 개수는 최대 50,000개, 간선.. 2025. 10. 28. [프로그래머스] 도넛과 막대 그래프 (python) 1️⃣ 문제https://school.programmers.co.kr/learn/courses/30/lessons/2587112️⃣ 필요한 개념차수 기반 문제 판별하기입력 크기 크다 → 탐색 괜찮나?문제 설명이 구조적 정의(사이클, 끝점, 교차점) → 차수로 풀 수 있나?출력이 개수만 요구됨 → 구체 탐색 필요 없네?3️⃣ 풀이def solution(edges): answer = [] in_out_list = [[0,0] for _ in range(1000000+1)] if (len(edges) == 1): return 1, 1, 0, 0 for edge in edges: a,b = edge in_out_list[a][1] += 1 .. 2025. 9. 5. [프로그래머스] 숫자 문자열과 영단어 (python) 1️⃣ 문제https://school.programmers.co.kr/learn/courses/30/lessons/81301 2️⃣ 기억해야 했던 개념들a.isdigit() : digit인지 판단하는 거 까먹어서 함수로 구현함 (기억하기) 3️⃣ 풀이 과정제한 시간 10초 -> 한번만 N의 복잡도면 충분히 가능하겠다 생각 (단순 구현)순차적으로 문자열 파싱함 4️⃣ 코드def is_num(a):if (a == "0" or a == "1" or a == "2" or a == "3" or a =="4" or a == "5" or a == "6" or a == "7" or a == "8" or a == "9"):return Trueelse:return Falsedef solution(s):answer = "".. 2025. 9. 5. [알고리즘 스터디] 백준 2164번 Python 풀이 - 카드2 (연산 복잡도, deque, 식 세우기) # 문제https://www.acmicpc.net/problem/2164 2164번: 카드2N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가www.acmicpc.net# 시도 1 (실패 - 시간초과)number = int(input())array = [i+1 for i in range(number)]length = numberwhile (len(array) != 1): del array[0] item = array.pop(0) array.append(item) print(array)print(array[0])array의 pop 연산자와 .. 2022. 6. 3. [알고리즘 스터디] 백준 2798번 Python 풀이 - 블랙잭 # 문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장www.acmicpc.net# 코드 풀이def solve(): n, m = map(int, input().split()) input_list = [] sum_list = [] input_list = list(map(int, input().split())) for i in range(2, n): for j in range(1, i): .. 2022. 6. 3. 이전 1 2 다음
