Algorithm 검색 결과

해당 글 11건

[자료구조]Stack 스택 구현(C++)

오늘은 Stack (스택) 에 대해 알아 보겠습니다. 스택역시 Queue 와 마찬가지로 C++에서는 STL 에서 제공되고있습니다. [자료구조]Queue 큐 구현(C++) 오늘은 Queue 큐 자료구조에 대해 알아 보겠습니다. C++에서는 표준 템플릿 라이브러리 STL(Standard Template Library) 로 큐(queue) 를 제공해 줍니다. 때문에 헤더파일에 #include 를 명시해 큐를 사용.. dpdpwl.tistory.com 지난번에 Queue 를 알아보았는데요, 이번에도 Stack 스택에 대해 알아 보고, 직접 스택을 구현해 보도록 하겠습니다. 스택(Stack)스택(Stack) 은 후입선출(Last In First Out) 의 형태를 띄는 자료구조입니다. 나중에 들어간것이 먼저나온다..
Algorithm 2018. 7. 5. 13:42

[자료구조]Queue 큐 구현(C++)

오늘은 Queue 큐 자료구조에 대해 알아 보겠습니다. C++에서는 표준 템플릿 라이브러리 STL(Standard Template Library) 로 큐(queue) 를 제공해 줍니다. 때문에 헤더파일에 #include 를 명시해 큐를 사용 할 수 있습니다. 하지만 STL 을 쓰지않고 직접 C++에서 큐(queue) 를 만들어 보고~ 나서 STL 의 큐 사용법에 대해 알아 보겠습니다. 큐(Queue)먼저 큐(queue) 란, FIFO ( First In First Out ) 선입선출 기본적인 자료구조중 하나로 스택 stack - LIFO(Last In First Out) 과 형제? 입니다. 그림과같이 먼저 들어간것이 먼저나오는 형태의 자료구조 입니다. 그럼 큐를 구현하기 위해서 여러 방법이 사용되는데요,..
Algorithm 2018. 7. 4. 17:30

[Algorithm]동적계획법(다이나믹 프로그래밍)

다이나믹 프로그래밍.다이나믹이라는 단어가 들어가서 그런지 이름만 들으면 엄청 화려?하고 신날거같지만 실상은 그렇지않다.프로그래밍에 다이나믹은 전혀 어울리지 않을거같은데 어떻게 다이나믹 프로그래밍이라는 이름을쓰지?그래서 이름에대한 유래를 알아봤다. 동적 계획법의 고안자인 벨만(Richard E. Bellman)은 dynamic이라는 단어가 멋있어서(...) 선택했다고 한다.Programming이란 단어는 최적화 연구 분야에서 최적의 프로그램을 찾아낸다는 의미로 사용된다. 프로그래밍 대회에서 배우는 알고리즘 문제해결전략(구종만 저) 1권 p.207 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그냥 멋있어보여서 사용함 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ다이나믹프로그래밍(DP) 에 대해 조금 알아보겠따.다이나믹프로그래밍은 큰문제를 풀기위해 작은..
Algorithm 2018. 6. 15. 00:30

[Algorithm]합병정렬(merge sort) 알고리즘 C++

대표적인 nlogn 정렬 알고리즘중 마지막인 합병(병합)정렬 이다. 합병정렬은 항상 nlogn 의 성능을 내는 알고리즘으로 힙정렬과 같고 최악상황의 퀵(n^2) 보다 안정적이다. 하지만 평균적으로 퀵정렬보다 느린 성능을 보이며 알고리즘 구현에있어 힙정렬보다 메모리를 더 많이먹는다. 합병정렬 -합병정렬을 쉽게 알수있는 짤(위키백과)- 합병정렬은 분할정복알고리즘이다. 분할정복은 하나의 문제를 잘개 쪼개어(분할하여) 문제를 해결하는 방법임. 합병정렬이 대표적인 분할정복을 사용하는 알고리즘인데. 정렬할 배열을 하나의 원소로 쪼개어 비교하며 정렬하는 방법이다. 이 정렬은 두가지 순서만 알면 되는데. 1.분할 (가장 작은 단위까지 분할)2.정렬 (가장 작은 단위부터 정렬) 과정을 정렬이 완료될때까지 반복이다. 순서..
Algorithm/정렬알고리즘 2018. 6. 12. 12:49

[C++]별 찍기(for문)

