O'bin and the Chocolate Factory

링크>https://www.acmicpc.net/problem/15686 15686번: 치킨 배달크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸www.acmicpc.net    sol1) itertools.combinations 사용12345678910111213141516171819202122232425262728293031323334from itertools import combinations # 입력n, m = map(int, input().split())town = [list(map(int, input().split())) for _ ..

링크>https://www.acmicpc.net/problem/2805  12345678910111213141516171819n, m = map(int, input().split())trees = list(map(int, input().split())) start, end = 1, max(trees) while start = end:    mid = (start + end) // 2     log_sum = 0     # 현재 높이에서 벌목 나무 합    for i in trees:        if i >= mid:            log_sum += i - mid        if log_sum >= m:        start = mid + 1    else:        end = mid -1..

링크>https://www.acmicpc.net/problem/4358 12345678910111213141516171819import sysfrom collections import defaultdictfrom decimal import Decimal, ROUND_HALF_UPinput = sys.stdin.readline trees = defaultdict(int) while True:    tree = input().rstrip()     # 입력값이 더 없으면 입력 종료    if tree == '':        break        trees[tree] += 1 for i in sorted(trees):    v = Decimal(f'{trees.get(i) / sum(trees.values..

링크>https://www.acmicpc.net/problem/1074   12345678910""" 재귀 풀이 """n, r, c = map(int, input().split()) def recursive(n, r, c):    if n == 0:        return 0    cur_cnt = 2 * (r % 2) + (c % 2)    return cur_cnt + 4 * recursive(n-1, int(r/2), int(c/2)) print(recursive(n, r, c))Colored by Color Scriptercs 분할 정복 문제풀이의 기본 원리와 재귀를 활용하면 짧은 코드로 풀 수 있는 문제다.

링크>https://www.acmicpc.net/problem/1269   sol 1) 대칭 차집합 연산자 사용123456a, b = map(int, input().split()) set_a = set(map(int, input().split()))set_b = set(map(int, input().split())) print(len(set_a ^ set_b))cs 파이썬에서 제공하는 대칭 차집합 연산자 : ^   sol 2) 교집합 연산자 사용12345678a, b = map(int, input().split()) set_a = set(map(int, input().split()))set_b = set(map(int, input().split())) both = len(set_a & set_b) pri..

🔷 zip() 함수란?여러 반복 가능 항목을 병렬로 반복하여 각 항목의 항목이 포함된 튜플을 생성  🔷 zip() 사용 예제123456789101112>> a = [1, 2, 3, 4, 5]>> b = ['a', 'b', 'c']>> c = [0.1, 0.2] >> zip(a,b)zip object at 0x0000025238DFD400> >> list(zip(a,b))[(1, 'a'), (2, 'b'), (3, 'c')] >> list(zip(a, b, c))[(1, 'a', 0.1), (2, 'b', 0.2)]cs  line 5) zip 함수는 제너레이터를 returnline 8) 리스트 형태를 원하면 list()로 감싸기튜플 형태로 return되기 때문에 값 수정 불가능한 immutable 객체..

링크>https://www.acmicpc.net/problem/2630  1234567891011121314151617181920212223242526272829303132333435363738394041import sysinput = sys.stdin.readline # 분할 정복 함수def count_paper(x, y, n):    global white_cnt, blue_cnt    color = paper[x][y]    same_color = True    # 현재 영역의 모든 셀이 같은 색인지 확인    for i in range(x, x+n):        for j in range(y, y+n):            if color != paper[i][j]:                ..

링크>https://www.acmicpc.net/problem/1931  1234567891011121314151617181920212223import sysinput = sys.stdin.readline n = int(input())schedule = [] for _ in range(n):    x, y = map(int, input().split())    schedule.append((x, y)) # schedule을 끝나는 시간 기준으로 정렬schedule.sort(key=lambda x:(x[1], x[0])) last_ending_time = 0cnt = 0 for start, end in schedule:    # 시작 시간이 방금 회의 끝나는 시간 이후면    if start >= last..

트리 구조  순서 트리와 무순서 트리순서 트리(ordered tree) : 형제 노드의 순서 관계 존재무순서 트리(unordered tree) : 형제 노드의 순서 관계 없음 순서 트리의 검색- 너비 우선 검색(BFS, breadth-first search)낮은 레벨부터 왼쪽에서 오른쪽으로 검색, 한 레벨에서 검색 마치면 다음 레벨로 내려감 - 깊이 우선 검색(DFS, depth-first search)리프에 도달할때까지 아래로 내려가면서 검색하는 것을 우선리프에 도달해서 더 이상 검색 대상 없으면 다시 부모 노드로 돌아가 검색 DFS의 스캔 방법전위 순회(preorder) : 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식중위 순회(inorder) : 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식후위 순회(..

링크>https://www.acmicpc.net/problem/11726   12345678n = int(input()) nums = [1,1] for i in range(2, n+1):    nums.append(nums[i-2] + nums[i-1]) print(nums[n] % 10007)cs 문제를 읽어보고 규칙성이 있을 것 같아 몇 개를 그림으로 그려 보니 아래와 같았다.n방법의 수22334558 피보나치 수로 진행되는 것이 보여 간단하게 문제를 해결했다. DP(동적 프로그래밍) 문제였는데, 큰 문제를 작은 문제로 쪼개는 원리가 피보나치에도 적용되어 있었다.    DP를 얼른 공부해야겠다.