DailyStudyNote

파라메트릭 서치(Parametric Search) 파라메트릭 서치(Parametric Search) 파라메트릭 서치(Parametric Search)는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 결정 문제란, '예' 혹은 '아니오'로 답하는 문제를 말한다. '주어진 범위에서 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용한다. 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀 나갈 수 있다. * 이진 탐색 개념 참고 [알고리즘] 이진 탐색(Binary Search, 이분 탐색) 이진 탐색(Binary Search) 이진 탐색(Binary Search) 란? 정렬되어 있는 배열에서 ..

Array1 - 문제풀이 위주 문1: 최빈수 구하기 # 1204. 최빈수 구하기 from collections import Counter T = int(input()) for test_case in range(1, T + 1): n = int(input()) counter_list = Counter(list(map(int, input().split()))) max_v = max(counter_list.values()) for k, v in counter_list.items(): if v == max_v: print(f'#{test_case} {k}') break 풀이: 특정 자료에서 가장 여러 번 나타나는 값을 출력하는 코드이다. 주어진 특정 자료에서 각 원소의 발생 빈도를 확인하기 위하여 Collect..

Tree Tree [Tree의 특징] 1) 한 개 이상의 노드로 이루어진 유한 집합 - 루트(Root): 노드 중 최상위 노드 - 나머지 노드들: n(>=0) 개의 분리 집합 T1....Tn 으로 분리 될 수 있다. 2) 이들 T1...Tn 은 각각 하나의 트리가 되며(재귀적 정의) 루트의 서브 트리(Sub Tree) 라고 한다. [Tree의 구성 요소] 1) 노드 - 트리의 원소 2) 간선 - 노드를 연결하는 선 - 부모 노드와 자식 노드를 연결 3) 차수 - 노드에 연결된 자식 노드의 수 - 트리의 차수: 트리에 있는 노드의 차수들 중 가장 큰 값 - 단말 노드(리프노드): 차수가 0인 노드, 자식 노드가 없는 노드 이진 트리(Binary Tree) [Binary Tree의 특징] 1) 모든 노드들이..

Linked List - 활용 스택(Stack) [스택의 원소: 리스트의 노드] - 스택 내 순서는 연결리스트의 링크를 통해 연결됨 - push: 연결 리스트의 맨 앞에 노드 삽입 - pop: 연결 리스트의 맨 앞 노드 반환/삭제 [변수 top] - 연결 리스트의 맨 앞 노드를 가리킴 - 초기상태: top = None 우선순위 큐(Priority Queue) 1) 우선순위 큐의 구현 - 연결리스트 이용한 우선순위 큐 2) 우선순위 큐의 기본 연산 - 삽입: enQueue - 삭제: deQueue [연결리스트 이용한 우선순위 큐 구현] - 연결리스트를 이용하여 자료 저장 - 원소를 삽입하는 과정에서 리스트 내 노드의 원소들과 비교하여 적절한 위치에 노드를 삽입하는 구조 - 리스트의 가장 앞쪽에 최고 우선순..

Linked List - 정렬 삽입 정렬 자료 배열의 모든 원소들을 앞에서 부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아냄으로써 정렬을 완성한다. [ 삽입 정렬의 정렬과정 ] 1) 정렬할 자료를 두 개의 부분집합 S 와 U로 가정한다. - 부분집합 S: 정렬된 앞부분의 원소들 - 부분집합 U: 아직 정렬되지 않은 나머지 원소들 2) 정렬되지 않은 부분 집합 U의 원소를 하나씩 꺼내며 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다. 3) 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. 4) 부분집합 U가 공집합이 되면 삽입 정렬이 완성된다. ✔ 시간 복잡도: O(n^2) 병합 정렬 여러 개의 정렬된..

연결 리스트(Linked List) 리스트(List) 1) 동적 배열로 작성된 순차 리스트 2) 자료의 삽입, 삭제 연산 - 원소의 이동 작업이 필요하다. 3) 원소의 개수가 많고 삽입, 삭제 연산이 빈번한 작업 - 소요되는 시간이 크게 증가 리스트 복사 # 1. new_list = old_list 주소의 복사, 얕은 복사 # 2. new_list = old_list[:] 슬라이싱(slicing), 깊은 복사 # 3. new_list = [] new_list.extend(old_list) ✔ extend(): 리스트를 추가하는 함수 깊은 복사 # 4. new_list = list(old_list) ✔ list() 깊은 복사 # 5. import copy new_lsit = copy.copy(old_lis..

Queue Queue 의 종류 1) 선형 큐: 간단하고 기본적인 형태이며, 리스트로 구현한다. 2) 원형 큐: 선형에서 발전된 형태이며, 리스트로 구현한다. 3) 연결 큐: 연결리스트 형식으로 구현한다. 4) 우선순위 큐 선형 큐 선형 큐의 특징 1) 1차원 리스트를 이용한 큐 - 큐의 크기 = 리스트의 크기 - front: 저장된 첫 번째 원소의 인덱스 - rear: 저장된 마지막 원소의 인덱스 2) 상태표현 - 초기상태 : front = rear = - 1 - 공백상태: front = rear - 포화상태: rear = n-1 (n: 리스트의 크기, n-1: 리스트의 마지막 인덱스) 원형 큐 1차원 리스트를 사용하되, 논리적으로 리스트의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용한..

Stack2 - 문제풀이 위주 문1: Forth T = int(input()) for test_case in range(1, T + 1): cases = input().split() stack = [] try: for i in range(len(cases)-1): if cases[i].isdigit(): stack.append(int(cases[i])) continue else: a = stack.pop() b = stack.pop() if cases[i] == '+': stack.append(b+a) continue elif cases[i] == '-': stack.append(b-a) elif cases[i] == '*': stack.append(b*a) else: if not b or not a: ..