Study

2023년 7월 28일 알고리즘 문제풀 백준 11866번 문제 링크 1차 시도 나의 생각 처음엔 인덱스를 옮겨가면서 없어진 수를 표시하는 방법을 생각했다. 예를 들어 [[1,0].[2,0],[3,0],[4,0].[5,0]] 이런 식을 설정하고 빠지는 원소는 2번째 원소를 1로 바꿔주는 방법. 하지만 굳이 배열을 한번 더 복잡하게 만들어야 할 필요성이 없다고 생각했다. 따라서 덱으로 설정한 배열의 가장 앞 원소만 주목하되, 현재 뺄 차례인지 그냥 넘어갈 차례인지만 분류하면 되겠다고 판단하였다. 뺄 차례라면 popleft 한 후 따로 만들어둔 정답을 위한 배열에 append 하였다. 로직 자체는 어려움이 없었으나 예제에서 출력할 때 수열을 담는 괄호가 대괄호가 아니라 그냥 괄호 ‘<>‘였다. 이 부분이 신경쓰였지만 가장 먼저 ‘<‘를 배열의 앞에 넣어주고, 수열을 넣을 때 마다 숫자를 str로 바꾼 후 따옴표(,)와 공백( )을 붙여서 넣었다. 그 이후 *를 이용해 원소들만 출력했다. ...

2023년 7월 26일 알고리즘 문제 풀이 백준 6549 문제 링크 시도1 나의 생각 왼쪽부터 반복문을 통해 조건에 따라 스택에 사각형의 넓이를 넣고 수정하는 방법을 사용하였다. 스택에는 사각형의 높이와 너비가 원소인 배열을 집어넣었다. 예를 들어, 이번 사각형의 높이가 4라면 [4,1]을 넣어주는 방법이다. 맨 처음을 위해 스택이 비어있을 땐 조건과 무관하게 스택에 삽입하였다. 이후는 최근 스택에 들어간 사각형의 높이(이전 사각형)와 현재 반복문에서 주목하는 사각형(현재 사각형)의 높이를 비교하였다. 만약 현재 사각형의 높이가 더 크거나 같다면, 스택에 들어 있는 사각형은 너비를 1 늘렸다. 이후는 현재 사각형과 더 이전에 들어갔던 사각형들의 높이를 비교하였다. 그래서 너비를 1 늘려주거나 만약 현재 사각형의 높이가 작으면 너비를 늘리지 않고 스택에 들어 있는 사각형의 높이와 너비를 곱하여 넓이를 구한 후 최댓값과 비교하여 저장하는 방법을 사용하였다. 로직을 정리해보자면 다음과 같다. 문제에서는 각 케이스별로 출력해야 하지만, 편의를 위해 하나의 케이스에서 발생하는 로직만 표시하였다. ...

3.2 표준 표기법과 흔히 사용되는 함수 단조성 m≤n일 때 f(m)≤f(n)이면 함수 f(n)은 단조증가 m≤n일 때 f(n)≤f(m)이면 함수 f(n)은 단조감수 m<n일 때 f(m)<f(n)이면 함수 f(n)은 순증가 m<n일 때 f(n)<f(m)이면 함수 f(n)은 순감소 내림과 올림 x의 내림 : 임의의 실수 x에 대해 x 이하의 정수 중 가장 큰 수 x의 올림 : 임의의 실수 x 에 대해 x 이하의 정수 중 가장 작은 수 a mon n = a%n = a를 n으로 나눈 나머지(remainder, residue) ...

3. Growhth of Functions 일반적으로 알고리즘의 정확한 실행 시간을 계산할 필요가 없다. 입력이 충분히 크면 최고차항간 비교만 유의미하기 때문이다. ex) 병합정렬(nlgn), 삽입정렬(n^2) 처럼 이전에 공부한 애들을 보면 알 수 있음. 입력이 충분히 커서 실행 시간의 증가율의 상대적 순서만 볼때, 우리는 알고리즘의 점근적(asymptotic) 효율성을 따지게 된다. 입력 크기가 아주 작을 때를 제외하고는 일반적으로 최선의 선택이 될 수 있다. 즉, 일반적인 상황이란 최고차항의 차수로 실행시간의 차이를 비교하는 때를 말하는데 이 때는 점근적으로 접근하게 된다. ...

11.5 웹서버 11.5.1 웹 기초 Clients 와 servers 는 HyperText Transfer Protocol(HTTP)를 사용하여 의사소통한다. Client와 server는 TCP 연결을 설립한다. client는 컨텐츠(content)을 요구한다(request) server는 요청된 컨텐츠에 응답한다(respond). client와 서버는 연결을 끊는다(결국 언젠가는) 11.5.2 Web content 웹 서버는 **컨텐츠(content)**를 client에게 반환한다. content : 연관된 MIME(Multipurpose Internet Mail Extension) 타입을 갖는 바이트 배열 ex. MIME 타입의 예시 text/html HTML document text/plain Unformatted text image/gif Binary image encoded in GIF format image/png Binary image encoded in PNG format image/jpeg Binary image encoded in JPEG format Static and Dynamic content HTTP 응답에서 반환된 컨텐츠는 **정적(static)**일수도 **동적(dynamic)**일수도 있다. ...

