cs
전체 글

전체 글

    [Web] HTTP 프로토콜의 이해
    CS/HTML·CSS·JavaScript

    [Web] HTTP 프로토콜의 이해

    인터넷(network 통신)의 이해 • 인터넷 != world wide web www는 인터넷 기반의 대표 서비스 중 하나이다. 각각의 서버는 포트 값으로 구분되어 동작한다. 이름 프로토콜 포트 기능 WWW HTTP 80 웹서비스 Email SMTP/POP3/IMAP 25/110/114 이메일 서비스 FTP FTP 21 파일 전송 서비스 DNS TCP/UDP 53 네임 서비스 NEWS NNTP 119 인터넷 뉴스 서비스 • 인터넷 (Internet) TCP/IP 기반의 네트워크가 전 세계적으로 확대되어 하나로 연결된 네트워크들의 네트워크(네트워크의 집합체) HTTP(Hypertext Transfer Protocol)이란? • Tim Berners-Lee와 그가 속한 팀은 CERN에서 HTML 뿐만 아니라..

    [BOJ] 10868번 : 최솟값
    CS/PS

    [BOJ] 10868번 : 최솟값

    https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net segment tree 개념 문제이다. 입력과 출력도 int 범위 내이고, update도 없으므로 크게 어려운 것 없는 문제이다. 다만 최솟값이라는 특성 상 initializing을 할 때 min(init(범위1), init(범위2)) 로 tree 값을 정해주고, query가 주어졌을 때에도 min(query(범위1), query(범위2))와 같은 형식으로 리턴..

    CS/PS

    [BOJ] 1781번 : 컵라면

    https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net priority queue(max heap)과 greedy 문제다. 중요한 아이디어는 앞 시간부터 데드라인을 계산하면 고려할 대상이 너무 많아지니 뒷 시간부터 데드라인을 계산하는 것이다. 만약 현재가 시간 t라면, 데드라인이 t보다 큰 모든 문제 중에서 가장 점수가 큰 문제를 골라서 해결하면 된다. 이 경우 시간 t까지 보았을 때 얻을 수 있는 점수 중에서 가장 큰 점수를 얻게 되므로 시간 1이 되었을 때..

    CS/Algorithm

    [Algorithm] 선분교차(Line-segment intersection) 판정 알고리즘

    • Line-segment intersection 판별 알고리즘의 필요성 Line-segment의 교차 판정은 PS에서 흔히 다뤄지는 문제이다. 예컨대 네 점 이 주어졌다고 하자. 이 때 다음과 같은 두 선분을 생각할 수 있다. 이때 두 선분의 교차 관계를 판단하는 가장 직관적인 방법은 역시 slope를 구해서 일차 함수로 표현한 뒤 교점을 구하여 범위를 인식하는 방법이다. 위의 두 line-segment의 intersection을 일차 함수를 이용하여 파악해 보자. 위와 같은 두 선형 함수를 만들 수 있고, 두 함수의 교점을 쉽게 구할 수 있다. 구한 교점에 대하여 x값과 y값의 범위를 계산하면 선분의 교차 관계를 매우 직관적으로 얻을 수 있다. 다만 이 방법엔 문제가 있다. 다음 문제들을 떠올릴 수 ..

    [BOJ] 1462번 : 퀴즈쇼
    CS/PS

    [BOJ] 1462번 : 퀴즈쇼

    https://www.acmicpc.net/problem/1462 1462번: 퀴즈쇼 첫째 줄에 문제의 개수 N과 보너스 점수를 얻는데 필요한 코인의 개수 M이 주어진다. (1 ≤ N, M ≤ 500,000) 둘째 줄에는 각 문제에 해당하는 점수가 1번 문제부터 주어지고, 셋째 줄에는 각 문제에 www.acmicpc.net 아주 재미있는 DP 문제이다. 얼핏 보면 2006정올 도대회 초등부 4번 '계단 오르기'(https://www.acmicpc.net/problem/2579)와 비슷해 보이지만 다르다. 처음엔 비슷한 문제로 보고 접근했다가 틀렸다. 가장 다른 점은 현재 풀고 있는 문제 i와 현재 가지고 있는 코인 개수 j를 가지고 2차원 DP table을 짜면 time complexity와 space ..

    [BOJ] 1637번 : 날카로운 눈
    CS/PS

    [BOJ] 1637번 : 날카로운 눈

    https://www.acmicpc.net/problem/1637 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 한참을 들여다봐도 풀 방법이 떠오르지 않아 푼 사람들로부터 힌트를 얻어 풀었다. binary search의 참신한 적용 문제이다. 그냥 brute-force를 쓰면 time complexity가 대략 20000* 2^32가 나오게 된다. 고로 다른 방법을 찾아야 한다. 이 문제에서는 범위를 잘라서 그 안에 있는 수들의 개수를 모두 세었을 때, ..

티스토리툴바