O'bin and the Chocolate Factory

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

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

셸 정렬 단순 삽입 정렬의 장점 + 단점 보완한 더 빠른 정렬 알고리즘 단순 삽입 정렬 장점 : 이미 정렬을 마쳤거나 끝나가는 상태에서 매우 빠른 속도 단점 : 삽입할 위치가 멀면 이동 횟수가 많아짐 정렬횟수는 증가하나, 전체적으로 원소의 이동 횟수가 줄어 효율적 서로 h 만큼 떨어진 원소를 꺼내 그룹으로 만들고 그룹별로 정렬 = h-정렬 ex) 4-정렬 -> 2-정렬 -> 1-정렬 순으로 실행 1 2 3 4 5 6 7 8 9 10 11 12 def shell_sort(a: MutableSequence) -> None: n = len(a) h = n // 2 while h > 0: for i in range(h, n): j = i - h tmp = a[i] while j >= 0 and a[j] > tm..

~ 목차 ~ 정렬 알고리즘 버블 정렬 버블 정렬 버블 정렬 개선 1 - 교환 발생하지 않는 경우 정렬 중단 버블 정렬 개선 2 - 이미 정렬된 원소는 비교/교환 범위에서 제외 버블 정렬 개선 3 - shaker sort 단순 선택 정렬 단순 삽입 정렬 정렬 알고리즘 - 안정적인 정렬 알고리즘 vs 안정적이지 않은 정렬 알고리즘 값이 같은 원소의 순서가 정렬 후에도 유지되는지 여부에 따라 결정 -> 유지 : 안정적 -> 유지 보장 x : 안정적 x - 내부 정렬 vs 외부 정렬 정렬할 데이터를 하나의 배열에 저장할 수 있는지 여부에 따라 결정 -> 가능 : 내부 정렬 -> 불가능 : 외부 정렬 - 버블, 단순 선택, 단순 삽입 정렬 시간복잡도 모두 O(n^2)로 프로그램 효율 좋지 X 버블 정렬(bubbl..

~ 목차 ~ 해시법 해시 충돌 체인법 오픈 주소법 정렬된 배열에서 원소 추가/삭제 시, 추가/삭제 위치 뒤/앞의 원소들 한칸씩 뒤/앞으로 밀어야 한다 = 복잡도 O(n) 해시법 검색과 데이터 추가/삭제도 효율적으로 수행할 수 있는 방법 해시 값(hash value) : 배열의 키(= 원소의 값) %원소의 개수 해시 함수(hash function) : 키->해시값 과정 해시 테이블(hash table) : 해시값을 인덱스로 하여 원소를 새로 저장한 배열 버킷(bucket) : 해시 테이블에서 만들어진 원소 해시 충돌 키와 해시값은 일반적으로 n:1 관계 해시 충돌 : 저장할 버킷이 중복되는 현상 해시 충돌 대처법 체인법 : 해시값이 같은 원소 연결리스트로 관리 오픈 주소법 : 빈 버킷을 찾을때까지 해시 반..

이진 검색 정렬된 배열에서 효율적으로 검색할 수 있는 알고리즘, 선형 검색보다 빠름 배열의 중앙을 기준으로 검색값과 비교해서 대소에 따라 검색 범위를 절반씩 줄이는 알고리즘 시간복잡도 O(log n) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 # 이진 검색 알고리즘 from typing import Any, Sequence """시퀀스 a에서 key와 일치하는 원소 이진 검색""" def bin_search(a: Sequence, key: Any) -> int: high = 0 # 검색 범위 맨 앞 원소 index lo..

- 배열 검색방법 중 가장 기본 - 직선 배열에서 검색하는 경우에 원하는 데이터를 찾을때까지 맨 앞부터 순서대로 검색하는 알고리즘 목차 선형 검색의 종료 조건 보초법 1. 선형 검색의 종료 조건 2. 보초법(sentinel method) 선형검색의 종료 조건 검사 비용 감소 방법 원본 데이터 맨 끝에 검색할 값(보초)를 추가 종료 조건 1번이 필요 없으므로 판단 횟수 반으로 감소 스캔 종료 시 찾은 데이터가 원본 데이터인지 보초인지 구별 필요 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 from typing import Any, Sequence import copy """ 시퀀스 seq에서 key와 ..

탐욕법(Greedy Algorithm) 매 순간 최선의 경우만 선택 -> 모든 경우 확인하지 않아 완전탐색보다 빠름 다른 경우는 고려하지 않음 -> 그리디로 풀면 반드시 틀리는 문제 존재 반례가 없는지 신중히 고민해야함 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 ..

브루트 포스(Brute Force) 시간 제한에 걸리지 않을 것 같거나, 풀이 방법이 바로 떠오르지 않는 문제의 경우 완전탐색으로 풀이를 시작하는 것도 방법 순열(permutation) 모든 경우의 수를 순서대로 살펴볼 때 용이 1 2 3 4 5 6 from itertools import permutations v = [0,1,2,3] for i in permutations(v,4): print(i) cs 조합(combination) 배열에서 특정 n개를 뽑아야 하는 경우(순서 상관 x) 1 2 3 4 5 6 from itertools import combinations v = [0,1,2,3] for i in combinations(v,2): print(i) cs

배열 - 배열 탐색 속도 : O(1) 배열은 임의접근(random access)를 통해 빠르게 탐색 가능 => 탐색 속도 O(1) ex) arr[2]에 접근 위해서는 => arr 배열 시작 주소 + 2(인덱스)*4byte(int 크기) = arr[2]의 메모리 주소값 - 배열 삽입/삭제 속도 : O(N) 삽입/삭제는 O(N)으로 탐색보다 느린데 왜냐하면 삽입/삭제를 위해서는 나머지 인덱스의 값들을 움직여야 하기 때문에 최소 0개~최대 N개를 미뤄야 하므로 시간복잡도가 O(N) 연결리스트(Linked List) - 연결리스트 탐색 속도 : O(N) 연결리스트는 배열과 달리 임의접근 불가 n번째 인덱스에 가기 위해서는 n개의 노드를 거쳐야 하므로 O(N)으로 탐색 속도 느림 - 연결리스트 삽입/삭제 속도 :..