매일코딩

이진탐색 오름차순 정렬돼있는 리스트 내에서 특정 값의 인덱스를 찾는 알고리즘 7이라는 숫자의 인덱스를 빠르게 찾는 방법은 리스트의 절반 인덱스 값을 확인하고 그 값보다 작으면, 그 앞의 절반 리스트만을 남기고 또 그 리스트의 절반 인덱스 값을 확인하고 또 그 값보다 작으면 절반의 리스트만을 남기는 절차를 계속 진행한다. 장점 빠른 속도 시간복잡도 O (logN) 단점 정렬된 리스트에서만 사용 가능 정렬 - 안정정렬 vs 불안정 정렬 -- 중복된 값의 순서 보장 여부 In-place정렬 vs Out-of-place정렬 - 원본 데이터 내 정렬의 여부 Bubble SORT - 인접한 두 원소를 비교 - 두 값이 정렬되지 않았다면 SWAP - 정렬이 완료된 원소를 제외하고 위의 과정을 반복 - O(N^2) -..

https://www.acmicpc.net/problem/1920 문제 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에..

해시의 예시 회원정보 사진 : 홍길동의 사진 이름 :홍길동 나이 :20 전화번호 : 01012345678 이렇게 12칸의 서랍중 홍길동의 회원정보가 담긴 곳을 항상 매번 찾으면 힘드니까 홍길동의 사진 -> 고유의 회원정보 찾아주는 함수 -> 항상 일정한 12가지 색 중 하나로 반환 따라서 KEY : 홍길동의 사진 VALUE: 홍길동의 회원정보가 들어있는 서랍 해시 테이블 - Key, Value로 값을 저장 - 데이터간 순서 존재 X Hashing - Key - 키를 기준으로 값을 매핑 - 고유한 값 (중복 X) Hashing Function -> 임의의 데이터를 특정 값으로 매핑시키는 함수 좋은 해시 함수? - 키 값을 고르게 분포 시킨다 - 빠른 계산 - 충돌을 최소화 해시 충돌? - 키 값이 다른데 ..

NIC - 네트워크 장비와 LAN 사이의 통신을 준비 - 전송될 데이터를 병렬에서 직렬로 전환 - 빠른 전송을 위해서 데이터 코딩 및 압축 - Access Control 기능이 구현된 하드웨어와 펌웨어가 들어있다. - 저장소인 하드웨어, 제어와 저장을 위한 펌웨어 존재 - 유선 무선 연결 지원 - 이더넷, 기가비트 이더넷, 광섬유, 토큰링 CS8900A 특징 - 10Mbps를 지원하는 이더넷 컨트롤러 - IEEE 802.3 기준을 따르고 Direct ISA-BUS 연결을 사용 - EEPROM을 제공하여 점퍼설정을 최소화한 설정이 가능 - EEPROM에는 MAC주소 읽는 것 가능 - CSMA/CD는 충돌처리를 담당 충돌처리 CSMA/CD 기본 알고리즘 - 일정시간을 기다리는 것에 따라서 알고리즘이 결정됨 ..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자...

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은..

Stack - 후입선출 (Last in First Out LIFO) - 인터넷 브라우저 뒤로가기 - Ctrl + z - 다시 되돌리기 먼저들어간게 먼저나간다. Stack - push : 데이터 추가 - pop : 데이터 제거 - top : 맨 위 데이터 가져오기 - peek : 맨 위 데이터 가져오기 Queue - 선입선출 (First in Fast Out -FIFO) - 순서가 보장된 처리 - 사용자가 몰린 서버 - 놀이공원 Queue - push, offer, add : 큐 추가 - pop, poll : 큐 삭제 - peek : 큐 가져오기 Queue의 구조 Queue는 배열로 구현한다면,,, 매우 비효율적이다 - 값을 하나만 삭제해도 모든 원소들을 앞으로 당겨야 하기 때문에 (O (n)) - Lin..

https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 문제 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. 출력..

Double Linked List의 생김새는 다음과 같다. prev 라는 포인터가 생기므로 사용하는 자원은 늘어났다. 공간을 더 사용함에도 분명한 장점이 있다. double Linked list를 초기화 하면 더미노드를 다음과 같이 2개를 갖게 된다. Linked List에서 맨 마지막에 값을 하나 추가하는게 O (n) 의 시간이 걸렸지만 double Linked List에서는 Tail 의 노드가 있기 때문에 O (1) 만에 뒤에 값을 추가할 수 있게 된다. 또한 double Linked list는 값을 검색할때 TAIL에서도 시작 가능하기 때문에 뒤에 가까운 값들은 TAIL로 부터 시작하여 값을 검색하여 가지고 온다. 따라서 O (1/2 * n) 이지만, 점근법을 쓰면 O (n)임 Double Link..