코딩기록

피보나치 수열: 첫째, 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열 동적계획법이란?: 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푸는 방법이 때, 하위 문제의 답을 저장하여 중복 연산을 하지 않음. 동적계획법 문제의 특성중복되는 부분문제 : 작은 하위 문제들이 중복되어 나타난다.최적 부분 구조 : 최적해는 부분 문제의 최적해로부터 구할 수 있다. 시간 복잡도간단한 재귀호출 : 계산하는 양이 대략 2배씩 늘어남. 계산양이 많아지면 느려짐동적계획법: 각 항들은 딱 1번씩만 계산이 됨. n번째 항을 구하기 위해선 n만큼만 시간을 들이면 됨. 공간 복잡도: 하위 문제들의 답을 저장해놓기 때문에 하위 문제의 수만큼 저장공간 필요 동적계획법을 구현하는 테크닉         점화식   ..

알고리즘이란?: 계산을 통하여 해결할 수 있는 문제를 해결하는 방법  알고리즘 특징유한성명확성입력출력효과성 재귀호출이란?: 함수가 자기 자신을 호출 수학적 귀납법 = 재귀적 증명법: 명제 P(n)을 다음과 같이 증명하는 방법N = 1일 때 성립함을 보인다.P(k)가 성립한다고 가정할 때, P(k+1)이 성립함을 보인다.따라서 모든 자연수 n에 대하여 P(n)이 성립한다.예시) 퀵정렬: 재귀호출을 이용한 대표적인 정렬예시) 4를 기준으로 작은수는 왼쪽 큰수는 오른쪽  재귀함수 디자인재귀함수를디자인 하기 위한 세가지 단계함수의 정의를 명확히 한다.기저 조건에서 함수가 제대로 동작하게 작성한다.함수가 작은 input에 대하여 제대로 동작한다고 가정하고 함수를 완성한다.

우선순위 큐란? : 출력 연산 시 가장 우선순위가 높은 원소를 출력한다. 📌 단순하게 생각해보기 ❗ 높은 숫자가 우선순위라고 가정함. = 출력값의 빈자리는 당겨짐 📌 우선순위 큐를 단순한 접근 방법으로 구현한 경우 - 입력 : O(1) - 출력 : O(n) 우선순위가 가장 높은 원소를 찾는 과정과, 원소 제거가 비효율적임. 힙 : 최솟값 또는 최댓값을 빠르게 찾기 위해 고안된 완전 이진 트리 최대 힙 : 부모 노드는 항상 자식 노드보다 큰 값을 갖고 있음. 최소 힙 : 부모 노드는 항상 자식 노드보다 작은 값을 갖고 있음. import heapq 파이썬의 heapq 모듈로 최소 힙 사용 📌 최대 값이 필요한 경우 값을 저장할 때 -1을 곱한 값을 저장하면 됨. -1을 곱함으로서 최댓값과 최솝값이 반전된다..

트리의 표현 방법 : 이진 트리의 각 노드는 왼쪽 또는 오른쪽 자식을 갖고 있으므로 위와 같이 표현 가능. **** 완전 이진 트리의 경우 배열로 간단하게 구현 **** 각 정점에 순서대로 번호를 붙일 수 있다. 어떤 정점의 번호가 n이면 왼쪽 자식은 2n, 오른 쪽 자식은 2n + 1 배열로 완전 이진트리 표현 트리 순회하기 트리의 모든 노드를 방문하는 순서 트리에 들어있는 자료에 접근하기 위해 순회를 해야함. 비선형 구조 트리는 정해진 순서가 존재하지 않는다. DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 방문 순서로 두가지가 있음. DFS 종류 전위 순회 중위 순회 후위 순회 DFS는 재귀호출을 사용하는 알고리즘으로, 트리의 재귀적 특성을 알아야함. 스택을 이용한다고 볼 수 있음. 서브 트리 ..

정렬된 상태를 유지하는 배열의 시간 복잡도 📌 임의의 자료들을 담고 있는 자료구조 A가 있다고 가정할 때, A는 항상 정렬된 상태를 유지해야 한다. 만약 A가 배열이라면 자료의 추가, 삭제, 탐색은 다음과 같다. 정렬된 상태를 유지하는 배열의 추가와 삭제 연산은 O(n)의 시간 복잡도를 가진다. 이진 탐색을 이용하면 정렬된 배열 내에서으 자료 탐색을 o(logn)만에 수행할 수 있다. 📌 이진 탐색 정렬된 배열의 중간값과 찾는 값의 크기를 비교하고 중간값보다 작은 경우에는 중간값을 기준으로 좌측, 중간값보다 큰 경우에는 우측을 대상으로 다시 탐색 ex) 상대방이 생각하고 있는 숫자 맞추기(업 다운 게임) : o(log100) = 6.64…이므로 숫자 맞히기까지 걸리는 횟수로 최악의 경우 7회임 📌 이진 ..

