CS

CS/Algorithm
[Algorithm] Segment tree with Lazy propagation (BOJ 10999)
• segment tree with lazy propagation algorithm의 필요성segment tree는 구간에 대한 query를 O(logN)에 수행할 수 있도록 한다. 한 index에 대한 update를 수행할 경우에 update의 time complexity는 역시 recursive call에 의해서 O(logN)에 수행된다. 만약 한 index가 아니라 구간 [L, R]에 대한 update를 수행할 경우 [L, R]에 속한 모든 index에 대하여 update를 해 주어야 하므로 O((R-L+1)logN), 일반적으로 쓰면 O(NlogN)의 긴 수행 시간이 필요하게 된다. 이를 해결하기 위해서는 일종의 optimization이 필요한데, 이것이 바로 lazy propagation이다. ..
→2021.08.06
CS/PS
[BOJ] 2473번 : 세 용액
• 문제 설명 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net KOI 2010 고등부 1번 문제이다. 푸는 방법은 두 가지가 있는데, two pointers로 푸는 방법과 binary search로 푸는 방법이 있다. two pointers로 풀면 time complexity는 O(N^2)으로 풀 수 있고, binary search로 풀면 O(N^2*logN)으로 풀 수 있다. 다만 two pointers로 풀기 위해서는 ..
→2021.07.31
CS/PS
[BOJ] 7578번 : 공장
2013년도 KOI 도대회 고등부 3번 문제이다. 간단한 segment tree 문제처럼 보였는데, TLE를 3번 받았다. 해법은 간단하다. 1행의 케이블의 번호를 1, 2, 3, 4, 5의 오름차순으로 정렬하고, 2행의 케이블의 번호를 이에 맞게 다시 부여해준다. 그러면 예제의 경우 2, 4, 1, 3, 5가 되는데, 교차는 한 기계에서 그 앞에 자신보다 큰 숫자가 있을 경우에 발생한다. 예제의 경우를 보자. 2의 경우 교차는 0이다. 4의 경우도 교차가 0이고, 1의 경우 앞에 2와 4가 있으므로 교차가 2번 발생하고, 3의 경우는 4로 인해서 한 번, 5는 발생하지 않는다. 따라서 교차횟수는 총 3회이다. 따라서 https://jordano-jackson.tistory.com/33에서 다루었던 BO..
→2021.07.29
CS/PS
[BOJ] 2517번 : 달리기
https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 2012년도 정올 고등부 2번 문제다. segment tree와 좌표압축을 사용하면 된다. 실력을 기준으로 segment tree를 만들면 특정 실력의 선수를 확인할 때 O(logN)만에 최대 등수를 확인할 수 있다는 아이디어를 얻을 수 있다. 여기서 중요한 점은 앞에서부터 차례로 update를 해 주고 query를 처리하여서 i번째 선수까지만 tree에 반영이 될 수 있도록 하는 것이다. ..
→2021.07.28
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 뿐만 아니라..
→2021.07.25
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))와 같은 형식으로 리턴..
→2021.07.24

• 이전
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 다음