728x90 프로그래밍/알고리즘 & 자료구조7 [알고리즘] 최대 유량/포드-풀커슨 알고리즘에 대하여 **이 글은 학교 수업 시간에 활용한 발표자료를 가지고 재구성한 글입니다. 다양한 블로그나 사이트로부터 내용과 사진을 참고했으므로 출처를 밝힙니다.**참고자료 출처(감사합니다!)- https://velog.io/@kasterra/%EC%9C%A0%EB%9F%89-%EA%B7%B8%EB%9E%98%ED%94%84-%ED%8F%AC%EB%93%9C-%ED%92%80%EC%BB%A4%EC%8A%A8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98- https://www.slideshare.net/slideshow/2020-2-8-250161391/250161391- https://gseok.gitbooks.io/algorithm/content/b124-d2b8-c6cc-d06c-d50c-b8.. 2024. 9. 10. 비선형 자료구조 - 히프(Heap)와 삽입 및 삭제 연산 히프(Heap)란? 히프는 완전 이진트리의 한 종류입니다. 이때 완전 이진 트리란 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 구조를 말합니다. 히프는 모든 부모 노드가 그 자식 노드의 값보다 더 큰(혹은 작은) 값을 가지는 구조로 여러 값들 중 최댓값이나 최솟값을 빠르게 찾을 수 있도록 만들어졌습니다. 이러한 히프는 최대 히프와 최소 히프로 나뉩니다. 여기서 최대 히프냐 최소 히프냐에 따라 루트 노드만 탐색하면 최댓값 혹은 최솟값을 O(1)의 시간복잡도로 얻어낼 수 있습니다. 또한, 이 히프 구조는 우선순위 큐를 구현할 때 많이 사용되기도 합니다. 최대 히프 최대 히프란 부모 노드가 항상 자식 노드보다 크거나 같은 구조를 말합니다. 이.. 2023. 10. 19. 자료의 정렬(1) - 버블, 선택, 삽입 정렬 버블 정렬(Bubble Sort) 인접한 원소 간 비교를 통해 교환하는 과정을 반복하는 정렬 방법입니다. 알고리즘 수행 과정에서 키값이 큰 원소가 점점 뒤로 가는 모습이 마치 거품이 점점 커지는 모습과 닮았다는 의미에서 붙여진 이름입니다. 직관적으로 이해할 수 있고 구현이 간단하지만 O(N^2)의 시간복잡도를 가지고 있습니다. for(int i=1; i 2023. 9. 6. [자료구조] 덱(Deque) - 코딩기록 덱 덱은 앞서 포스팅에서 올렸던 스택과 큐를 합친 버전이라고 할 수 있다. 스택이나 큐는 한쪽에서만 삽입과 삭제가 가능했다면 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하게 만든 큐이다. 터널과 비슷하다고 할 수 있다. 덱은 스택이나 큐처럼 사용할 수 있기 때문에 활용도가 높은 자료구조이다. 덱의 기능 이제 덱STL을 활용해 기능들을 살펴보겠다. push_front(x) : 덱의 앞에 x를 추가 push_back(x) : 덱의 뒤에 x를 추가 pop_front() : 덱의 원소 중 맨 앞 원소를 삭제 pop_back() : 덱의 원소 중 맨 뒤 원소를 삭제 front() : 덱의 맨 앞 원소를 반환 back() : 덱의 맨 뒤 원소를 반환 empty() : 덱이 비어있으면 1(true), 비어있지 않으면 .. 2023. 5. 5. [자료구조] 큐(Queue) - 코딩기록 큐(Queue) 큐는 이전 포스팅에서 설명했던 스택과 약간 다른 점이 있는 자료구조이다. 이전에 설명했던 스택은 LIFO(후입선출)구조였지만 큐는 FIFO(First - In - First - Out) 선입선출 구조이다. 즉, 먼저 집어 넣은 데이터가 먼저 나오는 것이다. 1번, 2번, 3번 데이터가 차례로 들어오고 이 순서대로 나간다고 생각하면 된다. 맨 오른쪽에 있는 화살표에 해당하는 구간이 삽입연산이 수행되는 곳인 리어(rear)이고 맨 왼쪽에 있는 화살표에 해당하는 구간이 삭제연산이 수행되는 곳인 프론트(front)이다. 큐의 기능 이제 큐STL을 활용해 큐의 기능들을 살펴보겠다. push(x) : 원소 x를 큐의 맨 뒤에 추가 pop() : 큐의 맨 앞 원소 삭제 empty() : 큐가 비어있으.. 2023. 5. 4. [자료구조] 스택(Stack) - 코딩기록 자료구조 자료구조에 대해 간단히만 짚고 넘어가겠다. 자료구조의 정의는 컴퓨터과학에서 효율적인 접근과 수정을 가능하게 해주는 자료의 조직, 관리, 저장을 의미한다. 자료구조를 통해 데이터를 효율적으로 저장, 관리할 수 있고 메모리를 절약하거나 시간을 단축할 수 있다. 우리가 흔히 말하는 알고리즘과는 약간의 차이가 있다. 자료구조는 이름처럼 데이터를 저장하기 위한 구조이고 알고리즘은 자료구조에 있는 데이터를 활용해 문제를 해결하는 방법이라고 할 수 있다. 즉, 자료구조를 잘 익혀두면 문제를 더 효율적으로 해결할 수 있을 것이다. 이 포스팅에서 다룰 것은 자료구조에서 선형구조 중 하나인 스택이다. 스택 스택은 '쌓다'라는 뜻을 가지고 있다. 이 말처럼 스택을 이해할 때 탑을 상상하면 편하다. 다음과 같은 탑이.. 2023. 5. 3. 이전 1 2 다음 728x90
