Computer Science/알고리즘30 [알고리즘] ep5-2+) DFS, BFS 구현 문제1) DFS 구현입력으로 주어지는 그래프의 DFS 순회 결과를 출력하는 프로그램을 작성하시오. 입력 그래프의 성질:n (1 ≤ n ≤ 100) 개의 정점과 m (1 ≤ m ≤ 1,000) 개의 간선으로 구성정점은 1 ~ n 사이의 정수로 번호가 매겨져 있고, 정점의 번호는 모두 다름모든 간선은 무방향 간선이고, 한 정점에서 임의의 다른 정점으로 가는 경로는 반드시 존재구현 조건:그래프는 인접리스트 구조를 사용하여 표현해야 한다.인접 정점의 조사 순서: 정점 u의 인접 정점(or 부착 간선)들을 번호가 작은 정점부터 조사한다. (즉, 아래 DFS 의사 코드의 for 문에서 인접 정점들을 번호가 작은 정점부터 큰 순서대로 조사하라. 조사 순서에 따라 방문 결과가 달라질 수 있음에 유의할 것)입력:첫 줄에.. 2024. 7. 22. [알고리즘] ep5-2) 그래프 순회 그래프 순회(graph traversal): 모든 정점과 간선을 검사함으로써 그래프를 탐험하는 체계적인 절차- 수도권 전철망의 모든 역(정점)의 위치를 출력- 항공사의 모든 항공편(간선)에 대한 노선 정보를 수집- 웹 검색엔진의 데이터 수집 부문은 웹의 하이퍼텍스트 문서(정점)와 문서 내 링크(간선)를 검사함으로써 서핑 그래프의 순회로는 DFS, BFS 두 가지가 있다그래프 G에 대한 DFS 순회 또는 BFS 순회의 활용은 아래와 같다- G의 모든 정점과 간선을 방문- G가 연결그래프인지 결정- G의 연결요소들을 계산- G의 신장 숲을 계산 ① 깊이우선탐색(DFS, Depth-First Search) by 스택(재귀)n개의 정점과 m개의 간선을 가진 그래프에 대한 DFS는 O(n + m) 시간 소요 "D.. 2024. 7. 21. [알고리즘] ep5-1+) 인접리스트, 인접행렬 구현 다음의 문제 1과 문제 2는 주어진 그래프를 인접리스트 및 인접행렬로 각각 표현하여 해결해야 한다. 다음은 두 문제 모두에 공통된 사항이다. 1) 그림 1의 그래프에 관해 해결해야 한다. 2) 가중치의 값은 양수와 음수 모두 가능하나, 0은 허용하지 않는다. 3) 그림 1 그래프의 정점 개수는 변경되지 않는다. 단, 간선 개수는 변화할 수 있다. 참고로 정점 6개인 그래프에서 가능한 간선 개수는, 자기 자신으로 가는 간선(즉, 루프)을 포함하여 최대 21(= 6 + 5 + 4 + 3 + 2 + 1)개다. 4) 간선의 이름을 생략하기로 한다. 따라서 간선 구조체의 이름 필드는 정의하지 않아도 된다. 5) 그래프를 배열 또는 연결리스트 가운데 어느 것을 이용하여 구현할지는 각자의 판단에 맡긴다. 문.. 2024. 7. 21. [알고리즘] ep5-1) 그래프(graph) ㅁ그래프(graph) ADT: (vertex, edge)의 쌍v: 정점 노드들의 집합e: 간선 노드들의 집합 정점: 공항을 표현하며 공항도시 이름을 저장간선: 두 공항 사이의 항로를 표현하며 항로의 거리(mile)를 저장 [그래프 응용]- 전자회로: 인쇄회로기판(PCB), 집적회로(IC)- 교통망: 고속도로망, 항공노선망- 컴퓨터 네트워크: LAN, 인터넷, 웹- 데이터베이스: 개체-관계 다이어그램(entity-relationship diagram) ㅇ무방향그래프(undirected graph): 모든 간선이 무방향간선인 그래프 ㅇ방향그래프(directed graph): 모든 간선이 방향간선인 그래프 [그래프 기본 용어]간선의 끝점(end vertex or endpoint): 점점 U와 V는 a.. 2024. 7. 21. [알고리즘] ep4+++) 비활성화 방식 삭제 문제) 크기가 M인 해시테이블에 키 값을 입력받아 저장하고, 개방주소법 중 이중 해싱을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오. [프로그램 요구사항]1) 해시테이블의 사이즈 M = 23 으로 정의할 것. 2) 이중해싱에 기반해야 하며 h 및 h’은 각자 적절히 정의하여 사용할 것. 3) 저장 원소는 0에서 99 사이의 정수로 제한할 것. 4) 삽입(i) 명령시, 중복 키 또는 해시테이블이 만원일 경우 적절한 안내 메시지와 함께 명령수행을 거절할 것. 5) 탐색(f) 또는 삭제(r) 명령시, 함께 주어진 키가 존재하지 않을 경우 NoSuchKey를 반환 및 인쇄할 것. [주의]인쇄(p) 명령시에만, 아래 예시처럼 현재 해시테이블의 내용을 두 개의 라인으로 보여줄 것. 윗 라인은.. 2024. 7. 19. [알고리즘] ep4++) 개방주소법 구현(선형 조사, 이중 해싱) 문제1) 크기 M인 해시테이블에 n개의 키 값을 입력받아 저장하고, 개방주소법 중 선형조사법을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오. [구현 조건]- 해시테이블은 크기가 M인 배열로 동적 할당한다.- n은 M보다 작은 자연수로 최대 삽입 개수다.- 입력 키는 중복이 없는 6자리 또는 8자리의 임의의 자연수(학번)다. - 키 x에 대한 해시함수 h(x) = x % M 을 사용한다.- 저장된 키 값이 없는 빈 버켓은 0으로 처리한다. [입력]- 해시테이블의 크기 M과 입력 데이터의 크기 n을 입력받는다.- 삽입(i), 탐색(s) 명령어를 순서에 상관없이 반복하여 입력받는다. i x> : 키 x를 해시테이블에 삽입s x> : 키 x가 해시테이블에 존재하는지 탐색 e : 프로그램 종료 [출.. 2024. 7. 19. [알고리즘] ep4+) 연쇄법 구현 문제) 크기 M인 해시테이블에 여러 개의 키 값을 입력받아 저장하고, 연쇄법을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오 [구현 조건]- 해시테이블은 크기가 M인 배열로 동적 할당한다.- 입력 키는 중복이 없는 자연수다.- 키 x에 대한 해시함수 h(x) = x % M 을 사용한다.- 삽입 시 충돌이 발생하는 경우, 해당 버켓 리스트의 맨 앞에 삽입한다. [입력]- 해시테이블의 크기 M을 입력받는다.- 삽입(i), 탐색(s), 삭제(d), 인쇄(p) 명령어를 순서에 상관없이 반복하여 입력받는다. i x> : 키 x를 해시테이블에 삽입s x> : 키 x가 해시테이블에 존재하는지 탐색d x> : 키 x가 해시테이블에 존재하면 삭제p : 해시테이블에 저장된 키들을 순서대로 인쇄(입출력 예시 참.. 2024. 7. 19. [알고리즘] ep4) 해시테이블(hashtable) 선형검색에 반해 해시테이블의 검색시간은 평균적으로 상수시간이다 (사전에 삽입된 모든 키가 충돌하는 최악의 경우는 O(n))해시테이블의 상수시간이 가능한 이유는 "해시함수"를 통해 바로 접근하기 때문이다ㅁ해시테이블(hashtable): 버켓배열 + 해시함수(key, address) 맵핑에 의해 구현된 사전 ADT※ key-value는 키와 값을 직접 연결하는 방식이라면, key-address는 키가 실제 데이터의 위치(주소)를 가리키는 방식 e.g. 컴파일러의 심볼 테이블, 환경변수들의 레지스트리, 소규모 DB, 브라우저 캐시 ㅇ버켓배열(bucket array) = 테이블 버켓을 슬롯(slot)이라고도 한다 ㅇ해시함수(hash fucntion): 맵핑하는 역할e.g. h(x) = x % Mh(x)는 정.. 2024. 7. 18. [알고리즘] ep3++) AVL 트리 구현 AVL 트리 구현종료(q) 명령 때까지 삽입(i), 탐색(s), 삭제(d), 인쇄(p), 명령을 반복 입력받아 수행i : 입력 에 대한 노드 생성 및 트리에 삽입d : 입력 가 트리에 존재하면 해당 노드 삭제 후 삭제된 키를 출력, 없으면 ‘X’를 출력s : 입력 가 트리에 존재하면 해당 키를 출력, 없으면 ‘X’를 출력 p: 현재 트리를 전위순회로 인쇄q: 프로그램 종료 주의: 중복 키가 없는 것으로 전제한다. 문제를 단순화하기 위해, 키만 존재하고 원소(element)는 없는 것으로 구현한다. main 함수는 반복적으로 명령을 입력받기 전에 빈(empty) 이진탐색트리를 초기화해야 한다 – 즉, 외부노드 1개로만 구성된 이진트리를 말한다. 힌트: 트리 노드 삭제 시, 삭제할 노드 w의 자식 중 하나.. 2024. 7. 17. 이전 1 2 3 4 다음
