본문 바로가기

Etc/Algorithm12

시간 복잡도과 Big-O 표기법, Greedy 시간 복잡도 Big - O 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 효율적인 알고리즘이란 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 말한다. 최선의 경우만 생각하여 로직을 작성하는 것보다, 최악의 경우를 고려해야 문제에 쉽게 대비할 수 있다! Big-O(빅-오): 시간 복잡도가 최악의 경우 Big-Ω(빅-오메가): 최선의 경우 Big-θ(빅-세타): 중간(평균)의 경우 🌿 O(1) constant complexity 입력값이 증가해도 시간이 늘어나지 않는다. 예) 정수를 입력하면 그에 해당하는 인덱스의 배열 요소를 반환하는 메서드 🌿 O(n) linear complexity 입력값이 따라 시간도 같은 비율로 증가한다. O(2n), O(3n.. 2022. 7. 28.
Tree와 Graph | 이진 트리와 이진 탐색 트리(BST: Binary Search Tree) Tree 단방향 그래프로, 계층형 비선형(하나의 데이터 뒤에 여러 데이터가 연결) 구조이다. 루트(Root)를 시작으로 데이터인 노드(Node)들을 서로 간선(edge)으로 연결되어 있으며 무방향이다. 상하 계층 구조로, 부모 노드와 자식 노드가 있다. Graph 여러 개의 점들이 거미줄처럼 서로 복잡하게 연결되어 있는 관계이다. 하나의 점을 정점(vertex)이라고 하고, 하나의 선을 간선(edge)이라고 한다. 🍇 인접 행렬 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로, 2차원 배열의 형태로 나타낸다. graph = [ [0, 1, 1, 1], [0, 0, 1, 0], [0, 0, 0, 0], [0, 0, 1, 0] ] 0번째 노드와 1번째 노드가 연결되어 있다면 0행 1행에 1을 입력한다. .. 2022. 7. 26.
[자료구조] 스택(Stack)과 큐(Queue) 보호되어 있는 글 입니다. 2022. 7. 24.
재귀(Recursive Function) 보호되어 있는 글 입니다. 2022. 7. 21.
정렬 알고리즘 이 글은 동빈나 님의 실전 알고리즘 강좌를 들으며 정리한 글입니다. 선택 정렬 아무렇게나 놓인 데이터 중 가장 작은 데이터의 위치를 가장 앞에 있는 데이터 위치와 바꾼다. 이미 원소를 넣을 자리는 선택되어 있고 이 자리에 놓일 데이터를 찾는다. 정렬되지 않은 데이터 중 최솟값을 찾는다. 이 최솟값과 첫 번째 자리에 있는 데이터의 위치를 서로 바꾼다. 위 작업을 계속 반복한다. 시간 복잡도 O(n²) 반복 10 + 9 + 8 + ... + 1 : 등차수열 10 * (10 + 1) / 2 = 55 → N * (N + 1) / 2 : 컴퓨터에서 N에 엄청 큰 수라는 가정 하에 나누거나 더하는 연산은 의미가 없다 → N * N 비효율적인 알고리즘 중 하나이다 void selectionSort(int[] arr).. 2022. 6. 25.
동적 계획법(DP, Dynamic Programming) 💟 정의 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시킨다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않는다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성된다. 💟 조건 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 중복되는 부분 문제(Overlapping Subproblem) - 동일한 작은 문제를 반복적으로 해결해야 한다. 💟 피보나치 수열 제2항까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수로 정의된다. 제0항은 생략하기도 한다. 단순 재귀 함수로 피보나치 수열을 구현하면 지수 시간 복잡도를 가진다. .. 2021. 11. 12.

티스토리툴바