본문 바로가기

Etc96

Algorithm with Math - 순열, 조합 GCD/LCM(최대공약수, 최소공배수) 순열/조합 멱집합 순열(permutation)과 조합(Combination) 순열: 요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수. 조합 : 순서에 상관없이 요소 n개 중에 m개를 뽑는 경우의 수. 🎪 카드 뽑기 5장의 카드 중 순서를 고려하고, 혹은 고려하지 않고 3장을 뽑을 때의 경우의 수는? 1. 순열(P ; Permutation) nPɾ = n! / (n - r)! 5 X 4 X 3 = 60가지의 방법 첫 번째 나열하는 카드를 선택하는 방법: 다섯 가지 첫 번째 카드를 나열하고, 두 번째 카드를 선택하는 방법: 네 가지 두 번째 카드를 나열하고, 세 번째 카드를 선택하는 방법: 세 가지 [A, B, D]와 [A, D, B]는 나열하는 순서.. 2022. 7. 30.
Implementation - Simulation, Brute-Force, Binary Search 구현 능력을 보는 대표적인 사례 시뮬레이션: 문제가 요구하는 복잡한 구현 요구 사항을 하나로 빠트리지 않고 코드로 옮긴다 완전 탐색: 모든 경우의 수를 전부 확인하여 문제를 해결한다 완전 탐색 알고리즘 Brute-Force Algorithm, 시행착오 방법론 지능형 전략을 사용하지 않고 컴퓨팅 성능에 의존하여 모든 가능성을 시도한다 (최적의 솔루션이 아니다) · 프로세스 속도를 높이는 데 사용할 수 있는 다른 알고리즘이 없을 때 · 여러 솔루션이 있고 각 솔루션을 확인해야 할 때 한계: 문제 복잡도에 민감하다 🌿 순차 검색 for문을 활용해서 인덱스 0부터 마지막 인덱스까지 차례로 검색 🌿 문열 매칭 길이가 N인 전체 문자열이 M 문자열 패턴을 포함하는가? public boolean BruteForceS.. 2022. 7. 28.
시간 복잡도과 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.

티스토리툴바