파일 합치기 문제는 인접한 파일을 합치고 합쳐진 파일을 다른 파일과 합쳐나가며 이 파일을 합치는데 필요한 비용을 최소화 하는 문제이다. 이 문제는 동적 계획법으로 풀 수 있다. 이 부분에 대한 개념은 구간에 대한 개념으로 나누어 보면 쉽게 풀 수 있다. 1 ~ n까지의 구간이 있다고 하면 1~n까지의 구간의 합을 최소로 만드는 것은 임의의 j에 대하여
백준 13911 집 구하기 문제는 맥도날드인 vertex에서 거리가 x이하이고 && 스세권의 vertex에서 거리가 y이하인 집을 찾는 문제이다. 단순히 맥도날드인 vertex, 스타벅스인 vertex에서 모두 다익스트라로 거리를 구해 만족하는 집들을 찾아내는 방법을 생각해도 맥도날드 또는 스타벅스의 수가 V-2개 까지 존재 할 수 있으
백준 2661 좋은 수열 문제는 숫자 1,2,3을 이용하여 수열을 만드는 대신 인접한 수열이 동일한 패턴을 가지면 나쁜 수열에 해당되어 이 나쁜 수열이 아니면서 가장 작은 값을 가지는 수열을 찾아내는 문제이다. 예를 들면 12131212라는 수열을 보면 앞의 7자리 1213121까지는 문제가 없는 수열이지만 뒤에 2라는 숫자가 오게되므로 12/12라는
백준 2579 계단 오르기는 전형적인 dp 문제이다. 이 문제에서의 조건은 돌을 올라가는데 연속 3개의 계단을 밟을 수 없고 계단을 오를때는 1점프 혹은 2점프밖에 할 수 없다는 것이다. 그리고 마지막 계단에 왔을 때 밟아온 계단의 점수를 최대화 하는 것이 문제이다. 이 문제의 핵심은 연속 3개의 계단을 밟을 수 없다는 것이다. 즉 1 2 3 4 라는
HashTable 또는 HashMap이란 키값을 이용하여 값을 저장하는 구조로 키값을 해시함수에 넣어 인덱스로 변환한 후 테이블에 접근해 저장하는 자료구조이다. 해시테이블은 해시함수를 통해 테이블의 인덱스를 계산하고 이 값을 통해 테이블에 직접 접근하기 때문에 O(1)의 빠른 접근시간을 가지고 있다. 위 그림을 보면 왼쪽에 사람의 이름에 해당하는
DisJointSet은 집합을 나타낼 수 있는 간단한 자료구조이다. 집합은 어떠한 원소들이 하나의 공통 요소에 의해 묶여 있다는 것을 말한다. 위의 그림을 보면 p q r s는 X라는 요소에 묶여 있고 1 2 3 4 5 는 Y라는 요소에 묶여 있다. 즉 이를 구현하기 위해 생각해보면 각 원소들은 X나 Y라는 요소를 가리키고 있다고 생각하면 편하게 된다.
우선순위 큐는 Heap의 구조를 이용해 정렬을 수행하는 이진 트리 구조이다. Heap은 원소를 삽입시 가장 큰 원소가 루트 노드에 오도록 노드의 위치를 재배열한다. 이 재배열을 하는 과정은 매번 O(logn)의 시간복잡도를 가지게 된다. 우선순위 큐를 구현하면서 가장 큰 두가지의 기능인 Push와 Pop의 기능을 생각해보자. Push 연산을 하게 되
Stack은 Last In-First Out의 자료구조로 가장 나중에 들어온 원소가 가장 먼저 나오게되는 자료구조이다. Stack은 top이라는 포인터 변수를 두어서 push, pop하며 이 top포인터를 조절하도록 구현된다. Stack 자료구조는 주로 재귀 호출에 주로 사용되게 되고 재귀 호출로 불린 함수는 가장 나중에 불린 함수가 가장 먼저 실행되
Queue는 First in First out의 자료구조로 가장 먼저 들어온 원소가 가장 먼저나가는 선입선출 구조이다. 순서대로 처리해야 할 일을 큐에 집어 넣고 처리할 때 주로 사용되며 알고리즘에서 BFS를 주로 큐를 이용해 구현한다. 12345678910111213141516171819202122232425262728293031323334353637
Linked List는 노드 들간의 연결된 포인터들로 구성되는 자료구조이다. 배열과 같이 원소가 선형으로 저장된다는 특성이 있지만 배열과는 달리 중간에 원소의 삽입 삭제가 가능하고 중간에 있는 원소에 접근하기 위해서는 Head에서부터 순차적으로 접근해서 찾는 방식을 취할 수 밖에 없다. 배열과 Linked List는 다음과 같은 차이점을 가지고 있다.