https://www.acmicpc.net/problem/10986누적합(prefix sum)먼저 누적합이란 나열된 수의 누적된 합을 말한다. 만약 [1, 2, 3, 4, 5] 라는 배열이 있고, 이 배열을 누적합으로 나타낸다면 [1, 3, 6, 10, 15] 가 된다. 보통 반복문을 통해 `0번 index부터 4번 index까지의 누적합`을 구한다면 5번의 수행동작이 필요하다. 즉 O(N)의 시간 복잡도를 갖는 것이다. 하지만 누적합을 사용하여 `0번 index부터 4번 index까지의 누적합`을 구한다면 누적합 배열의 4번 index 값을 꺼내오기만 하면 되기 때문에 O(1)의 시간 복잡도를 갖는다. 그렇다면 `2번 index부터 4번 index까지의 누적합`을 구하기 위해서는 어떻게 해야할까? (1..

https://www.acmicpc.net/problem/11444인사이트이번 문제는 우리들이 사랑하는 피보나치 수열이다. 피보나치 수열이 골드2까지 난이도가 책정된 이유에는 입력값의 크기 제한에 있다. 일반적으로 1초에 대략 1억번 정도의 연산이 처리된다는 것을 감안하면, 입력값의 최대값이 1000억이기 때문에 dp를 사용해서 O(N)의 시간 복잡도로 처리해도 시간 초과가 날 것임을 예상할 수 있다. 그렇기 때문에 피보나치 수열의 일반항으로는 어떤 짓을 해도 시간초과를 해결할 수 없을 것이다. 해서, 이 피보나치 수열의 일반항에서 시간 처리를 극적으로 줄일 점화식을 고안해내야 한다. 여기서 한가지 더 생각해보면 1000억이란 숫자를 1억 내로 안정적으로 줄이려면 제곱근으로 접근하는 것 외에는 거의 방법..

1107번: 리모컨첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이www.acmicpc.net 문제 풀이 고장나지 않은 버튼들만을 이용해서 목표 채널까지 버튼을 가장 적게 눌러 도착하면 된다. 그런데 입력 조건을 보면 목표 채널의 최대값이 500,000인 것을 확인할 수 있다. 즉, 채널을 1부터 하나씩 모두 검사해도 처리시간이 매우 적게 나온다는 것이다.그렇다면 이 문제는 브루트포스를 사용해 손쉽게 해결할 수 있을 것 같다. 그렇다면 우리는 최악의 경우인 목표 채널이 500,000 번이고, 9를 제외한 모든 숫자가 고장났다고 했을 때를 감..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제 풀이 위 문제의 주제는 최소한의 작업 시간으로 땅을 평탄화시키는 것이고, 이를 잘 생각해보면 최소한의 작업 시간으로 땅을 평탄화를 시켰을 때 나올 땅의 높이를 구하면 된다는 것을 알 수 있다. 마침 땅의 높이도 ( 0 Number(item))); let [N, M, B] = input.shift(); let blocks = [].concat(...input); let min_height =..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 위 문제는 전형적인 동적 계획법 (Dynamic Programming), DP 문제이다. 동적 계획법(DP)의 정의는 큰 문제를 작은 문제로 나누어 푸는 방식을 말한다. 큰 문제를 작은 문제로 나누어 푸는 방식을 동적 계획법(DP)이라고 부른다면 분할과 정복과 어떤 차이가 있는지 궁금할 수 있다. 가장 큰 차이점은 동적 계획법은 분할과 정복과 다르게 하위 문제의 해결이 상위 문제에서 사용 되기 때문에, 하위 문제의 해결을 재사용한다는 것이다. 그리고 이렇게 하위 문제를..

발단 우테코 프리코스가 끝나고 나는 심심할 때면 티스토리 방문 통계를 보곤 했다. 방문 통계에는 유입 경로가 나와 있는데, 내가 우테코 증빙자료로 첨부해 놓은 주소와 같은 경로로 들어온 흔적이 보이면 우테코님들께서 다녀가신 것 같은 기분이 들었기 때문이다. 친구는 내가 이렇게 시도 때도 없이 불멍 때리듯이 방문 통계로 통멍을 때리는 것을 보고, 그럴거면 차라리 글에 방문자가 생길 때마다 알림을 보내는 일종의 게시글 현관종(?) 기능을 만들어보는건 어떠겠냐 물었고, 흥미가 생긴 나는 기말고사가 끝나기만을 기다렸다 마지막 시험이 끝나자마자 만들어봤다. 기능 구조는 아래와 같다. 서버를 하나 만들고 배포한다. 서버에 이미지 파일을 호스팅한다. 서버 코드에 사용자 정의 미들웨어를 추가하여 나의 로컬 폴더의 이미..