별찍기는 종류도 다양하다. 백준에 가보면 별찍기만 22개정도다 기본적인 별찍기를 알아보겠따. 너무나도 기초적인 별찍기 코딩 입문자들의 필수코스 별찍기 C++로 알아보게다.자바도 똑같다. 더 짧은코드를 원한다면 파이썬을 이용하자 별 찍기 - 1(https://www.acmicpc.net/problem/2438)* ** *** **** *****이모양이 나와야한다. #include using namespace std; int main() { int n; cin>>n; for(int i = 1 ; i
Algorithm 2018. 6. 9. 11:00

[Algorithm]퀵정렬 알고리즘(C++)

시간복잡도가 nlogn 인 정렬 알고리즘은 대표적으로 힙정렬, 병합정렬, 퀵정렬이 있다.힙정렬은 지난번에 알아보았고 이번엔 nlogn 알고리즘중에서도 평균적으로 가장 성능을 잘 내는 퀵정렬에 대해 알아보겠따. [Algorithm]힙정렬 알고리즘(C++) 힙정렬은 시간복잡도가 nlogn 으로 퀵정렬과 병합(합병)정렬과 같은 시간복잡도를 가진 정렬 알고리즘이다. 하지만 병합정렬과는 다르게 추가적인 메모리가 필요하지않고, 항상 nlogn의 정렬 성능을 보여주기때문.. dpdpwl.tistory.com 퀵정렬최악의 경우 n^2의 성능을 내지만 사실 최악의경우는 잘 나오지 않는다.. 이경우를 제외하곤 평균적으로 nlogn 의 성능.대부분의 상황에서 nlogn중 가장빠르다.사실 퀵정렬은 딱히 복잡한게 없다. 정렬을..
Algorithm/정렬알고리즘 2018. 6. 4. 14:29

[Algorithm]힙정렬 알고리즘(C++)

힙정렬은 시간복잡도가 nlogn 으로 퀵정렬과 병합(합병)정렬과 같은 시간복잡도를 가진 정렬 알고리즘이다. 하지만 병합정렬과는 다르게 추가적인 메모리가 필요하지않고, 항상 nlogn의 정렬 성능을 보여주기때문에 최악의 경우 n^2 의 성능을 보이는 퀵정렬보다 안정적인 성능을 보인다. 힙정렬은 힙의 구조에 대해 알고있으면 생각보다 간단한 정렬이다. 힙정렬을 알아보기전에 힙(Heap) 에 대해 간단히 알아보자. 힙(Heap)힙 트리 라고도 하는 힙은 완전이진트리 형태의 자료구조이다. 완전이진트리노드를 삽일할때 왼쪽부터 차례대로 추가하는 이진트리(모든 노드의 차수가 2이하로 구성된 트리) 위와같은 트리가 완전이진트리이며(각노드의 왼쪽부터 채워진 이진트리) 아래는 그냥 이진트리. 힙에는 최소힙과 최대힙이 있으며..
Algorithm/정렬알고리즘 2018. 5. 30. 14:47

[Algorithm]내부정렬 정렬시간(시간복잡도)

안녕하세요. 오늘은 내부정렬(버블정렬,선택정렬,삽입정렬)의 시간복잡도에 대해 알아보겠습니다. 버블정렬과 선택정렬 삽입정렬 모두 시간복잡도는 O(n²) 로 동일한데요. 그럼 과연 난수 배열을 생성하여 정렬을 시작하고 끝나는 시간이 모두 같은지 확인해보겠습니다. 12만개의 난수 배열을 생성하여 정렬시간을 비교해보았습니다. 결과는 거의 모든 상황에서 삽입정렬이 가장 빨리 끝이났고 버블정렬과 선택정렬은 비슷한 시간이 나오는것을 확인할수 있었습니다. 삽입정렬은 최악의 경우 시간복잡도가 O(n²)인 반면 버블정렬과 선택정렬은 항상 모든상황에서 자신만의 정렬 알고리즘을 전부 수행하기때문에 일정한 시간이 나오는데요. 삽입정렬 같은경우 최악의 경우는 잘 나오지 않기때문에 가장 빠르게 끝나버리는것같습니다. 그래서 난수배열..
Algorithm/정렬알고리즘 2017. 8. 24. 17:32

[Algorithm]삽입정렬 예제(insertion sort)

안녕하세요. 이번에도 기본정렬중 하나인 삽입정렬(insertion sort) 에 대해 알아보겠습니다. 삽입정렬은 기준이 되는 인덱스의 앞쪽을 검사하여 기준이 되는 인덱스가 들어갈 자리를 찾아서 삽입? 하는 정렬입니다. 시작은 1번 인덱스로 (0번인덱스가 처음인덱스), 0번 인덱스는 정렬이 되어있다고 하고 시작을합니다.(수가 하나라면 정렬을 할 필요가 없겠죠?) 그림과 예제를 보겠습니다. 보시는 것처럼 기준이 되는 수와 앞쪽 인덱스를 비교하여 앞쪽에 기준이 되는 수보다 큰 값을가진 인덱스가 있으면 한칸 밀고 기준이되는 인덱스의 수를 넣고, 또 앞쪽인덱스와 비교하여 앞쪽 인덱스가 더 크면 한칸밀고 기준이되는 인덱스의 수를 집어넣는 방식입니다. 이렇게 비교인덱스가 -1(0이 끝이기때문) 이 되거나 기준이 되는..
Algorithm/정렬알고리즘 2017. 8. 22. 13:46

[Algorithm]선택정렬 예제(selection sort)

안녕하세요~~~ 오늘은 자바로 선택정렬(selection sort) 에 대해 알아 보겠습니다. 버블정렬과 함께 정렬중에 기본인 선택정렬인데요!! 버블정렬과 마찬가지로 느린 정렬에 속합니다. 하지만 정렬에 기본이되기때문에 알아두면 좋은데요. 선택정렬은 기준이되는 수와 나머지수를 비교하여 가장 낮은수를 제일 앞으로 보내는 정렬입니다!!(오름차순일 경우) 그림설명을 보고 코드를보며 알아보겠습니다. 그림과 같이 0번째 인덱스와 그뒤의 값을 비교한뒤 가장 낮은 값을 0번째로 만들고 수행이 끝났으면 기준을 한칸 옮겨서 똑같이 수행합니다. 코드로 보면 public class SelectSort { public static void main(String[] args) { int[] a = {254,3,213,64,75..
Algorithm/정렬알고리즘 2017. 8. 22. 10:51