프로그래밍67 chapter09 알고리즘 그래프(1) 버스노선 시공 일정 네비게이션의 경로탐색 -> 최소신장트리, 최단경로탐색으로 해결 9.1 그래프의 개요 9.1.1 그래프의 탄생 쾨니히스베르크 도시를 가로지르는 다리들을 한번만 건너서 순회하는 방법을 찾다가 고안 되었다 해결법은 한붓그리기 : 홀수개의 선으로 연결된 점이 없거나 두개인 도형에서만 가능하다. 9.1.2 그래프의 정의 V : 정점의 집합 E : 간선의 집합 G: 그래프 =(V,E) 길이 : 정점과 정점 사이에 있는 간선의 수 인접(또는 이웃관계) : 간선으로 연결된 두 정점 경로는 길이를 가지는데, 길이는 정점과 정점 사이의 간선의 수이다. 사이클(Cycle) : 어느 경로가 정점 하나를 두 번 이상 거치도록 되어있을 때 (트리에서는 볼 수 없다) 방향성 그래프 : 간선에 방향성이 있을 대 .. 2023. 5. 17. 9. java 생성자 생성자 인스턴스를 생성할 때 사용한다 어떤 값을 가지고 인스턴스가 만들어지게 하고 싶다면 생성자를 사용한다. 클래스 작성시 생성자를 하나도 만들지 않았다면 자동으로 기본 생성자가 생성된다. 기본 생성자는 매개변수를 하나도 받지 않는 생성자를 말한다. public Car(){ System.out.println("자동차가 한 대 생성됩니다"); } 생성자는 메소드와 비슷하다 return type이 없다. 클래스 이름과 같아야 한다. 접근 제한자 다음에 바로 클래스명이 나온다. 매개변수가 0개인 생성자를 기본 생성자라고 한다. 생성자가 하나도 없으면 아무일도 안하는 기본 생성자가 자동으로 컴파일타임에 만들어진다. 이름을 가진 인스턴스가 만들어지고, 이름을 출력하고 싶으면 다음과 같이! private Strin.. 2023. 5. 11. chapter12 알고리즘 분할 정복, 병합정렬 12.1 분할 정복 기법 12.1.2 분할 정복 알고리즘의 개념 사탕의 큰 덩어리를 작은 조각으로 나누어 먹으면 더 넓은 표면을 입안에서 녹일 수 있다. 분할정복도 마찬가지로 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나뉜 문제들을 각각 풀어 결국 전체 문제의 답을 얻는 기법. 5장의 퀵 정렬. 대강의 설계 요령 분할(divide) : 문제가 분할 가능한 경우 2개 이상의 하위 문제로 나눈다. 정복(conquer) : 하위 문제가 여전히 분할 가능한 상태라면 하위 집합에 대해 단계 1을 수행. 그렇지 않다면 하위 문제를 해결 결합(combine) : 단계2를 통해 구한 답을 취합 문제를 잘게 나누는 것이 가장 중요하다. 문제를 제대로 나누기만 한다면 정복(해결)하는 일은 아주 쉽다. 분할정복 .. 2023. 4. 17. chapter08 알고리즘 해시테이블 8.1 해시 테이블의 개요극한의 탐색 성능을 가진 자료구조 8.1.1 해시뜻 : 잘게 자른 고기를 양파나 감자와 같은 다른 재료와 함께 튀겨 한덩어리로 만든 요리. ㅋㅋ,,, 아무튼 데이터를 입력받아 완전히 다른 모습의 데이터로 바꾸는 작업. 해시테이블 : 데이터의 해시값을 테이블 내 주소로 이용하는 궁극의 탐색ㅇ ㅏㄹ고리즘. 빠르다고 정평이 나 있는 이진탐색도 명함을 내밀지 못함암호화 : 해싱은 원본 데이터를 다른 모습으로 바꿔놓는다. 해싱은 같은 데이터에 대해 같은 결과를 출력하지만 다른 데이터에 대해서는 다른 결과를 출력한다. 말하자면 해시는 데이터의 지문 역할을 할 수 있다. 이런 특징 때문에 해시는 디지털 서명이나 블록체인에 많이 사용된다. MD5, SHA 알고리즘이 대표적인 예데이터 축약 : .. 2023. 4. 17. chapter07 자료구조(알고리즘) 우선순위 큐, 힙 7.1 우선순위 큐 우선순위에 따라 출력 순서를 결정하는 큐 삽입과 제거 연산을 지원하는 ADT 보통 큐와의 차이는 ‘삽입과 제거 연산이 어떻게 동작하는가?’에 있다. 7.1.1 우선순위 큐의 삽입/제거 연산 노드 삽입 연산 첫 노드와 순차적으로 우선순위를 비교하면 되는데, 순차탐색을 해야하나? 해결할 방법 : 트리 처럼 하면 될듯. (내 생각,,, 아그래서 힙인가보다…ㅁㅊ) 노드 제거 연산 제거 연산은 간단하다. 전단만 제거해서 반환하면 끝. 큐니까! 7.1.2 우선순위 큐의 구현 힙을 사용한다~~ 7.2 힙 힙 : 힙 순서 속성을 만족하는 완전 이진 트리. 최고 깊이를 제외한 모든 깊이의 노드가 완전히 채워져 있는 이진트리. 힙 순서 속성 : 트리 내의 모든 노드가 부모 노드보다 커야 한다. (이진탐.. 2023. 4. 15. chapter13 자료구조 큐 3.1 큐 ADT FIFO 선입선출 3.1.2 큐의 핵심 기능 : 삽입과 제거 연산 전단 : 큐의 가장 앞 요소 후단 : 큐의 가장 마지막 요소 삽입은 후단, 제거는 전단에서 수행된다. 3.2 순환 큐 전단과 후단을 가리키는 변수를 만든다. 삽입이 일어날 때 마다 후단의 위치 +1. 삽입이 이루어질 때 후단이 가리키는 위치에 데이터를 바로 입력. 배열의 시작과 끝을 연결하면 메모리 용량을 잘 사용할 수 있다. 전단과 후단 사이에 공백 메모리를 둬서 큐가 공백상태일 때는 전단과 후단이 같은 곳을 가리키고, 큐가 포화상태일 때는 후단이 전단보다 1 작은 값을 가지도록 하여 상태를 구분한다. 3.2.2 순환 큐의 기본 연산 순환 큐의 노드 구조체 선언 typedef int ElementType; typedef.. 2023. 4. 14. 이전 1 2 3 4 5 6 ··· 12 다음