rhrnald's 코딩

Range minimum은 배열이 주어져 있을 때, 연속한 구간의 최솟값을 구하는 것을 의미한다. 최솟값을 여러 구간에 대해 반복적으로 구하는것이 Range Minimum Query, 줄여서 RMQ라 부른다. 다양한 방법이 존재하여 PS를 처음 접하는 사람들이 한번 보고 넘어가기 좋은 내용인거 같다. 다음과 같은 노테이션을 사용하겠다. n : 배열의 길이 X[1~n] : 주어진 배열 q : 쿼리의 개수 xi, yi : i번째 쿼리, X[xi]~X[yi] 중 최소인 값 1. 단순한 방법 전처리 : 無 업데이트 : 無 query당 : O(n) 특이사항 : 초등학생도 짤 수 있음 그냥 전부 탐색해주는 방법. 매 번 (l-r)개의 숫자를 직접 확인해보며 최솟값을 찾아주는 방법이다. 구간의 길이에 따라 달라지지만..

PS가 뭔지 잘 모르거나 처음 접하는 사람에게 나는 이 문제를 소개 시켜 주고 싶다. https://www.acmicpc.net/problem/8907 8907번: 네온 사인 문제 시흠이는 최근에 레스토랑 "삼각형"을 오픈했고, 시흠이는 레스토랑을 상징하는 네온 사인을 주문했다. 네온 사인은 총 N개의 꼭짓점이 원의 둘레를 따라 찍혀져 있다. 그리고, 총 N * (N-1) / 2개의 야광 튜브가 꼭짓점을 연결하고 있다. 야광 튜브는 두 가지 색(빨간색과 파란색)이 있다. 시흠이는 한 번에 한 삼각형만 불을 밝히려고 한다. 이때, 삼각형의 모든 변은 색상이 같아야 하고, 꼭짓점이 서로 이어져 있어야 한다. 그는 이러한 단색 삼각 www.acmicpc.net 굉장히 좋은 문제이다. 주관적이긴 하지만 좋은 문..

블로그에 어떤 글을 올려야되나 고민을 해보았다. 알고리즘이나 문제풀이 등은 시간도 많이 걸리며 다른 블로그에 더 잘 정리되있을 것 같고 마땅히 올릴 글이 없다. 일기 식으로 써나가거나 시간이 여유로울때 알고리즘 몇개 정리해보는 식으로 정리 해봐야지. 이번에는 블로그를 시작한 겸 지금까지 어떻게 코딩 공부를 해왔는지 글을 써보려한다. 처음 PS를 시작한 건 랭킹이 멋있어 보여서였다. 당시에 백준에서 푼 문제들을 기준으로 레이팅을 매겨주는 애플리케이션?이 있었는데 해보고 싶다는 생각이 들었고 백준 계정을 만들게 되었다. 게임 같다고 느껴졌고 재밌어 보였던 것 같다. 게임을 너무 좋아해서 탈이다. 그래도 요즘 Codeforces도 그렇고 대부분 PS대회들이 게임 같아서 흥미를 잃지 않고 꾸준히 할 수 있는 것..

블로그를 시작해본다. 글도 못쓰고 남에게 보여주는 것도 별로 좋아하지 않아 블로그 같은 것을 관리할 생각이 별로 없었다. 근데 이번에 친구의 블로그를 보며 도움이 될거 같다는 생각이 들었고 내친김에 한번 만들어 보았다. PS공부를 하면서 새로운 걸 공부하거나 예전에 익혔던 것들을 간간히 정리하는대 이용해볼 생각이다. 도메인을 간단히 만들었으니 내 PS 아이디를 아는사람들이 한번쯤 들어와 볼수도 있지 않을까?