pythaac의 개발노트

BAEKJOON Online Judge(BOJ) 문제입니다. https://www.acmicpc.net/ Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 문제 https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 내가 작성한 코드 import sys read = sys.stdin.readline def read_data(): N = int(..

BAEKJOON Online Judge(BOJ) 문제입니다. https://www.acmicpc.net/ Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 내가 작성한 코드 import sys from collections import defaultdict, deque..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 g 이상인 값을 s와 매칭할 수 있는 최대 개수 책에서 구현된 코드 # 그리디 알고리즘 from typing import List class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() s.sort() child_i = cookie_j = 0 # 만족하지 못할 때까지 그리디 진행 while child_i = g[child_i]: child_i += 1 cookie_j += 1 return child_i # 이진 탐색 ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 주유소를 원형 큐에서 시계방향으로 돌 때, 현재 채울 수 있는 gas와 다음 주유소의 cost로 모든 주유소에 도달할 수 있는 시작점 출력 책에서 구현된 코드 from typing import List class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: # 모든 주유소 방문 가능 여부 판별 if sum(gas) < sum(cost): return -1 start, fuel = 0, 0 for i in range(len(gas)): # 출발점이 안되는 지점 판별 if gas[i] + fuel < cost[i]..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 n개 안에 겹치는 문자가 없도록 배열, 불가능할 경우 "idle"을 삽입하여 최소 길이 출력 책에서 구현된 코드 import collections from typing import List class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: counter = collections.Counter(tasks) result = 0 while True: sub_count = 0 # 개수 순 추출 for task, _ in counter.most_common(n + 1): sub_count += 1 result += 1 counter.s..

BAEKJOON Online Judge(BOJ) 문제입니다. https://www.acmicpc.net/ Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 문제 https://www.acmicpc.net/problem/22981 22981번: 휴먼 파이프라인 모든 상자를 최대한 빠르게 옮기는 경우의 작업 시간을 분 단위로 출력한다. www.acmicpc.net 내가 작성한 코드 import sys, math read = sys.stdin.readline N, K = map(int, read().rstrip().split()) nums = sorted(map(int, read().rstr..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 요약 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘 (코딩 테스트에서의 정의를 의미하는듯? -> 항상 글로벌 최적을 찾기는 어려울 듯) 그리디 알고리즘 드물게 최적해를 보장하는 경우도 있음 보통 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼음 최적해를 찾을 수 있는 두 가지 조건 탐욕 선택 속성 (Greedy Choice Property) - 앞의 선택이 이후 선택에 영향을 주지 않음 - 즉, 문제 해결 과정 중 substructure마다 독립적인 문제 해결 최적 부분 구조 (Optimal Substructure) - 문제의 최적 해결 방법이 부분 문제에 대한..