알고리즘 개념(Concept)
[알고리즘,개념,조합] 이항계수, 조합의 수
https://dailymapins.tistory.com/246 [백준/11050/파이썬] 이항 계수 1 https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net Problem 자연수 N과 정수 K가 주어졌을 때, 이항.. dailymapins.tistory.com 제 글 이항계수 1번 글에 있는 개념을 정리한 글입니다 :) 이항계수(Binomial coefficient) 원래의 정의는 , (X+Y)^n과 같이 어떤 합의 꼴의 거듭제곱 식에서 계수가 어떻게 나오는지에 대해서 , 정리한 일종의 규칙이다. 예를들어, (x+y)^2 ..
[알고리즘/개념/그래프] 위상 정렬(Topological Sort)
위상정렬 정렬 알고리즘 중 하나로, 순서가 정해져 있는 작업을 차례대로 수행해야 할 때, 사용할 수 있는 알고리즘 입니다. 위상정렬의 현실세계에서의 예시를 들어보겠습니다. 돈까스를 만든다고 생각을 했을 때, 아래와 같은 순서로 만들 수 있습니다. 1 -> 2 ->4 ->3 ->5 ->6 일반적으로 생각하면, 튀김재료의 준비는 언제 하든 별로 상관이 없는 행동입니다. 하지만, 튀김 재료가 준비되지 않을 상태에서, 튀김옷을 입혀줄 순 없기 때문에, Node 사이의 관계에서 특정 순서가 정해집니다. Feedback arc set 과같은 랭킹시스템에 이용이 된다는데, 한번 찾아봐야겠다. 영어로 되어있는 자료밖에 없어서 시간이 좀 걸릴거 같다. 위상정렬의 조건 위상정렬은 기본적으로, DAG (Directed Ac..
[알고리즘/DP/개념] 팰린드롬
Panlindrom 똑바로 읽으나 , 거꾸로 읽으나 똑같은 글자를 Panlindrom 우리나라 말로는 회문이라고 한다. 예를들어 , 주황색 방향으로 읽든(정방향) ,파랑색 방향(역방향)으로 읽든 "기러기"로 읽힌다. 팰린드롬이 현실생활에?! 1. 지폐수집 지폐 수집계에서는 RADAR라고 부르는데, 일반 화폐보다 조금 더 가치가 있다고 한다. 참고로, 1가지 숫자로만 되어있으면 "솔리드"라고 부르는데, "9999999"로 되어있는 지폐가 있다면 보존을 잘 해놓자. 약 100만원의 이상의 가치를 가지고 있다고 한다. 2. 염기서열 생명과학에서 DNA가 이루는 염기서열을 분석할 때, 특정 염기배열을 나타내는 개념으로 쓰인다고 합니다.( 팰린드롬 확인하기 팰린드롬을 확인하는 제일 직관적인 방법은, 문자열을 뒤집..
[알고리즘/개념/그래프] 크루스칼 알고리즘(KrusKal Algorithm)
개념 MST(Minnimal Spanning Tree)를 알아내는 알고리즘 중 하나로, Graph를 탐사하는 방법 중 하나이기도 합니다. Graph를 탐사하는 과정을 보면, 모든 정점들을 가장 적은 비용으로 연결하기 위해서 사용되는 알고리즘입니다. MST(Minimal Spanning Tree) Minimal Spanning Tree는 최소 신장 트리라고도 합니다. Spanning Tree가 뭔지 수학적 정의도 있고, 말로 정의하는 것도 좋지만, 그림으로써 먼저 이해하는게 좋습니다. 아래와 같은 그래프가 있다고 합시다. 위 그래프의 Spanning Tree 위의 그림들을 먼저 보고, 하나씩 특징들을 생각해봅시다. Spanning Tree 모든 노드를 사이클 없이 방문하는 Tree Tree 이기 때문에, ..
[알고리즘/개념/그래프] Dijkstra 최단경로 알고리즘
Graph를 탐색하는 방법은 엄청 많다. 하지만, 그 중에서도 우리에게 의미가 있는 탐색방법이 있는데, 그 중 하나가 최단경로를 알아내는 것이다. 이것은 현실세계에서도 마찬가지이다. 돌아가는 것보단, 그 누구라도 목적지에 빨리 도달 하고 싶을 것이다. Thinking BFS/DFS는 가중치가 있는 그래프에서도 쓸 수 있지만, BFS/DFS는 완전탐색 알고리즘이므로, 결국 모든 노드를 방문해야한다. "어떻게 효율적으로 아래와 같은 가중치가 있는 그래프가 있을 때, 최단 경로를 알아낼 수 있을까" 의 이야기이다. 전제 조건 Graph는 단방향이든, 양방향이든 가중치가 있는 그래프를 대상으로 한다. 각 간선은 음의 가중치가 없어야한다. * 왜 존재하면 안되는지 글의 끝에 설명하겠다. 현실세계라고 생각하자. 출..
[알고리즘,개념] Binary search, Parametric Search
Binary Search "Searching"의 수많은 방법 중에 하나인 Binary Search에 대해서 알아보자! 이분 탐색은 백준에서 문제를 보면, 이게 이분 탐색인지 뭔지 잘 모를때가 많다. 그래서, 개념을 자신의 껄로 완벽하게 만들어야한다. 이분 탐색의 특징 자료가 정렬이 되어있는 상태여야 한다. 모든 탐색 범위를 전부 탐색하지 않는다. Target을 정하고, Target과 중간값의 대소관계에 따라서, 탐색 범위를 줄여간다. 선형 탐색보다 엄 ~ 청 빠른 성능을 자랑한다. (반씩 줄여나가기 때문에, O(logN)) 개념은 정말 간단하다. IF) Targetmid : mid의 오른쪽 탐색 IF) target==mid : 값 반환 하지만, 구현은 헷갈리기 쉬우니까, 정확하게 구현할줄 알아야한다. 탐..
[개념/자료구조/파이썬] Disjoint Set, Union-Find 구조
부제) 크루스칼 알고리즘에 이용되는 자료구조 개념 두 집합 사이에 교집합 원소는 하나도 없고, 모든 집합의 합집합은 전체집합인 자료구조. 수학으로 정의하면, 서로소 관계인 두 집합을 이야기한다. 컴퓨터에서는 파티션이 이러한 구조이다.(C,D,E드라이브들을 다 합치면, 하드디스크 용량이 나오는것처럼) MST를 찾는 크루스칼에 이용되는 자료구조이다. 구현(표현) Union,Find 2가지 연산이 있으며, 각각의 트리(노드)들을 특이한 방식으로 1차원 배열에 mapping한다. 예시를 들어 보겠습니다. 8명이서 각자 조를 짜서, 여행을 간다고 생각해봅시다. 8명의 친구가 있고, 저는 "1"입니다. 저는 4명이 가는 여행이 가장 재밌다고 생각하여, 마음이 잘 맞는 2,3,4 친구와 함께 4명이서 가기로 했습니다..
[알고리즘,개념] 연쇄 행렬 곱셈 문제(CMM)
Chained Matrix Multiplication Problem 행렬의 곱셈에서, 행렬의 곱셈은 결합법칙이 성립한다. (A*B)*C = A*(B*C) 하지만, 행렬 곱셈의 순서에 따라서, 각 원소의 곱셈 횟수가 달라지게 된다. 예시) A=(5,2),B=(2,3),C=(3,6) AB *C : 5*2*3 +5*3*6 = 30+60 = 90 A*BC : 5*2*6+2*3*6 = 60+36 = 96 각 원소의 곱셈 횟수가 가장 작아지도록 하는 곱셈 순서를 구하고 싶다.(최적의 순서) Brute Force 하게 접근하기 모든 경우의 수에 대해서 계산하고,최적의 순서를 선택하면 된다. 예시를 하나씩 해보다보면 알겠지만, 이 문제는 다양하게 해석이 가능하다. 괄호를 씌울 수 있는 경우의 수 - (ABC)(D),(..