알고리즘 개념(Concept)
[알고리즘,개념,DP] LIS (Longest Increasing Subsequence)
* 이 글은 구글의 다양한 포스팅을 보고난 뒤, Mapin의 방식으로 정리하는 글 입니다. 다양한 블로그들의 개념 글과 흡사할 수 있습니다. 제일 이해가 잘되었던,블로그 포스팅을 refer에 넣겠습니다. LIS(Longest Increasing Subsequence) 어떤 수열에서, 특정 부분을 지워서 만들어낼 수 있는 증가 부분수열 중 가장 긴 수열 이때, 부분 수열의 숫자들은, 원 배열에서 이어져 있지 않아도 된다. 예를들어, 수열 A={1,4,6,8,3,5,6,7}에서 증가 부분수열은 S1={1,4,6}, S2={4,6,8} 등등이 있을거다. S1,S2...Sn와 같은 증가 부분수열 중 가장 긴 수열을 LIS라고 한다. 이 글에서는 LIS의 길이를 구하는데 초점을 둘거다! Sol 1. Brute F..
[알고리즘,개념] DP(Dynamic Programming)
DP(Dynamic Programming) Dynamic Programming , 컴퓨터에서 이야기하는 Static/Dynamic할 때, 정적/동적의 개념이 아니다. 일반적이지 않게 풀기, 멋있는 방법으로 풀기라고 생각해서, Dynamic Programming이라고 지었다고 한다. 개념은, 문제의 Scale(size)가 너무 커서, 작은 문제의 답을 구하고, 그 답을 통해서, 최종적인 답을 구할 수 있게 되는 형태의 문제들을 DP문제라고 한다. 부분 문제 반복(Overlapping subproblem)과 최적 부분 구조(Optimal Substrcture)를 가지고 있다. DP는 말로 정의내리기가 참 애매한거 같다. 그래서, 난 DP가 나오게된 배경을 알아봤고, 도움이 된 부분이 있어서 , DP의 등장배..
[알고리즘,개념] Backtracking
Backtracking 정의 : 모든 조합의 수(경우의 수)를 살펴본다. 단, 특정 조건이 만족할 때(Promising)만, 그 조합을 본다. - "the algorithm design manual" (1997.스티븐 스키에나) 모든 경우의 수를 찾는 것보다, 경우에 따라, 훨씬 빠를 수 있다(pruning). Promising,Pruning(가지치기) 기법을 이용한다. Promising: 해당 루트가 조건에 맞는지를 검사하는 기법. Pruning : 조건에 맞지 않으면, 포기하고, 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법. 너무나도 유명한 예제 중 하나인, N-Queen 문제를 살펴보면서, Promising의 개념이 뭔지, Pruning의 개념이 뭔지 구체화 시켜보자. N-Queen N..
[알고리즘,개념,활용] 길을 찾자!
이 글은 BFS/DFS에 대한 저의 이해를 기록한 글 입니다. 사람마다 이해하는 방법이 다를 수 있으니, 너그러운 시선으로 봐주세요! 대신, 틀린 부분이 있다면, 거침없이 지적/tackle해주세요 ! 경로 찾기 문제 알고리즘 문제를 풀다보면 , BFS 관련해서 자주 등장하게 되는게 , 길찾기 문제이다. 이 길찾기 문제에 대해서, 하나하나 뜯어볼 생각이다. 왜 BFS,DFS는 경로 찾기 문제에 쓰일까 당연하다. BFS, DFS는 완전 탐색 알고리즘 중, 하나이고 모든 경우의 수를 보는 알고리즘이기 때문에, 답을 못찾을 수가 없다고 말하면 알고리즘을 배우는 의미가 없으니까 , 말해주면 길찾기 문제의 Map을 그래프 관계로 나타낼 수 있고, 이 배열을 하나하나 다 순회하면서 탐색하는것보단, BFS,DFS로 쭊..
[개념/파이썬/알고리즘] BFS(Breadth First Search)
BFS 한 경우에 대한, 모든 가능한 경우의 수를 탐색한다. Queue를 이용한다. 최단거리(최단경로)를 탐색하는 대표적인 알고리즘 중 하나이다. 완전탐색 알고리즘 중 , 하나이다. 방문했던 Node는 방문하지 않는다. Web crawling,SNS,Network broadcasting,grabage collection 등에 이용된다고 합니다. 순서: A->B->C ->D ->E->F ->G ->H ->J -> J -> K BFS는 큐를 사용합니다! Queue를 이용해서, 어떻게 탐색하는지 봅시다. 큐에서도 2가지 동작이 있습니다. popleft: 큐의 왼쪽에서 노드를 꺼냅니다. appendleft:큐의 왼쪽에 노드를 추가합니다. popleft 하면서, 자식 노드들을 추가하면서, 하나하나씩 출력합니다! ..
[개념/파이썬/알고리즘] DFS (Depth First Search)
그래프를 배우게 되면, 제일 처음 배우게되는 일종의 정립되고, 문제에서 아주 자주나오는 스테디셀러인 친구들이 있다. DFS , BFS가 뭔지 살펴보기 전에, DFS,BFS는 완전탐색알고리즘이고, 가능한 수를 전부 다 뒤지는 알고리즘의 일종이다.그래서, 느리지만, 정답을 무적권 찾을수 있다는 기본적인 특성이 있기 때문에, 이건 알고가자. 오목을 한다고 생각해보자! 여러분은 백돌이고, 여러분의 차례이다. 그럼 , 어디를 막을 수 있을까? 생각을 하게 될것이다. 여러분은, 위와 깉이 다양한 경우의 수를 생각하면서, 오목을 할 것이다. 그럼 , 이때, 여러분의 생각의 방식에 따라서, 2가지로 나눌 수 있다. 첫번째. 1가지의 경우에 대해서 생각한 뒤, 그 경우일 때, 일어나는 경우를 계속 생각하는 방법 . 오목..
[개념,그래프] 인접행렬 ,인접리스트 - 그래프를 코드로 !
그래프의 개념은 뭔지 알았으니, 이제 그걸 코드로 구현해보는 연습을 해보자. 2가지 방법이 있는데, 각각의 장/단점은 뭐고, 어떨때 쓰면 이득인지 알아봅시다. 사실 그래프의 종류는 워낙 많아서, 나중에 차근차근 더 살펴보는 걸로 하자. 언어 : Python 1. 인접 행렬 Vertex * Vertex 크기 만큼 행렬을 만들어서, 그 두개의 Vertex가 Edge로 이어져있다면 1 , 아니면 0을 넣어 그래프를 표현하는 방식이다. 인접 행렬로 구현을 할 경우, 그래프(무방향의 한해서) 대각 성분을 기준으로 대칭인 성질을 갖게된다 위의 그래프를 인접행렬로 생각한다면, 옆의 그림과 같이 될것임. 그럼 이걸 코드로 어떻게 구현할까. 보통, 문제에서는 구성하는 정점의 개수(Vertex),간선의 개수(Edge), ..
[자료구조,개념] 그래프, 트리 (graph,tree)
그게 뭔데 컴덕아. Graph (그래프) 비트코인 차트그래프 이런거 아닙니다. 자료구조입니다. 어떤 Node(vertex 또는 정점)와 Node(vertex 또는 정점)의 관계를 나타내는 자료구조입니다. 구성: Vertex(정점),Edge(간선) 표현식: G(V,E) , G=(V,E) 간선이 방향성을 가지면, 방향성 그래프 / 무방향이면, 무방향 그래프 혹은 양방향 그래프 간선에 가중치가 있으면, 가중치 그래프. 순환(Cycle)이 하나라도 있다? => 순환 그래프. 순환이 하나도 없다 => 비순환(Acyclic) 그래프 DAG (Directed Acyclic Graph) => 방향성 비순환 그래프인데, VCS(version control System) ,블록체인, git의 브랜치 등 다양한 곳에 많이 ..