![]()
그래프를 탐색하는 알고리즘 [깊이 우선 탐색(DFS)] 이름처럼 한길만 깊이 파고드는 알고리즘이다 (depth) 1. 하나의 정점에서 다른 하나의 정점만 탐색한다(한 사람에게만 연락한다) 2. 스택을 이용하여 경로를 되돌아간다★ 3. 처음 탐색을 시작한 정점의 위치에서 탐색은 끝이 난다 ▶ DFS의 구현 스택 : 경로 정보의 추적을 목적 (내가 이미 탐색을 완료해서 탐색할 기회를 다른 정점에게 넘긴 애들만 들어옴) 배열 : 방문 정보의 기록을 목적 그래프 구현한 내용에서 DFS 탐색 기능(스택+연결리스트)만 추가 정점의 이름 // 정점의 이름들을 상수화 enum {A, B, C, D, E, F, G, H, I, J}; 그래프를 표현한 구조체 (탐색이 완료된 정점의 정보 추가 by 배열) typedef s..
![]()
정점(데이터)끼리의 연결관계를 저장한 자료형 [용어정리] 정점 : 연결의 대상이 되는 개체 간선 : 개체 사이의 연결 무방향 그래프(양방향 가능) 방향 그래프 가중치 그래프 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프 부분 그래프 : 원 그래프의 일부 정점 및 간선으로 이워진 그래프 그래프 G의 정점 집합 V(G)={A, B, C, D} 그래프 G의 간선 집합 E(G)={(A,B), } (* ()는 무방향, 는 방향 그래프) [그래프의 두가지 구현방법] 인접 행렬 기반 그래프 (두 정점이 연결되어 있으면 1, 연결되어 있지 않으면 0으로 표시) 인접 리스트 기반 그래프 ▶ 그래프의 ADT 필요한 기능 : 그래프 초기화, 그래프 리소스 해제(그래프 자체 없엠), 연결된 간선 추가, 모든..
![]()
고유값 key(made by 해쉬함수)을 이용해서 배열에 저장함 ≒ #include [테이블] 키와 값이 하나의 쌍을 이루어 저장되는 데이터의 유형 O(1)의 시간 복잡도 #include typedef struct _empInfo { int empNum; //이것이 고유번호가 될것이여 int age; //실제 저장할 대상 }EmpInfo; int main(void) { EmpInfo empInfoArr[1000]; EmpInfo ei; int eNum; printf("사번과 나이 입력: "); scanf("%d %d", &(ei.empNum), &(ei.age)); empInfoArr[ei.empNum] = ei; printf("확인하고픈 직원의 사번 입력: "); scanf("%d", &eNum); e..
▶ 재귀 문제를 풀 때 생각의 흐름 반복되는 작업을 찾는다 (반복되는 부분은 재귀함수나 반복문으로 해결할수 있다) 반복되는 작업을 함수로 생각하고 input과 output의 형식을 각각 정한다 (output이 있을 경우 이 output이 다음번 input으로 사용될 수 있다) input은 한단계씩 점진적으로 변한다 (보통 크기나 길이가 줄어든다) 종료 조건을 설정한다 ▶ 재귀 문제 TIP 1. 문제의 정의를 명확히 표기한다 (ex. 피보나치 수열이란 어떤 수열의 항 = 앞의 두항의 합) 2. 종료조건을 정확히 설정한다 3. 재귀는 목적만 설정해주는 디클래러티브적 프로그래밍 (선언적 프로그래밍) 을 해야한다는것을 인지하자 4. 내가 생각한 컴퓨터가 알아서 슈슉 돌리고 결과를 짠하고 보여주는것은 불가능함 저..
어느정도 규칙은 찾았지만 함수를 2개 선언해야하는것, 전역변수에 2차원 배열을 선언하는것을 생각해 내지 못했다 👩🏻💻 문제링크 https://www.acmicpc.net/problem/10994 10994번: 별 찍기 - 19 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 우선 안에 있는 별 모음을 둘러싸는 별 모음을 만들어야한다 2. 이전 별 모음의 바깥쪽을 둘러쌓는 새로운 별모음을 만드는것이 재귀적이다 3. 다음번 별 모음을 생성할려면 인덱스가 +2, +2 씩 더해진다 ✍️소스코드 다른 사람의 코드를 어느정도 보고 내 방식대로 구현해 본것 #include using namespace std; char arr[400][400]; void..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 y좌표를 중가하는 순으로가 1순위 y좌표 같으면 x좌표 증가하는 순으로 ✍️소스코드 #include #include #include using namespace std; bool cmp(pair a,pair b) //!!! { if(a.secondN; vector v; for(int i=0; ..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 결국엔 숫자 나열해서 N번째 숫자 구해라는거임 2. 시간 제한이 1s이므로 n2 까지의 연산이 가능하다, 메모리 제한이 12mb 이므로 1500*1500*4byte의 값을 다 저장 못하므로 5개 자리 만들어서 입력 받을때 마다 최후의 5인이 결정된다 ✍️소스코드 #include #include using namespace std; int main() { c..
![]()
들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다 [우선순위 큐의 종류] 배열을 기반으로 구현하는 방법 (삽입/삭제시 모든 데이터 뒤로 밀거나 당겨야함, 모든 데이터와 우선순위를 비교해야함) 연결리스트를 기반으로 구현하는 방법 (모든 데이터와 우선순위를 비교해야함) 힙을 이용하는 방법 힙 = 완전이진트리 + 모든 노드에 저장된 값은 자식노드에 저장된 값보다 크거나 같음(최대 힙) [힙을 이용하여 만드는 우선순위 큐] 힙≠우선순위 큐 이다 → 힙은 우선순위 큐 구현에 딱 어울리는 자료구조일 뿐이다. (데이터 추가 방식) 1. 새로운 데이터는 우선순위가 가장 낮다고 가정하고 마지막 위치에 저장함 2. 부모 노드와 비교해서 위치가 바뀌어야 하면 바꿈 3. 제대로 된 위치를 찾을때 까지 반복 (데이터..
