O'bin and the Chocolate Factory

🔷 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/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를 얼른 공부해야겠다.

🔷 permutationsitertools.permutations(iterable, r)iterable 중에 r개의 요소를 중복 없이 뽑은 순열 🔷 combinationsitertools.combinations(iterable, r)iterable 중에 r개의 요소를 중복 없이 뽑은 조합 🔷 combinations_with_replacementitertools.combinations_with_replacement(iterable, r)iterable 중에 r개의 요소를 중복 허용하여 뽑은 조합  위 세개 함수 사용 예) 12345678910import itertools nums = [1,2,3] print(list(itertools.permutations(nums, 2)))# [(1, 2), (1,..

링크> https://www.acmicpc.net/problem/16953   🔷 sol) bfs를 이용한 목표 값 탐색, 노드 깊이로 연산 횟수 계산123456789101112131415161718from collections import deque MAX = 10 ** 9 def bfs(n):    q = deque([(n, 1)])     # (노드, 변환 횟수)    while q:        v, cnt = q.popleft()        if v == b:            return cnt        for w in [v * 2, (v * 10) + 1]:            if w = MAX:                # cnt + 1 : 자식 노드는 현재 노드보다 깊이 + ..

링크>https://www.acmicpc.net/problem/2468어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.   🔷 sol 1) DFS_재귀(Recursion)123456789101112131415161718192021222324252627282930313233343536import syssys.setrecursionlimit(10 ** 5)input = sys.stdin.readline # 상하좌우 좌표dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1] def dfs(x, y, h, visited):    visited[x][y] = True     for m in range(4):        nx ..

링크>https://www.acmicpc.net/problem/7576  12345678910111213141516171819202122232425262728293031323334353637import sysfrom collections import deque input = sys.stdin.readline def bfs(m, n, ground):    directions = [(-1,0),(1,0),(0,-1),(0,1)]    # 동서남북 방향벡터 정의        # 토마토 위치 = bfs 시작할 위치 저장    q = deque([(i, j) for i in range(m) for j in range(n) if ground[i][j] == 1])        while q:        x, y ..

🔷 그래프 🔹구성정점(node), 간선(edge) 🔹그래프 종류방향 기준무방향(= 양방향) 그래프방향 그래프순환성 기준 순환 그래프 (cyclic graph) - 한군데라도 cycle이 있으면 순환그래프비순환 그래프(acyclic graph) - cycle이 하나도 없으면 비순환 그래프방향성 비순환 그래프(DAG, Directed Acyclic Graph )연결 요소로 이루어진 그래프도 존재  🔷 그래프 표현 방법1. 인접행렬 (Adjacency Matrix) 간선 정보를 0 또는 1로 해서 [출발노드][도착노드]로가는 간선이 존재하면 1, 존재하지 않으면 0으로 표기 무방향(양방향)그래프의 경우 두 노드 간 간선이 두개라고 볼 수 있으므로인접행렬이 대각선 기준으로 대칭 구조 2. 인접리스트(연결..

링크>https://www.acmicpc.net/problem/11659 1234567891011121314151617181920import sysinput = sys.stdin.readdata = input().split()  # 한번에 입력 받기 n, m = map(int, data[0:2]) nums = list(map(int, data[2:n+2])) sums = [0] * (n+1)      # 누적합 저장할 sums 배열 초기화for i in range(1, n+1):    sums[i] = sums[i-1] + nums[i-1] index = n+2results = []for _ in range(m):    a = int(data[index])    b = int(data[index + 1]..