본문 바로가기

Etc/Algorithm53

[Java] 순열 - 새로운 치킨 소스 레시피 보호되어 있는 글 입니다. 2022. 7. 31.
[JAVA] 중복 순열 - RockPaperScissors 보호되어 있는 글 입니다. 2022. 7. 30.
[Algorithm] 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.
[Algorithm] Implementation - Simulation, Brute-Force, Binary Search 구현 능력을 보는 대표적인 사례  시뮬레이션: 문제가 요구하는 복잡한 구현 요구 사항을 하나로 빠트리지 않고 코드로 옮긴다완전 탐색: 모든 경우의 수를 전부 확인하여 문제를 해결한다   완전 탐색 알고리즘Brute-Force Algorithm, 시행착오 방법론  지능형 전략을 사용하지 않고 컴퓨팅 성능에 의존하여 모든 가능성을 시도한다 (최적의 솔루션이 아니다)· 프로세스 속도를 높이는 데 사용할 수 있는 다른 알고리즘이 없을 때· 여러 솔루션이 있고 각 솔루션을 확인해야 할 때한계: 문제 복잡도에 민감하다  🌿 순차 검색for문을 활용해서 인덱스 0부터 마지막 인덱스까지 차례로 검색 🌿 문열 매칭길이가 N인 전체 문자열이 M 문자열 패턴을 포함하는가?public boolean BruteForceSt.. 2022. 7. 28.
[Algorithm] 시간 복잡도과 Big-O 표기법, Greedy 시간 복잡도Big - O 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?  효율적인 알고리즘이란 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 말한다. 최선의 경우만 생각하여 로직을 작성하는 것보다, 최악의 경우를 고려해야 문제에 쉽게 대비할 수 있다!Big-O(빅-오): 시간 복잡도가 최악의 경우Big-Ω(빅-오메가): 최선의 경우Big-θ(빅-세타): 중간(평균)의 경우 🌿 O(1) constant complexity입력값이 증가해도 시간이 늘어나지 않는다.예) 정수를 입력하면 그에 해당하는 인덱스의 배열 요소를 반환하는 메서드 🌿 O(n) linear complexity입력값이 따라 시간도 같은 비율로 증가한다. O(2n), O(3n)이어도.. 2022. 7. 28.
[Algorithm] 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.

티스토리툴바