11.6 종합 설계: 소형 웹 서버 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 /* * tiny.c - A simple, iterative HTTP/1.0 Web server that uses the * GET method to serve static and dynamic content */ #include "csapp.h" void doit(int fd); void read_requesthdrs(rio_t *rp); int parse_uri(char *uri, char *filename, char *cgiargs); void serve_sattic(int fd, char *filename, char *cgiargs); void get_filetype(char *filename, char *filetype); void serve_dynamic(int fd, char *filename, char *cgiargs); void clienterror(int fd, char *cause, char *errnum, char *shortmsg, char *longmsg); int main(int argc, char **argv) { int listenfd, connfd; char hostname[MAXLINE], port[MAXLINE]; socklen_t clientlen; struct sockaddr_storage clientaddr; /* Check command-line args */ if (argc != 2) { fprintf(stderr, "usage: %s <port>\n", argv[0]); exit(1); } listenfd = Open_listenfd(argv[1]); while (1) { clientlen = sizeof(clientaddr); connfd = Accept(listenfd, (SA *)&clientaddr, &clientlen); Getnameinfo((SA *) &clientaddr, clientlen, hostname, MAXLINE, prot, MAXLINE, 0); printf("Accepted connection from (%s, %s)\n", hostname, port); doit(connfd); Close(connfd); } } TINY main 반복실행 서버로 명령줄에서 넘겨받은 포트로의 연결 요청 듣는다. ...

CHAPTER 11. 네트워크 프로그래밍 웹 검색, 이메일 메시지, 온라인 게임 등 모두가 네트워크 응용을 사용 11.1 클라이언트-서버 프로그래밍 모델 모든 네트워크 응용 프로그램은 Client-server 모델에 기초 : 1개의 server process + 1개 이상의 client process로 구성 SERVER : 일부 리소스를 관리, 조작해서 Client를 위한 일부 서비스를 제공 예시 웹 서버 : 디스크 파일들을 관리, CLIENT를 대신해서 이들을 가져오고 실행 FTP 서버 : CLIENT를 위해 저장하고 읽어오는 디스크 파일들 관리 이메일 서버 : CLIENT를 위해서 읽고 갱신하는 스풀 파일 관리 CLIENT-SERVER 모델의 근본적인 연산은 트랜잭션(transaction), ...

CHAPTER 3 프로그램의 기계수준 표현 3.7 프로시저 프로시저 호출 : 스프트웨어에서의 주요 추상, 지정된 인자들과 리턴 값으로 특정 기능을 구현하는 코드를 감싸주는 방법을 제공 잘 설계된 소프트웨어 : 무슨 값이 게산되는가, 이 프로시저가 프로그램 상태에 무슨 효과를 갖는가 에 대한 간결한 인터페이스 정의 제공 일부 동작의 구체적인 구현은 감춰주는 방식으로 프로시저를 추상화 메커니즘으로 이용 ex. 프로시저 P가 프로시저 Q를 호출, Q가 실행한 후 다시 P로 리턴 제어권 전달 : 프로그램 카운터는 진입할 때 Q에 대한 코드의 시작주소로 설정되고, 리턴할 때는 P에서 Q를 호출하는 인스트럭션 다음의 인스트럭션으로 설정되어야 함 데이터 전달 : P는 하나 이상의 매개변수를 Q에 제공할 수 있어야 하며, Q는 다시 P로 하나의 값을 리턴할 수 있어야 함. 메모리 할당과 반납 : Q는 시작할 때 지역변수들을 위한 공간을 할당할 수도, 리턴할 때 이 저장소를 반납할 수 있음. 3.7.1 런타임 스택 C언어와 다른 대부분의 언어에서의 프로시저 호출 동작방식 : 스택 자료구조가 제공하는 후입선출 메모리 관리 방식을 활용 ...

Chapter 3 프로그램의 기계수준 표현 컴퓨터 : 데이터를 처리하고, 메모리를 관리하고, 저장장치에 데이터를 읽거나 쓰고, 네트워크를 통해 통신하는 등의 하위 동작들을 인코딩한 연속된 바이트인 기계어 코드(machinc code)를 실행한다. 컴파일러 : 프로그램 언어의 규칙, 대상 컴퓨터의 인스트럭션 집합, 운영체제의 관례 등에 따라 기계어 코드 생성 GCC C 컴파일러 : 기계어 코드를 문자로 표시한 어셈블리 코드의 형태로 출력을 만들어 프로그램의 각 인스트럭션 생성 GCC : 어셈블러와 링커 호출 => 어셈블리 코드로부터 실행 가능한 기계어 코드 생성 ...

삽입 정렬 : 점진적인 방법 사용 원소 A[j]를 정렬된 부분 배열 A[1 .. j-1]의 적절한 위치에 삽입 2.3.1 분할정복 접근법 재귀적 구조 : 주어진 문제를 풀기 위해 자기 자신을 재귀적으로 여러 번 호출함으로써 밀접하게 연관된 부분 문제를 다룸. => 분할정복 접근법 분할정복 접근법 : 전체 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고, 부분 문제를 재귀적으로 품. 찾은 해를 결합하여 원래 문제의 해를 만들어 낸다. 분할정복의 3단계 ...