프로그래밍 & IT/Algorithm 검색 결과

해당 글 7건

자료구조 알고리즘 정리 - Stack / Queue / Deque / Heap

알고리즘 문제를 풀 때, 기본적인 자료구조를 알아야만 풀 수 있는 경우가 많다.자료구조는 컴퓨터가 자료를 처리할 때, 이를 효율적으로 관리하고 구조화시키기 위해 구성하고 처리하는 작업을 의미한다.예를 들어 선입선출의 원리에 따라 먼저 저장된 자료가 먼저 사용되어야 하는 상황에서, Queue를 사용하면 손쉽게 해결할 수 있다. C나 C++, Java 등의 프로그래밍 언어는 기본적인 자료구조에 대한 라이브러리를 제공한다.각 언어에서 제공하는 기본적인 라이브러리를 활용하면 복잡한 자료구조 구현도 가능하다. 컴퓨터가 자료를 처리하게 위해 연구된 수많은 자료구조 중 가장 많이 쓰이고 기본이 되는 Stack, Queue, Deque, Heap 네가지 자료구조에 대해 알아보자. Stack Stack은 FILO(Fir..
프로그래밍 & IT/Algorithm 2017. 3. 20. 21:59

그래프 넓이우선탐색(BFS, Breadth First Search) 알고리즘(java 코드 포함)

알고리즘 문제에서 동적계획법과 함께 단골로 출시되는 것이 그래프 문제이다.그래프 형태의 자료구조로 표현할 수 있는 문제를 해결하기 위한 알고리즘은 여러 가지가 있다.그 중 가장 기본적이면서도 대표적인 알고리즘 기법이 넓이우선탐색(Breadth First Search)과 깊이우선탐색(Depth First Search)이다. 이 중에서 먼저 넓이우선탐색(BFS, Breadth First Search)에 대해 그림으로 알아보고 예제 문제를 자바(java) 코드로 구현해 보자. 위와 같은 형태의 그래프가 있다. 이제 1번부터 시작해서 넓이우선탐색을 통해 모든 정점들을 하나씩 다 방문해 보려고 한다. 넓이 우선 탐색은 처음 시작 정점을 방문한 뒤, 정점에서 인접한 모든 정점들을 우선 방문한다. 방문하지 않은 정점..
프로그래밍 & IT/Algorithm 2017. 3. 10. 23:43

동적계획법(DP) 대표문제2 - ROD CUTTING(막대기 자르기)

동적계획법(Dynamic Programming, DP)는 가장 많이 쓰이는 알고리즘 기법이자 기초이다. 하지만 그만큼 다양한 응용과 아이디어가 필요해서 완벽하게 익히기도 어렵다. 이론은 듣기에 간단하지만 문제에 따라 응용이 매우 어려운 것이다. 때문에 다양한 문제를 풀어보며 직접 익히는 방법밖에는 없다. 특히, 점화식을 세우고 점화식에 따라 DP 해법을 저장하는 배열을 선언하는 연습을 많이 해 봐야 할 것이다. 동적계획법을 사용해 풀 수 있는 대표 문제 중 두번째로 ROD CUTTING(막대기 자르기) 문제에 대해 소개하려고 한다. 문제를 푸는데 사용한 언어는 java 이다. 이 문제를 보기 전에, 동적계획법에 대한 아무런 사전 지식이 없다면 아래 포스팅을 먼저 참고 바란다.[동적계획법 풀이 대한 간략한..
프로그래밍 & IT/Algorithm 2017. 3. 6. 19:42

그래프 알고리즘(Graph Algorithm)의 기초 용어 정리

수많은 알고리즘 문제들이 동적계획법으로 변형하여 해결이 가능한 것으로 알고있다. 하지만, 이를 위해서는 수학적인 직관과 알고리즘 문제에 대한 상당한 숙련이 필요하다. 사실 알고리즘 선수 수준의 숙련도가 아닌 이상 알고리즘 문제를 해결할 때에는 문제를 잘 파악한 뒤 이 문제에 어떤 알고리즘 기법을 사용해야 할지를 결정하는 것이 문제 해결의 80%는 결정한다고 본다. 사실 그래프는 알고리즘 기법이라기 보다는 여러 가지 효율적인 알고리즘을 적용하기 위한 자료구조이다. 알고리즘 문제를 접할 때에도 그래프(Graph)를 사용한 알고리즘 문제 풀이는 동적계획법에 비해 상대적으로 의도를 파악하기 쉬운 자료구조이기 때문에 잘 알아두면 분명 도움이 될 것이다. 그래프의 기초 용어 정리 그래프는 정점과 간선으로 구성하는 ..
프로그래밍 & IT/Algorithm 2017. 3. 1. 02:12

MST(Minimum Spanning Tree) 문제 해결을 위한 크루스칼 알고리즘(Kruskal's Algorithm)

MST(MCST, Minimum Cost Spanning Tree, 최소비용신장트리)는 약어 그대로 그래프에 존재하는 여러 개의 Spanning Tree 중 최소 비용을 가지는 것을 찾는 문제이다. 주로 간선(Edge)의 방향성이 없는 undirected graph에서 모든 Vertex(Node) 들을 방문하는 최소의 비용을 구하는 문제가 해당된다.이 MST 문제를 해결하기 위한 알고리즘은 물론 여러 가지가 있을 수 있지만, 대표적으로 Kruskal's Algorithm(크루스칼 알고리즘)과 Prim Algorithm이 있다. Kruskal's Algorithm은 Merge Sort와 Union-Find를 사용하여 구현하는 알고리즘이고, Prim Algorithm은 Heap을 사용하여 구현하는 알고리즘이..
프로그래밍 & IT/Algorithm 2017. 2. 28. 21:01

동적 계획법 알고리즘 문제풀이 기초와 예제(Assembly-line scheduling)

우선 동적계획법에 대한 기본 설명과 대표적 문제 4개(Assembly-line scheduling, Rod cutting, Lcs, Matrix-chain multiplication)에 대한 소개는 ( http://www.leafcats.com/71 ) 을 참고 바란다. 이 글을 읽기 전 저 링크를 먼저 읽고 접근하는 것이 좋을 것이다. 이번 글에서는 Assembly-line scheduling에 대해 풀어 볼 것이다. 간단하게 요약해 동적계획법이란 복잡한 문제를 푸는 알고리즘의 한 종류로서, 큰 문제를 작은 문제로 나누고 작은 문제를 먼저 해결 한뒤에 결과를 바탕으로 큰 문제의 해답을 찾는 방법이다.피보나치 수열을 예로 들어보자. 피보나치 수열은 아래와 같이 표현할 수 있을 것이다. 하나의 수열 항목을..
프로그래밍 & IT/Algorithm 2017. 2. 22. 18:42

동적계획법(Dynamic Programming)과 대표 알고리즘 기초 소개

동적계획법 동적계획법은 어떠한 문제에 대한 최적해를 얻고자 할 때, 해당 문제에 대해 부분적으로 분할하여 작은 문제를 먼저 해결한 뒤, 각 부분에 대해 최적의 해답을 차례로 구해 가는 알고리즘이다. 말이 조금 어려운데, 전체 큰 해를 구하기 위해서 작은 해를 구한 뒤에 그걸 재활용해서 여기저기서 이용하면서 답을 찾아 가는 기법이다.동적계획법(Dynamic Programming)은 줄여서 DP라고도 부른다. 일반적으로 이름이 붙어진 알고리즘들이 구체적으로 문제를 해결하는 길을 제공하는 알고리즘이라면, 동적계획법은 구체적인 어떤 알고리즘을 지칭한다기보다는 문제를 해결하는 일종의 여러 방법들의 집합과도 같다. 문제를 해결하는 하나의 철학인 것이다. 한가지 큰 문제를 풀기 위해서 그 문제를 작은 문제들의 연장으..
프로그래밍 & IT/Algorithm 2017. 2. 21. 01:23