알고리즘, 자료구조/자료구조3 27. 그래프 그래프 사용의 예 철도망의 안정성 분석 - 28 절단점 찾기 알고리즘 소셜 네트워크 분석 - 29 BFS(너비 우선 탐색) 인터넷 전송 속도 계산 - 31 최소 스패닝 트리 한 붓 그리기 (오일러 경로) - 28.4 DFS(깊이 우선 탐색) 외환 거래 - 30 최단 거리 알고리즘 암시적 그래프 구조들 그래프 형태를 갖는 구조가 아니라도, 그래프를 통해서 표현하면 쉽게 해결할 수 있는 문제들이 있음. 이를 암시적 그래프(implicit graph)라 한다. 할일 목록 정리 - 위상 정렬(topological sort) - 28 DFS(깊이 우선 탐색) 15-퍼즐 - 29, 30 최단 경로 문제 게임판 덮기 - 32 이분 그래프, 이분 매칭 알고리즘 회의실 배정 - 28 강 결합성 문제 그래프의 표현: 인접.. 2019. 9. 8. 19. [스택, 큐, 데크] 간단 정리 구현 1. 연결리스트 O(1) : 리스트 양쪽 끝에 추가와 삭제 O(N) : 임의의 노드의 할당, 삭제, 포인터 따라가기(traveling) 2. 동적 배열 스택 : 추가, 삭제 O(1) 큐 : rear(뒤) 부분 추가, 삭제 O(1) / front(앞) 부분 추가, 삭제 O(N) 따라서 circular queue(혹은 circular buffer)를 만들기도 함. (추가, 삭제 발생시 head와 tail을 변경) : O(1) 데크 : 둘다 O(1) 온라인 알고리즘 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘. 입력의 크기가 너무 커서 프로그램상에 올려놓을 수 없을 때 사용한다. 2019. 8. 27. 선형자료구조 1. 동적배열 - 원소를 순서대로 저장 --> 인덱싱(원소찾기)이 O(1) - 삽입, 삭제 O(N) - 원소들이 메모리에 연속해 배치되어 있어 CPU 캐시의 효율을 높여줍니다. capacity: 미리 여유있게 할당받은 메모리의 크기 = 배열의 용량 size: 배열의 원소 수 용량(capacity)이 꽉찼을 때, 배열에 새로운 원소를 추가하려면 아래 방식으로 재할당을 하여야 합니다. 더 큰 새 배열을 동적으로 할당받고, 기존 배열의 내용을 모두 복사한 다음, 배열에 대한 포인터를 바꿔치기(swap)해야 합니다. - append() 연산과, 성능 append() 연산을 여러번 할 때 배열의 최종크기가 얼마일지 미리 짐작할 수 있다면, 동적배열의 용량을 미리 늘려둠으로써 재할당 비용을 없앨 수 있습니다. --.. 2019. 8. 26. 728x90 이전 1 다음
