본문 바로가기

CS

 (46)
[BOJ 11003번] 덱을 이용한 최솟값 문제 처음에 이문제를 보고 덱을 이용해서 원소를 앞뒤로 삭제 추가 해주면서 포인터를 이용해서 최솟값만 그때 그때 뽑아주면 된다고 생각했지만 최악의 경우 N은 1000000 인데 시간복잡도가 N^2logN 이 돼서 아무리 최적화 해봐도 통과되지 않았다. 일단 원소가 앞에서는 삭제되고 뒤에서는 추가 되니까 덱을 발상하는것을 어렵지 않았다. 그리고 한칸씩 슬라이딩 윈도우가 지나가면서 변하는 최솟값을 구하는것인데 이부분을 구현하기가 어려웠다. 그래서 답을 확인했고 이번에 덱의 활용법을 새로 배웠다. 일단 한칸씩 이동하기 때문에 덱 전체를 그때마다 sorting하는것은 너무 낭비라는것을 이해해야 한다. 이 부분에서 시간초과가 났다 이미 알고있는 원소를 충분히 활용하면서 최솟값을 찾아내는 방법은 덱의 성질을 이용하는 것..
모두의 네트워크(3) 물리계층 트위스트 페어 케이블(UTP, STP)을 일반적으로 랜 케이블이라고 부름 랜 케이블은 다이렉트 케이블, 크로스 케이블이 있음 크로스 케이블은 다이렉트 케이블과 달리 데이터 충돌을 막기위해 송신과 수신 선을 교차한 구조 다이렉트 케이블은 한쪽은 1,2번 송신 3,6번 수신 다른쪽은 1,2번 수신 3,6번 송신 크로스 케이블은 양쪽다 1,2번 수신 3,6번 송신 하지만 교차해서 충돌없이 통신 가능 리피터: 신호 증폭하는 기능을 가진 네트워크 중계 장비 (리피터) 허브: 포트를 가지고 여러대의 컴퓨터와 통신할수 있는 장비, 전기신호 정형 및 증폭(리피터) 한 포트에서 다른 포트로 데이터를 전송하면 나머지 포트에도 데이터가 전송됨 -> 보안 문제 발생 -> 더미 허브라고도 함
모두의 네트워크(2) 프로토콜: 통신하기 위한 규약 OSI 모델: 데이터를 응용 계층, 표현 계층, 세션 계층, 전송 계층, 네트워크 계층, 데이터 링크 계층, 물리 계층인 7개의 계층으로 나누어서 전송하는 모델 응용 계층: 애플리케이션 서비스 제공 표현 계층: 데이터 변환 세션 계층: 세션 체결, 통신방식 결정 전송 계층: 신뢰할수 있는 통신 구현 네트워크 계층: 다른 네트워크와 통신하기위한 경로 설정 및 논리 주소 결정 데이터 링크 계층: 네트워크 기기 간의 데이터 전송 및 물리주소 결정 물리 계층: 시스템 간의 물리적인 연결과 전기 신호 변환 및 제어 TCP/IP 모델: 데이터를 응용 계층, 전송 계층, 인터넷 계층, 네트워크 접속 계층인 4개의 계층으로 나누어서 전송하는 모델 캡슐화와 역캡슐화: 캡슐화는 컴퓨터 통신에..
모두의 네트워크(1) 네트워크 구조 네트워크: 두개 이상의 컴퓨터 간의 연결 인터넷: 전 세계의 큰 네트워크부터 작은 네크워크까지 연결하는 거대한 네트워크 패킷: 컴퓨터 간의 데이터를 주고 받을때 네트워크를 통해 전달하는 데이터의 기본 단위(큰 데이터는 작은 패킷으로 분할) 랜(LAN)과 왠(WAN) 랜(LAN): 건물 안이나 특정 지역을 범위로 하는 근거리 통신 네트워크 왠(WAN): U+ 같은 통신회사인 인터넷 서비스 제공자(ISP)가 제공하는 서비스를 사용하여 구축한 광역 통신 네트워크 랜은 범위가 좁고 속도가 빠르며 오류가 발생할 확률이 낮음 왠은 범위가 넓고 속도가 느리며 오류가 발생할 확률이 높음 가정에서는 인터넷 서비스 제공자와 인터넷 공유기를 연결하고 유무선 랜을 통해 네트워크를 구성 회사에서 하는 랜 구성 D..
데이터 베이스 기본실습 스키마: 테이블(표)들를 그룹핑하는 일종의 폴더의 형태 데이터 베이스 서버: 스키마들의 집합 MySQL(Structured Query Language) -서버 실행 -mysql -uroot -p -스키마 생성 -CREATE DATABASE opentutorials; -스키마 삭제 -DROP DATABASE opentutorials; -스키마 보기 -SHOW DATABASES; -어떤 스키마를 사용할지 결정 -USE opentutorials; -현재 스키마에서 테이블 보기 -SHOW TABLES; CRUD CREATE -테이블 만들기 -CREATE TABLE topic( id INT(11) NOT NULL AUTO_INCREMENT, title VARCHAR(100) NOT NULL, description..
데이터베이스 데이터베이스 -특정 조직의 여러 사용자가 공유하여 사용할수 있도록 통합해서 저장한 운영데이터의 집합 -통합 데이터: 최소의 중복과 통제가능한 중복만 허용 -공유 데이터: 특정 조직의 여러 사용자가 함께 소유하고 이용 -저장 데이터: 컴퓨터가 접근할수 있는 매체에 저장된 데이터 -운영 데이터: 지속적으로 유지해야하는 데이터 데이터베이스의 특성 -실시간 접근: 실시간으로 응답 -계속 변화: CRUD를 통해 현재의 정확한 데이터 유지 -내용 기반 참조: 주소나 위치가 아니라 내용으로 참조 -동시 공유: 서로다른 또는 같은 데이터의 동시 사용 지원
백트래킹 백트래킹이란 무엇인가? -현재상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 (ex. 게임에서 현재상태에서 가능한 모든 선택지를 다 플레이 해보는 방법) 문제풀이에서 백트래킹의 활용방식은? -각 상태별로 여러가지 경우의수가 생기고 일일이 확인할 필요가 있을때 -분기점에 다시 되돌아올 마킹을 남겨야 할때 Code int n,m; int arr[10]; bool isused[10]; void func(int k){ if(k == m){ for(int i=0; i
메모리 할당 연속 메모리 할당 -프로세스 생성/종료 반복 -> Scattered hole 발생 -외부 단편화(External fragment) 발생: 메모리가 남지만 홀들로 쪼개져 있어서 프로그램 적재 불가 -할당방식 3가지: First-fit(최초 적합), Best-fit(최적 적합), Worst-fit(최악 적합) -메모리 낭비로 인해 페이징 기법 사용 페이징(Paging) -프로세스를 일정한 단위(page)로 자르고 메모리도 같은 단위(frame)로 자른다음 적재 -MMU안의 여러개의 relocation register를 이용하여 주소변환을 해주면 CPU는 연속적인것처럼 느낌 주소변환(Address Translation) -논리주소(Logical address) -CPU가 내는 주소(2진수) -상위 비트는 페이..

티스토리툴바