강의자료/알고리즘 37

[자료구조] 우선순위큐(Priority Queue)

우선순위큐(Priority Queue) 란? 우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선순위가 높은 데이터가 먼저 나가게 된다. 응용분야 - 시뮬레이션 시스템 - 네트워크 트래픽 제어 - 운영체제에서의 작업 스케줄링 우선순위큐 STL 기본 형태 priority_queue : 원하는 자료형 및 클래스 T를 통해 생성, 여기서 Container는 Vector와 같은 컨테이너 이며 Compare 는 비교 함수 클래스(단,Compare 조건에서 참인 것이 후 순위로 밀린다.) 우선순위큐 함수 push(element) : 우선순위 큐에 추가 pop() : 원소 삭제 top() : top에 있는 원소를 반환 empty() : 비어있으면 true 아니면 false size() : 우선 순위 큐에..

[자료구조]링크드 리스트(Linked List)

선형리스트 - 배열에서 원소 삽입 방법을 살펴 보자. 질문) 위와 같은 경우 배열의 데이터가 1억개 인경우 0 번지에 데이터를 삽입 하기 위해서 몇번 연산을 해야 할까? - 배열에서 원소 삭제 방법을 살펴 보자. 질문) 위와 같은 경우 배열의 데이터가 1억개 인경우 0 번지에 데이터를 삭제 하기 위해서 몇번 연산을 해야 할까? 순차 자료구조의 문제점 - 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가 작업과 시간 소요 - 원소들의 이동 작업으로 인한 오버헤드로 원소의 개수가 많고 삽입・삭제 연산이 많이 발생하는 경우에 성능상의 문제 발생 - 순차 자료구조는 배열을 이용해 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가짐 - 순차 자료..

[알고리즘]알고리즘 수행시간을 비교해 볼까?

알고리즘이란? - 입력 : 외부에서 제공되는 자료가 0개 이상 제공된다. - 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.( 즉 모든 입력에서 하나의 출력이 나오면 안됨) - 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성 - 유한성 : 유한번의 명령을 수행 후 종료된다. - 효율성 : 모든 과정은 명백하게 실행가능(검증가능) 한것이어야 한다. 좋은 알고리즘이란? - 정확성 : 적당한 입력에 대해서 유한 시간내에 답을 산출하는가? 를 판단. - 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정 - 기억장소 사용량 : 수행 과정에서 필요한 저장공간 - 최적성 : 그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가? (단, 최적이란 가장 '잘 알려..

[알고리즘]그리디(greedy) 알고리즘

그리디(greedy) 알고리즘이란? 단어에서 나타내듯이 아주 탐욕스러운 알고리즘 입니다. 이렇게 탐욕스럽다라고 표현 하니 학생들은 아주 나쁜 알고리즘이네요? 라고 말하네요. 하지만 탐욕스러운 것이 정말 나쁜 것일까요? 자신이 항상 손해 보면서 사는 사람은 없을 것입니다. 사람 사는 세상에 주고 받고 하면서 자신이 더 큰 이득을 보기 위해 조금 더 작은 것을 내 주는 것일 뿐입니다. 이와 마찬가지로 그리디 알고리즘은 현재 선택해야 되는 시점에서 자신에게 가장 이득이 되는 것을 취하고 나머지는 버리는 경우를 그리디 알고리즘이라고 합니다. 이러한 알고리즘의 예로 가장 많이 사용 되는 것이 동전 바꿔 주는 문제인데요. 500원,100원,50원,10원,5원,1원 단위의 동전이 있을때 문방구에 가서 1432원짜리 ..

(기하알고리즘) 반직선의 교점찾기 2

https://wondangcom.com/903 (기하알고리즘) 반직선의 교점 찾기 1 지난번에 두 선분의 교점 찾기에 대해 설명을 해 드린적이 있는데요. https://wondangcom.com/466 기하알고리즘] 두 선분의 교차점 찾기 위와 같은 그림에서 교차점이 발생하는 경우는 a,c,d,h 인 경우 입니다. 이.. wondangcom.com 지난번에 반직선의 교점 찾기 위해서 기본적인 클래스를 구현해 보았는데요. 오늘은 지난번에 만들어 놓은 클래스와 함수들을 이용해서 다음의 문제를 풀어 보도록 하겠습니다. 문제 원본 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2555&sca=30d0 JUNGOL | 반직선이 만나는 경우의 수 > 문제은행..

(기하알고리즘) 반직선의 교점 찾기 1

지난번에 두 선분의 교점 찾기에 대해 설명을 해 드린적이 있는데요. https://wondangcom.com/466 기하알고리즘] 두 선분의 교차점 찾기 위와 같은 그림에서 교차점이 발생하는 경우는 a,c,d,h 인 경우 입니다. 이러한 두 선분의 교차점을 검사하는 방법으로는 다음과 같이 찾아 볼수가 있습니다. 1] 각 선분에 대해서 그 선분을 포함하는 양방향으로.. wondangcom.com 오늘은 반직선의 교점 찾기에 대해 설명을 해 볼까 합니다. 반직선은 한쪽은 막혀 있고 다른쪽 방향으로 진행을 하는 화살표를 가진 직선을 반직선이라고 합니다. 반직선의 교점을 찾기 위해서는 먼저 직선의 교점을 찾는 방법에 대해 확인을 해 봐야 하는데요. 지난번의 두선분의 교점은 시작점과 끝점이 주어졌기에 그 위치에서..

[문자열 알고리즘] KMP 알고리즘

KMP 알고리즘이란? 위키백과에 따르면 커누스(Knuth),모리스(Morris),프랫(Pratt) 이 발견한 문자열 일치 문제에 대해 패턴정보를 활용하여 검색시간을 단축하는 방식 이라고 정의 되어 있습니다. 이러한 문제는 다음과 같은 경우에 빠른 시간에 문자열을 검색하기 위한 알고리즘인데요. 위와 같이 네이버에서 원당컴퓨터학원을 찾기 하면 원당컴퓨터학원이라는 글자에 표시가 되는 것을 조금 더 빠르게 해결하기 위한 패턴입니다. KMP 알고리즘을 이해 하기 전에 먼저 브루트포스법 이라고 하는 알고리즘을 살펴 보겠습니다. 만약 문자열 S="ABCDABCDABBABCDABCDWZ" 가 있고 찾을 문자열 P="ABCDABCWZ" 라는 문자열이 있다면 우리가 알고 있는 알고리즘은 다음과 같습니다. ABCDABCDA..