Rosy's Artificial Intelligence Blog

Heap 힙 자료구조 힙이란? 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로함 배열에 데이터를 넣고, 최대값과 최솟값을 빠르게 찾기 위해서는 O(n)이 걸리지만, 힙에 데이터를 넣고 최댓값과 최솟값을 찾으면 O(logn)이 걸림 힙 property? 최소 힙? 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙? 부모 노드의 키 값이 자식 노드의 키값보다 항상 큰 힙 -> 이러한 속성으로 힙에서는 가장 낮거나 높은 우선순위를 가지는 노드가 항상 루트에 오게됨 -> 이를 통해 우선순위큐와 같은 추상적 자료형을 구현할 수 있음 힙 함수 활용하기 heapq.heappush(heap, item): item을 heap에 추가 heapq...

그래프 최단경로 - 각 간선의 가중치 합이 최소가 되는 두 정점 사이의 경로를 찾는 문제 - (Wiki) 가장 짧은 경로에서 두 꼭짓점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제이다. 예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제 알고리즘종류 (1) 다익스트라 : 단일-쌍, 단일-출발, 단일-도착 최단 경로 문제 (2) 벨먼-포트 알고리즘 : 변의 가중치가 음수라면 단일 출발 문제 (3) A* 탐색 알고리즘 : 탐색 속도를 높히기 위한 휴리스틱 방법을 사용하며, 단일-쌍 최단 경로 문제를 풀 수 있음 (4) 플로이드-와셜 알고리즘 : 전체-쌍 최단 경로 문제를 풀 수 있음 17. Letter..

정렬 1. 병합정렬 2. 퀵정렬 56. Merge Intervals 75. Sort Colors 147. Insertion Sort List * 삽입 정렬? 정렬을 해야할 대상, 정렬을 끝낸 대상 -> 두 그룹으로 나누어 진행 * cur -> 정렬을 끝낸 연결 리스트 추가, 이미 정렬을 끝냈기 때문에 * parent -> 계속 그 위치에 두어 사실상 루트를 가리키게 함 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def insertionSortList(self, head: Optional[..

1. Queue - 큐 메모리구조? 선입선출을 따르는 자료구조 - 가장 먼저 저장된 데이터(push)가 가장 먼저 인출(pop)되는 구조 2. Stack - 먼저 들어온 데이터가 나중에 나가고, 나중에 들어온 데이터는 먼저 나가는 구조의 컬렉션- Push()와 Pop()을 이용 - 후입선출(LIFO) 시멘틱을 따르는 자료 구조 3. Deque - Double-Ended Queue의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는 - 파이썬에서는 데크자료형을 collections모듈에서 deque라는 이름으로 지원 20. Valid Parentheses class Solution: def isValid(self, string: str) -> bool: dic = {"}" : "{", ")" : "(..

해시테이블(Hash Table)? - 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 인덱스 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하여 검색을 빠르게 하기 위한 자료 구조 - 연관 배열 추상 데이터 유형을 구현하는 데이터 구조로서, 키를 값에 매핑할 수 있는 구조 - 해싱(Hashing)? 테이블을 인덱싱하기 위해 해시 함수를 사용하는것 , 정보를 가능한 한 빠르게 저장하고 검색 - 체크섬, 손실압축, 무작위화 함수, 암호 등과도 관련이 깊으며, 때로는 서로 혼용도 됨 - 성능좋은 해시 함수 특징 (1) 해시 함수 값 충돌의 최소화, (2) 쉽고 빠른 연산 (3) 해시 테이블 전체에 해시값이 균일하게 분포 (4) 사용할 키의 모든 정보를 이용하여 해싱 (5) 해시 테이블 사..

Math - LeetCode https://leetcode.com/tag/math/ Math - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 66. Plus One 231. Power of Two - 평가 : 풀었지만 난 너무 normal 하게 품

효율적인 알고리즘 코드 작성하기 - 알고리즘이 수행을 시작하여 결과가 도출될 때까지 실행에 걸리는 시간이 짧고 연산하는 컴퓨터 내의 메모리와 같은 자원을 덜 사용하는 것이 효율적 - 같은 코드이지만 다른 효율성이 나올 수도 있음 --> 이를 개선하기 위해서는 어떠한 자료형을 쓰는가가 중요함 case1) - ArrayList와 LinkedList 추가/ 삭제를 하는 경우? ArrayList느림, LinkedList 빠름 - '' 인덱스 조회를 하는 경우? ArrayList 빠르지만 , LinkedList 느림 시간 복잡도란? - 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것 - 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타냄 - 위의 그래프를 보니.. O..

Depth First Search - 시간을 우선으로 그래프를 탐색하는 알고리즘으로 시작점부터 인접한 정점을 차례대로 방문함 - Stack(FILO) 사용 , 재귀함수 형태로 사용 Breadth-First Search - Queue(FIFO) JAVA_DFS예제 class Main { static String[] vowels = {"A", "E", "I", "O", "U"}; static ArrayList words; public static void createWord(int lev, String str){ words.add(str); for (int i = 0; i < 5 ; i++){ if(lev < 5){ createWord(lev+1, str.concat(vowels[i])); } } } pub..

1. 탐욕 알고리즘(Greedy Algorithm) - 최적회를 구하는데 사용되는 근사적인 방법, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 -> 즉 최종적인 해답에 도달 - 현재 상황에서 가장 좋아 보이는 답을 선택하는 방법 - 각 부분에서 최적을 선택하면 전체에서도 최적이 될 것이라는 가정을 전제로 함 - 선택은 항상 하위 문제에 대한 해답이 나오기 전에 선택됨 대표적인 문제 ex) 배낭채우기문제 최소신장트리(MST, Minimum Spanning Trees) - 신장트리(Spanning Tree) ? 사이클을 형성하지 않고 그래프의 모든 정점이 간선으로 연결되어 있는 것 - 특징 1. 간선의 가중치 합이 최소여야 함 2. n개의 정점을 가지는 그..

[JAVA,C#,Python 코드 비교] 11. 이분탐색 0. 검색알고리즘이란? - 정해진 단위 절차를 반복하면 원하는 결과를 얻을 때 사용하는 것 1. 이분탐색(Binary Search)란? - 정렬 등과 함께 가장 기초인 알고리즘 - 검색 범위를 줄여나가면서 원하는 데이터를 검색하는 알고리즘 - 이진탐색을 위해서는 자료가 순서에 따라 정렬되어 있어야 함 2. 문자열 검색 알고리즘 - 주어진 문자열 에서 찾고자 하는 문자열이 있을 때, 해당 문자열 위치를 찾는 알고리즘 3. KMP 검색 알고리즘 - 문자열 안에서 부분 문자열을 검색할 때 검색에 실패한 위치를 기반으로 비교할 필요가 없는 문자열은 건너뛰고, 다음번 검색위치를 결정하는 알고리즘 4. BM 검색 알고리즘 - 문자열을 데이터에 검색할 때 검색..