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) 모든 노드들이..

Stack1 Stack 자료구조 ✔ 스택 구현 시 고려 사항: 리스트를 사용하여 스택을 구현하는 경우 - 장점: 구현이 용이 - 단점: 리스트의 크기를 변경하는 작업은 내부적으로 큰 오버헤드가 발생하는 작업으로 많은 시간을 소요 ✔ 해결 방법 1) 리스트의 크기가 변동되지 않도록 배열처럼 크기를 미리 정해 놓고 사용하는 방법 2) 동적 연결리스트를 이용하여 저장소를 동적으로 할당하여 스택을 구현하는 방법 - 장점: 구현이 용이 - 단점: 리스트로 구현하는 것보다 구현이 복잡함 괄호 검사 1) 괄호의 종류: 대괄호('[', ']'), 중괄호('{', '}'), 소괄호('(', ')') 2) 조건: (1) 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. (2) 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보..

List 2 - 2차원 리스트 2차원 리스트 1) 1차원 리스트를 묶어 놓은 리스트이다. 2) 2차원 이상의 다차원 리스트는 차원에 따라 인덱스를 선언한다. 3) 2차원 리스트의 선언: 세로길이(행의 개수), 가로길이(열의 개수) 를 필요로 한다. 4) 파이썬에서는 데이터 초기화를 통하여 변수 선언과 초기화가 가능하다. 리스트 초기화 # 1차원 리스트 초기화 #1) arr = [0,0,0,0,0] #2) arr = [0] * 5 # res = [0,0,0,0,0] #3) arr = [i for i in range(2,9) if i%2 == 0 ] # res = [2,4,6,8] # 2차원 리스트 초기화 #1) brr = [[1,2,3], [1,2,3], [1,2,3]] #2) brr =[[1,2,3]] ..

List 1 - Brute force, Greedy, 순열, Sort(정렬) 강의 정리(필요하다고 생각되어지는 부분) 문제풀이 정리 Exhaustive Search 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열하고 확인하는 기법을 의미한다. → Brute-force 혹은 Generate-and-Test 기법이라고도 부른다. → 모든 경우의 수를 테스트 한 후 최종 해법을 도출 하므로 수행 속도는 느릴 수 있어도 해답을 찾아내지 못할 확률이 적다. → 주어진 문제를 풀 때, 우선 완전 탐색으로 해답을 도출한 후 성능 개선을 위하여 다른 알고리즘을 사용하여 해답을 확인하는 것이 이상적인 접근 방법이다. 예시 문) Baby Gin 6개의 숫자를 입력 받아 선택된 3개의 숫자가 연속된 숫자(run) 혹..

List 1 강의 정리(필요하다고 생각되어지는 부분) 문제풀이 정리 리스트(List) 1. 시퀀스 자료형(Sequence types) 파이썬(Python)에서는 리스트(List), 튜플(Tuple), range, 문자열(String) 처럼 값이 연속적으로 이어지는 자료형을 시퀀스 자료형(Sequence types)라고 한다. [시퀀스 자료형의 특징] 데이터를 순서대로 하나씩 나열하여 나타낸 데이터 구조이므로 특정 위치의 데이터를 가리킬 수 있다. 시퀀스 자료형으로 만든 객체를 시퀀스 객체라고 하며 시퀀스 객체에 들어있는 각 값을 요소(Element)라고 한다. [시퀀스 자료형의 활용] (1) 특정 값이 있는지 확인 하기 → (값) in (시퀀스 객체) → (값) not in (시퀀스 객체) >>> a =..

힙(Heaps) 힙(Heap) 이란 ? 완전 이진 트리(Complete Binary Tree)로 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다. 힙은 우선순위 큐를 구현하거나, 힙 정렬을 하는 데 사용된다. 루트 노드에 있는 값이 최대값, 혹은 최소값이며, 자식 노드들의 값의 위치는 기본적인 조건만 맞추면 된다. 최대 힙(Max heap) 원소 삭제 1. 루트 노드 제거: → Max heap의 경우 최대 값 제거 → Min heap의 경우 최소 값 제거 2. 트리의 마지막 자리 노드를 임시로 루트 노드 자리에 배치 3. 자식 노드들 과의 값 비교 하며 아래로 이동 → 자식 노드들 중 더 큰 값 기준으로 이동 최대 힙(Max heap) 원소 삭제 - ..