TIL/ComputerScience

경우의 수 - 합의 법칙, 곱의 법칙 경우의 수란? 어떤 사건(일)이 일어날 수 있는 경우의 가짓수를 수로 표현한 것이다. 위키백과 경우의 수를 구하는 방법이 여러개가 있지만, 이번에는 곱의 법칙과 합의 법칙에 대해서만 알아보도록 하겠습니다. 알고리즘 문제를 풀때 알아둔다면 쉽게 공식을 통해 풀수 있습니다. 순열과 조합은 아래의 링크에서 확인해주세요. Permutation Algorithm(순열 알고리즘) & Combination Algorithm(조합 알고리즘) 합의 법칙 두 사건 A,B가 동시에 일어나지 않을 때, 사건 A와 사건 B가 일어나는 경우의 수는 각각 m, n이면 사건 A 또는 사건 B가 일어나는 경우는 m+n이다. 예시 예를들어 캡모자가 3개가 있고 비니모자가 3개가 있을때 착용할 수 있..
응집도(Cohesion) vs 결합도(Coupling) 서론 OPP에서는 응집도는 높히고 결합도는 낮춰야 한다는 말을 많이 하게 된다. 그렇다면 실제 응집도는 무엇이고 결합도는 무엇일까? 응집도(Cohesion)란? 하나의 모듈이 하나의 기능을 수행하는 요소들간의 연관성 척도 독립적인 모듈이 되기 위해서는 응집도가 강해야 한다. 응집도가 낮은 클래스의 문제점 이해하기 힘들고 따로 재사용하기 힘들며 유지보수하기 힘들고 다른 클래스의 변화에 민감하게 된다. 응집도가 높은 클래스의 특징 단일 책임을 가진 클래스 다른 클래스와 잘 협력하는 클래스 응집도의 종류 우연적 응집도 < 논리적 응집도 < 시간적 응집도 < 절차적 응집도 < 교환적 응집도 < 순차적 응집도 < 기능적 응집도 기능적 응집도(Functiona..
DFS(Depth First Search) VS BFS(Breadth First Search) 탐색 알고리즘이란? 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 각 장점이 서로 연결되어 있는지, 주어진 시간 내에 탐색을 통해 확인하는 알고리즘이다. 그래프란? 그래프는 정점과 간선으로 구성된, 한정된 자료구조를 의미한다. 각각의 지점을 정점이라고 하고, 정점과 정점의 연결을 간선이라고 한다. DFS(Depth First Search) - 깊이 우선 탐색 가장 직관적이고 구현하기 쉬운 탐색 방법 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 현재 정점과 연결된 정점들을 하나씩 갈 수 있는지 검사하고, 특정 정점으로 갈 수 있다면 ..
1부터 100까지 더하는 효율적인 방법 찾기 서론 간단하게 1 ~ 100까지 더해 결과를 보여주는 코드를 작성해보려고 한다. for문을 맨 처음 배우게 되면 하게 되는 코드이지만, 좀 더 효율적으로 할 수 있는 방법을 같이 설명하고자 한다. 기본적인 방법 int sum = 0; for (int i = 1; i x+y);효율적인 방법 - 가우스 조금만 생각해보자. 예를들어 1 ~ 10까지 있다고 해보자. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1 + 10 = 11 2 + 9 = 11 .... 5 + 6 = 11 즉, 앞에서 순차적으로, 뒤에서 순차적으로 두 값을 더하게 되면 같은 값이 나오게 되는걸 확인할 수 있다. 이에 맞춰 코드를 작성해보면 아래와 같이 나오게 된다. int sum = 0..
Permutation Algorithm(순열 알고리즘) & Combination Algorithm(조합 알고리즘) 전체적인 코드는 Java코드로 작성합니다. 순열 알고리즘이란? 수학에서 순열(Permutation) 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 순열은 정의역과 공역이 같은 일대일 대응이다. n개의 원소의 순서를 뒤섞는 순열의 개수는 n의 계승 n!와 같다. 즉, n 이하의 양의 정수들을 곱한 값이다. -위키피디아 공식(nPr) 서로 다른 n개중에 r개를 선택하는 경우의 수 모든 경우의 수를 계산하는 완전 탐색에서 사용하는 알고리즘입니다. 순서 n개에 대한 모든 경우의 수를 구하는 것은 n!로 구하기 쉽습니다. 예를들어 {1, 2, 3}이 있다고 했을때 가능한..
Greedy Algorithms(탐욕 알고리즘)Greedy Algorithms(탐욕 알고리즘)문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식위의 사진에서 큰 요소를 찾을때 분기마다 제일 큰 값을 찾아 최종 해답을 찾아 나갈때 결과는 12이다. 실제는 99가 가장 크다. 이처럼 문제해결에서 최적 해답을 찾지 못한다.즉, 순간 순간 마다 최선의 결정에 전체 문제의 최선의 해결책이 되지는 않는다.위와 같은 단점이 있다만 가장 큰 장점은 속도이다. 위의 문제를 완전탐색으로 풀었다면 7개를 모두 확인했어야 하지만, 실제 Greedy를 사용하면 3개만 확인하면 된다는 장점이 있다.따라서 이 방법이 몇몇 문제에서 최적화를 빠르게 산출해낼..
피보나치 수 알고리즘 피보나치 수열이란? 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열 위키백과 피보나치 수 F(n)는 다음과 같은 초기값 및 점화식 으로 정의되는 수열이다. 0번째 항부터 시작할 경우 다음과 같이 정의된다. 즉 아래와 같이 정의할 수 있다. fibo(n) = n == 0 || n == 1 ? n : fibo(n-1) + fibo(n-2) 5가지의 알고리즘 코드들은 모두 자바로 작성할 예정입니다. 기본 재귀적 풀이 가장 구현하기 쉬운 풀이입니다. 가장 큰 단점은 시간복잡도 인데요. 함수가 한 번 호출되면 다시 두 번 호출 되기 때문에 지수적으로 증가하여 O(2^n)이 됩니다. public static int fibo(final int n) { if (n >= ..
힙(heap)알고리즘 이란? 서론 자료구조로 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조다. 여러 개의 값들 중 최댓값, 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙의 종류 최대 힙 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 부모 노드 ≥ 자식노드 최소 힙 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 부모 노드 ≤ 자식노드 힙의 구현 힙을 저장하는 표준적인 자료구조는 배열 구현을 쉽게 하기 위해 첫번째 인덱스는 사용되지 않는다. 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. 힙에서의 부모 노드와 자식 노드의 관계..
Stack vs Queue 코딩에 대한 설명은 Java로 합니다. 따라서 메서드들이 모두 Java 기반인 걸 감안해주시면 감사하겠습니다. 선형구조(Linear Structure) 데이터들이 일렬로 저장되어 있는 형태입니다. 일렬로 저장하는 방식은 리스트와 각 데이터가 다음 데이터의 위치를 가지는 연결 리스트 두 가지 방식이 있습니다. 일렬로 쭉 저장되어 있는 데이터를 사용하는 방법은 리스트와 연결 리스트 외에 사용 방법에 따라 스택, 큐, 데크가 추가됩니다. Stack 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조 즉, 가장 최근에(마지막에) 스택에 추가한 항목이 가장 먼저 제거될 항목이다. Stack의 연산 pop() : 스택에서 가장 위에 있는 ..
Seyun(Marco)
'TIL/ComputerScience' 카테고리의 글 목록