1. 연결 리스트 1) 정의 : 자료가 순서를 가지고 나열된 자료구조를 이야기 한다. 2) 리스트의 표현 ⓐ 배열 이용 - 이 방식은 리스트의 각 원소마다 배열의 원소에 대응시킨다. - A[k]를 읽거나 교체하는 연산은 상수시간이 걸리지만, 삽입과 삭제 연산은 순차매핑을 유지하기 위해 원소의 이동을 필요로 하므로 많은 시간이 소요된다. * 순차 매핑 : 배열이 메모리의 연속적인 공간을 차지함 ⓑ 연결 리스트 이용 - 연결 리스트란 화살표로 표시되는 링크를 가진 노드의 순서 리스트 이다. - 첫번째 노드를 가르키는 포인터의 이름이 연결 리스트의 이름이다. * 연결리스트의 노드들은 메모리에 순차적으로 놓여있지 않을 수 있다. 🟡 포인터를 이용하여 연결 리스트 표현하기 - 하나의 노드는 데이터를 갖고있는 데이..

#쉽게 배우는 데이터 통신과 컴퓨터 네트워크(개정판) 책을 바탕으로 작성하였습니다. 01 네트워크 관련 기초용어 1. 네트워크 기초 용어 네트워크 : 전송 매체로 연결된 시스템의 모음, 프로토콜을 사용하여 데이터를 교환하는 시스템 집합의 통칭(H/W) 시스템 : 내부 규칙에 따라 능동적으로 동작하는 대상 (H/W+S/W) 인터페이스 : 시스템과 전송 매체의 연결 지점에 대한 약속 ex) GUI, HCI, API, NAI 등 전송매체 : 시스템끼리 데이터를 전달하기 위한 물리적인 전송수단 ex) 인터넷케이블, 무선, 광케이블 등 프로토콜 : 전송매체를 통해 데이터를 교환할 때의 임의의 통신 규칙 인터넷 : 전세계의 네트워크가 유기적으로 연결되어 동작하는 통합 네트워크 표준화 : 서로 다른 시스템이 상호 연..

1. 문자와 문자열 - 문자와 문자열은 다른 개념입니다. - 문자는 단일 문자를 이야기하며, 문자열은 둘 이상의 결합문자를 이야기 합니다. 2. 문자 입력받기 - C언어에서 문자를 입력받기 위해서는 char 자료형을 이용해야 합니다. - 서식문자로 %c를 사용합니다. 예시 ) 문자 한개만 입력받기 int main() { char c1; printf("문자를 입력하세요: "); scanf("%c", &c1); // 문자를 입력받아서 변수에 저장 printf("%c\n", c1); // 변수의 내용을 출력 return 0; } 예시) scanf 하나로 문자 여러개를 입력받기 - 정수나 실수를 입력 받듯이 %c를 붙여서 입력받으면 c2값은 들어가지 않습니다. 왜냐하면 엔터키나 스페이스도 하나의 문자로 치기 때..

1. 퀵 정렬(분할정복법) 1) 과정 - 리스트에 원소 하나를 고른다(피벗) - 피벗과 다른 n-1개 원소 각각을 비교하여, 피벗보다 작은 것과 큰 것으로 분할한다. - 분할된 두 개의 작은 리스트를 재귀적으로 정렬한다. 2) 피벗 선택방법 - 중앙값(최선 피벗) - 랜덤선택 - 리스트 맨앞, 중간, 맨뒤에 있는 세 원소의 중앙값을 선택 3) 코드 void Quick_sort(int arr[],int i, int j) { int n, cnt = 0; if (i >= j) return; int pivot = arr[(i + j) / 2]; int left = i; int right = j; while (left pivot) right--; if (left

1. 정렬 알고리즘 - 정렬알고리즘은 알고리즘 중에 가장 기본적인 알고리즘 이다. - 이 글에서 살펴볼 알고리즘은 삽입, 선택, 거품(버블), 퀵, 합병(merge), 힙, 이진탐색 트리를 이용한 정렬이다. 1) 삽입정렬 - O(n^2) - 배열의 모든 원소를 앞에서부터 차례대로 배열 부분과 비교하여, 삽입함으로써 정렬하는 알고리즘 - 처음 key 값(처음으로 뽑아 비교할 원소)은 두번째 원소이다 > 과정 두번째 원소 10을 뽑아 첫번째 원소와 비교하여 29보다 작으므로 29왼쪽으로 삽입된다. 세번째 원소 14를 뽑아 두번째 원소와 비교하여 29보다 작으므로 29왼쪽으로 삽입된다. 14는 10보다 크므로 바뀌지 않는다. 네번째 원소 37를 뽑아 세번째 원소인 29와 비교한다. 37이 29보다 크므로 바뀌..

1. 문제 * 길이가 n인 배열 A[0], A[1], ..., A[n-1] 이 입력으로 주어 질때, i번째부터 j번째까지 원소드로 이루어진 배열 A[i], ..., A[j] 를 부분배열이라고 하고, A[i, j] 로 나타낸다. - 부분 배열의 속한 원소들의 합이 최대가 되는 부분 배열을 구하는 것이 이 문제의 목적이다. 이 때 길이가 0인 부분배열도 허용하며, 이 부분배열의 원소들의 합은 0이라고 정의한다. 예를 들어, 아래와 같은 배열이 있다면, -2 -1 3 5 2 -5 0 2 이 배열의 최대부분배열의 합은 몇일까? 3+5+2 = 10 이다. 2. 해결방법 - 최대부분배열의 원소합을 구하는 알고리즘에는 크게 4개가 있다. - 완전탐색, 중복제거한 탐색, 분할정복법, 동적계획법 1) 완전탐색(브루트포스..

* 교재 : COMMON LISP: A Gentle Introduction to Symbolic Computation + 기본 문법 - 주석 : ;;(한 줄 주석), ""(따옴표 안 주석) - 함수 정의 (defun) - number : 정수, 실수, 비율 ex) (/ 3 6.0) = 0.5 (피연산자에 실수가 있으면 답이 실수로 나옴) - Data type (데이터 타입) Number (숫자) Symbols (심볼) T/Nil (부울) Strings (문자) Lists (리스트) * QUOTE : '(DON'T EVALUATE) 1. 함수(Function) - 리습에 내장되어있는 함수이다. 1) 종류 +, -, *, / 사칙연산 RANDOM 랜덤 ex) (random 10) = 6 expt 제곱 ex)..

1. BFS란? - BFS 는 너비우선탐색을 말합니다. - 루트 노드에서 시작하여 인접한 노드를 탐색하는 방법입니다. Q. 너비우선 탐색을 하면 순서가 어떻게 될까요? A. 0 - 1 - 2 - 3 - 4 - 5 -6 1) 특징 - 두 노드사이의 최단 경로를 찾을 때, 임의의 경로를 찾을 때 사용 - 코드가 DFS보단 복잡하지만 속도는 더 빠르다 2) 알고리즘 구현 방법 BFS의 결과 : 1 - 2 - 6 - 3 - 4 -5 - 큐를 이용하여 구현함 void bfs(int st) { q.push(st); visited1[st] = 1; while (!q.empty()) { int now = q.front(); q.pop(); printf("%d ", now); for (int i = 0; i < adj[..

1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 난이도 : 실버2 풀이과정 : DFS는 재귀함수를 이용해서 풀었습니다 [Algorithm] DFS 정리 (tistory.com)