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에 반영이 될 수 있도록 하는 것이다. ..

인터넷(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 뿐만 아니라..

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))와 같은 형식으로 리턴..

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

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

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 ..

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가 나오게 된다. 고로 다른 방법을 찾아야 한다. 이 문제에서는 범위를 잘라서 그 안에 있는 수들의 개수를 모두 세었을 때, ..

PS공부하기 싫어서 쉬워보이는 문제로 아무거나 골라 풀었다. 의외로 재미있어서 좋았다. https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 아이디어는 역시 간단하다. 한 건물을 중심으로 다른 두 방향으로 쭉 뻗어나가면서 gradient를 계산해 주면 된다. 예를 들어 다음과 같은 입력에서 5번째 건물을 보자. 15 1 5 3 2 6 3 2 6 4 2 5 7 3 1 5 5번째 건물의 높이는 6이다. 어느쪽 방향이든 첫 번째 건물을 무조건 볼 수 있다..

https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 그다지 어렵지는 않은 DP 문제이다. 다만 한 가지 아이디어가 중요한데, 마름모가 네 변으로 구성되므로 그 네 변의 길이를 brute-force로 구하지 말고 memorization을 사용해서 구하겠다는 아이디어만 내놓으면 된다. 나는 먼저 UpRight방향, UpLeft방향, DownRight방향, DownLeft방향에 대해서 그 map을 마지막으로 하는 가장 긴 연속적인 1의 길이를 DP table에 저장하였다. 이 과정에서는 directi..