본문 바로가기
728x90

프로그래밍43

[네트워크] 응용 계층 : Application layer Introduction응용 계층(Application layer)은 프로토콜 스택 가장 위에 있는 계층으로, 네트워크를 사용하는 응용 프로그램 간 소통을 위해 제작되었다.  Network Structure1. Client-Server ArchitectureServerAlways-on hostPermanent IP addressExamples: Web servers, mail servers, DNS serversClientDynamically connectedMay have dynamic IP addressesCommunicate with serversExamples: Web browsers, email clientsPros : stabilityCons : scaling cost2. Peer-to-Peer.. 2024. 10. 4.
[데이터베이스 시리즈] SQL 문법 정리 목차1. SQL이란2. SQL 자료형3. DDL    1) CREATE, ALTER, DROP, RENAME    2) VIEW4. DML    1) SELECT, INSERT, UPDATE, DELETE    2) 서브 쿼리    3) CTE    4) 집합 연산자    5) JOIN    6) 여러가지 함수들5. DCL    1) GRANT, REVOKE6. TCL    1) COMMIT, ROLLBACK, SAVEPOINTSQL이란Structured Query Language의 줄임말으로, 구조화된 질의어라는 뜻이다. 1970년대 초, IBM 사 San Jose의 연구실에서 System R이라는 DBMS 개발 프로젝트에서 최초로 구현되었으며, 그것이 다듬어져 현대의 SQL이 되었다. SQL은 ANS.. 2024. 10. 1.
[알고리즘 시리즈] 탐욕 알고리즘 : Greedy Algorithm 탐욕 알고리즘 : Greedy Algorithm목차1. 그리디 알고리즘의 목적2. 그리디 알고리즘의 적용 조건3. 그리디 알고리즘 적용 예시1. 그리디 알고리즘의 목적현재의 선택이 다음 단계에 끼치는 영향을 고려하지 않고 전체 문제의 최적의 해를 구한다. 2. 그리디 알고리즘의 적용 조건1) Greedy-choice property현재 최선의 선택이 미래에도 최선의 선택인가이 속성을 만족하지 않는 그리디 알고리즘은 huristic한 해결책을 제시한다. 2) Optimal Substructure부분 문제의 해결 방법으로 전체 문제도 해결할 수 있는가 3. 그리디를 적용한 대표적인 문제들1) Activity Selection Problem시작 시간과 끝 시간이 있는 활동이 여러개가 있을 때, 주어진 구간에서.. 2024. 10. 1.
[백준 시리즈] 2812번 : 크게 만들기 - 골드3 / Python 2812번 : 크게 만들기출처 : 백준 /  2812번: 크게 만들기 (acmicpc.net) 사용 알고리즘 : 스택, 그리디 문제 설명N자리 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 제한시간 제한 : 1초 / 메모리 제한 : 128MB1  문제 풀이1단계 : 최대 시간복잡도는 얼마인가?N이 50만이므로 O(NlogN) 이하의 알고리즘이 필요하다. 2단계 : naive하게 해결해보자횟수를 모두 사용하더라도 맨 앞자리에 제일 큰 숫자를 배치하는 것이 이득이다. i번째 숫자가 i+1번째 숫자보다 크면 남기고 작으면 지워야한다는 점에서 스택이 연상된다. 3단계 : 핵심 아이디어는 무엇인가넣을 숫자보다 작은 숫자를 K번 이하로 지우면서 스택에 삽입한다. 모든 숫자를 스택에 다 넣었음에도.. 2024. 9. 23.
[알고리즘 시리즈] 투 포인터 : Two Pointer 투 포인터 : Two Pointer목차1. 투 포인터의 목적2. 투 포인터의 적용 조건 및 적용 상황3. 투 포인터의 사용법4. Meet in the middle1. 투 포인터의 목적특정 조건에 따라 두 포인터를 조작하여 O(n) 만에 특정한 값을 찾는다. 2. 투 포인터의 적용 조건 및 적용 상황1) 검색을 위해 사용한다.특정한 조건을 만족하는 순서쌍을 찾는 문제에서 사용되는 투 포인터가 이 경우이다. 리스트가 오름차순 또는 내림차순으로 정렬되어 있어야 한다.  2) 한 배열을 정렬하기 위해 사용한다.quick sort 정렬 연산 시 사용되는 투 포인터가 이 경우이다.특별한 조건이 필요하지 않다. 3) 두 배열을 비교할 때 사용한다.merge sort의 병합 단계가 이 경우이다.두 배열이 오름차순 또는.. 2024. 9. 21.
[백준 시리즈] 2666번 : 벽장문의 이동 - 골드5 / Python 2666번 : 벽장문의 이동출처 : 백준 /  https://www.acmicpc.net/problem/2666사용 알고리즘 : 브루트 포스 문제 설명1. 항상 2개의 문이 열려있는 벽장 N개가 있다.2. 문을 열 벽장의 순서에 따라서 벽장문 이동 횟수의 최솟값을 구하라.3. 벽장문은 옆 벽장이 비어있어야 이동가능하다.  제한시간제한 : 1초 / 메모리 제한 : 128 MBN (3 문을 열 벽장의 개수는 최대 20개이다. 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?모든 경우의 수를 고려하는 브루트포스로 문제를 해결했을 때, 최악의 경우에도 20*2^20번의 연산만이 수행되기 때문에 브루트포스 알고리즘으로 해결할 수 있다. 2단계 : naive 하게 생각해 보자현재 더 가까운 쪽의 벽장문을 열더라도 그.. 2024. 9. 21.
[백준 시리즈] 21318번 : 피아노 체조 - 실버 1 / Python 21318번 : 피아노 체조출처 : 백준 /  21318번: 피아노 체조 (acmicpc.net) 사용 알고리즘 : 누적 합 문제 설명1. Q번의 쿼리에 대해 x번부터 y번까지 악보를 연주할 때 실수하는 곡이 몇 곡인지 찾아라.2. 각 악보마다 난이도가 주어지며 숫자가 높을수록 높은 난이도이다.3. 현재 연주하는 악보가 다음에 연주할 악보보다 어려우면 실수하며, 마지막 곡은 무조건 실수하지 않는다. 제한시간 제한 : 0.5초 / 메모리 제한 : 1024MB N(1 ≤ N ≤ 100,000) Q(1 ≤ Q ≤ 100,000) x, y(1 ≤ x ≤ y ≤ N)  문제 풀이1단계 : 최대 시간복잡도는 얼마인가?O(QlogN) 2단계 : naive하게 해결해보자x번부터 y번까지 실수의 총합을 구하는 문제이.. 2024. 9. 17.
[백준 시리즈] 1024번 : 수열의 합 - 실버 2 / Python 1024번 : 수열의 합 - 실버 2 / Python출처 : 백준 /  1024번: 수열의 합 (acmicpc.net) 사용 알고리즘 : 수학 문제 설명N과 L이 주어질 때, 합이 N이면서 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하시오. 제한시간 제한 : 2초 / 메모리 제한 : 128MBN은 1,000,000,000 이하의 자연수이다.L은 2이상 100이하인 자연수이다.  문제 풀이1단계 : 최대 시간복잡도는 얼마인가?시간복잡도를 가늠하기 어렵다. N을 기준으로 시간복잡도를 구성한다면, O(logN) 이하의 알고리즘이 필요하다. 2단계 : Naive하게 풀어보자배열의 요소는 1~N까지 순차적이므로 등차 수열의 합 공식을 이용하여 순서쌍을 선택하는 문제로 변경할 수 있다. 배열이.. 2024. 9. 17.
[네트워크 시리즈] 소켓 프로그래밍 : Socket Programming 소켓 프로그래밍 : Socket Programming목차1. 소켓(Socket)이란 무엇인가2. 소켓을 사용하지 않는다면3. 소켓 API를 이용한 통신 과정4. Java Socket API를 이용하여 서버와 통신해보자5. blocked 상태를 해소하는 방법1. 소켓(Socket)이란 무엇인가OS에서 네트워킹을 위해 프로토콜 스택을 쉽게 이용할 수 있도록 제공하는 인터페이스이다. 소켓을 이용하기 위해선 서버의 포트 번호(0~65535)와 IP 주소가 필요하다. TCP, UDP 프로토콜 마다 다른 소켓 API가 존재한다.  2. 소켓을 사용하지 않는다면클라이언트와 서버 애플리케이션에서 프로토콜 스택을 헤더에 적층하고 해석하는 과정을 일일히 정의해야 하므로 번거로워 진다. 3. 소켓 API를 이용한 통신 과정.. 2024. 9. 16.
728x90

티스토리툴바