트리 : 트리는 그래프의 특수한 형태 중 하나 그래프 정점과 간선으로 이루어져 있는 자료구조간선 - 정점 간의 관계를 나타냄 정점 - 자료, 상태 등 뭔가를 담고 있음. (노드라고도 표현) 어떤 정점에서 간선을 통해 다른 정점으로 이동할 수 있음. 다른 정점으로 이동하기 위해 거치는 모든 정점을 경로라고 함. 정점 4에서 정점 6으로 이동하는 경로들 중 하나는 4→5→3→6이 될 수 있음. - 그래프의 간선은 방향이 있을 수도, 없을 수도 있다. - 방향이 있는 간선이 있는 그래프를 유향 그래프 라고 함. - 처음시작한 정점으로 다시 돌아오는 경로를 ‘사이클’ 이라고 함. - 3 → 6 → 7 → 3 은 사이클 트리 : 그래프 중 특별한 성질을 갖는 그래프를 트리라고 함. = 사이클을 갖지 않는 그래프 ..

주문 처리하기 : 주문을 들어온 순서대로 처리. 단 vip의 주문은 우선 순위가 높음 : 주문에 대한 정보는 (t, d) 형태로 주어지 며 t는 주문이 접수되는 시각, d는 주문을 처리하는 데 드는 시간 요세푸스 순열 1번부터 n번까지 번호를 가진 n명이 있다. 1번부터 순서대로 세었을 때 k번째 사람을 원에서 제거 제거된 사람의 다음 사람부터 k번째 사람을 원에서 또 제거 ..반복 제거된 사람들의 번호를 순서대로 나열한 것을 요세푸스 순열이라고 함. 💡 요세푸스 순열 과정 💡 원을 k - 1번 반시계 방향으로 회전 시켰을 때 12시 위치에 있는 사람이 제거되는 걸로 바꾸기 12시에 있는 사람을 시작으로 보고, 1번부터 n번까지 큐에 저장. 큐에 저장된 자료가 모두 제거될 때까지 아래 작업 반복 (a) ..

올바른 괄호인지 판단하기 :짝이 맞는 지 확인하기 각 괄호를 하나씩 처리하기 괄호 문자열 특징 알아보기 특징 나중에 등장한 여는 괄호는 항상 먼저 등장한 여는 괄호보다 먼저 완성 닫히지 않은 괄호가 존재하면 올바르지 않음. 여는 괄호가 남김 없이 모두 완성되어야함. 올바른 괄호인지 판단하기 - 예시 괄호를 처음부터 하나씩 검토하기 여는 괄호라면 스택에 넣고, 닫는 괄호라면 스택에서 하나 제거 괄호 문자열을 처리한 결과에 따라 값 반환= (b) (a)가 아니거나, 스택이 비어있는 상태에서 닫는 괄호가 입력되었다면 올바른 괄호가 아님. = (a) 괄호 문자열을 모두 처리하고 나서 스택이 비어있다면 올바른 괄호 계산 순서 정하기 입력되는 닫는 괄호와 대응하는 여는 괄호를 찾기 스택에 저장하는 값을 ‘여는 괄호..

스택, 큐의 개념 대표적인 자료구조의 예시 선형구조 - 스택, 큐 : 자료가 순서를 가지고 연속되어 있음. 비선형 구조 - 트리, 그래프 : 선형 구조에 해당하지 않는 자료구조 스택 : 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조 스택이 지원하는 연산목록 -push : 자료 넣기 -pop : 자료 빼기 -top : 가장 위에 있는 자료 반환 -empty : 스택 비어있는지 확인 스택 과정 : 나중에 들어간 자료가 먼저 출력되서 후입선출 자료구조라고 함. 큐 : 입구와 출구가 각각 한 쪽 끝에 존재 큐가 지원하는 연산 목록 -push : 자료 넣기 -pop : 자료 빼기 -front : 가장 앞의 자료 반환 -back : 가장 뒤의 자료 반환 -empty : 큐가 비어있는지 반환 : 배열을 이용하여 구..

자료구조는 왜 공부해야하냐!! : 프로그램의 의도에 맞는 자료구조를 사용하여 효율적인 성능으로 구현하기 위해 해시 테이블 : 각 데이터(value)를 고유한 key에 대응하도록 저장하는 개념 좌) key 10101 데려와라! (ex_1학년 1반 1번 학생은 누구냐!) 우) value 데려옴 (ex_ 이름 엘리스, 성적은 100…) / 각각의 고유한 겹치지 않는 key에 대해서 데이터를 묶어줌. key가 정수이고 value 역시 정수인 Key-Value Store를 구현해보자 Key-Value쌍을 입력하는 연산은 put, 특정 Key의 Value를 조회하는 연산은 get이라고 정의 배열의 index를 key로 이용하기 배열에 value를 저장하고, 배열의 인덱스를 key로 이용하는 방식으로 구현해보자! 장..