분류 전체보기

[백준 10167번] 금광

10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이 www.acmicpc.net 목차 사전 지식 문제 접근 문제 풀이 사전 지식 2차원 좌표 압축에 대한 개념을 알고 있어야 한다. (링크) 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 가장 큰 연속합을 구하는 세그트리 문제를 이해하고 있어야 한다. (링크) 문제 접근 이 문제에 대한 순차적인 접근은 여기를 참고하기 바란다. 문제 풀이 이 문제의 핵심은 답이 되는 경우를 얼마나 효율적으로 탐색하는가이다. (좌표 압축을 ..

[백준 15561번] 구간 합 최대? 2

15561번: 구간 합 최대? 2 첫 번째 줄에 정수 N과 Q, U, V가 입력된다. (1 ≤ N, Q ≤ 105, - 5 ≤ U, V ≤ 5) 두 번째 줄에 정수 K1, K2, ..., KN이 주어진다. (-102 ≤ Ki ≤ 102) 세 번째 줄부터 쿼리가 www.acmicpc.net 목차 사전 지식 문제 풀이 사전 지식 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 가장 큰 연속합을 구하는 세그트리 문제를 이해하고 있어야 한다. (링크) 문제 풀이 $\small{U \times (K_i + K_{i+1} + \cdots + K_j) + V \times (j-i)}$ 의미 이 식은 $\small{(UK_i + UK_{i+1} + \cdots + UK_j) + ..

[백준 25639번] 수열과 최대 상승 쿼리

25639번: 수열과 최대 상승 쿼리 길이가 $N$인 수열 $a_1, a_2, ..., a_N$이 주어졌을 때, 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자. 1 k x: $a_k$를 $x$로 바꾼다. 2 l r: 구간 $[l, r]$의 최대 상승 값을 출력한다. 구간 $[l, r]$의 최 www.acmicpc.net 목차 사전 지식 문제 접근 문제 풀이 사전 지식 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 특히, 세그먼트 트리가 쿼리를 처리하는 과정을 이해하고 있어야 한다. 문제 접근 문제에서 길이가 $N$인 배열($\small{a_1, a_2, \cdots, a_N}$)과 $Q$개의 쿼리(query)가 주어진다. 이 배열에서 아래의 두 개의 query..

[백준 2336번] 굉장한 학생

2336번: 굉장한 학생 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 세 개의 줄에는 각 시험에서 1등인 학생부터 N등인 학생이 순서대로 주어진다. 학생의 번호는 1부터 N까지 매겨져 있다. www.acmicpc.net 목차 사전 지식 문제 접근 사전 지식 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 문제 접근 먼저, 대단한 학생과 굉장한 학생의 정의를 정확히 이해해야 한다. 학생 A의 등수가 $(a_1, a_2, a_3)$이고 B의 등수가 $(b_1, b_2, b_3)$일 때, $\small{a_1 < b_1} \large{,}$ $\small{a_2 < b_2} \large{,}$ $\small{a_3 < b_3}$를 만족하면 A는 B보다 ..

[백준 12015번] 가장 긴 증가하는 부분 수열2 - 세그먼트 트리

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 목차 사전 지식 DP 풀이 세그먼트 트리 풀이 가장 긴 증가하는 부분 수열 문제는 LIS(Longest Increasing Subsequences)로 잘 알려진 문제이다. 이번 글에서는 LIS 문제를 세그먼트 트리를 이용하여 풀어보겠다. 사전 지식 LIS의 DP(Dynamic Programming) 풀이를 이해해야 한다. (링크) 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) DP 풀이 - $\scriptsize{O(N^2..

[AtCoder] ABC295 A~D 업솔빙

안녕하세요 Gliver 입니다. 이번 글은 앳코더 ABC295에 대해 업솔빙하는 글입니다. 이번 대회는 약 60분 정도부터 시작하였다. A번 - 단순 구현 문제이다. B번 - 단순 구현 문제로 $O(R^2 \cdot C^2)$으로 해결할 수 있다. - 조금 더 효율적으로 구현하면 $O(R \cdot C \cdot 9^2)$으로 해결할 수 있다. C번 - 약간의 사고력을 요구하는 문제이다. - sort(정렬)을 이용하여 $O(N \cdot \log N)$으로 해결할 수 있다. - map 자료구조를 이용하여 $O(N \cdot \log N)$으로 해결할 수 있다. D번 - 대회가 끝나고 본 문제이며, prefix xor을 이용하면 $O(N)$으로 해결할 수 있다. A. Probably English $N$개..

환경 변수(PATH)란?

목차 환경 변수란? 환경 변수 PATH 환경 변수란? 환경 변수(Environment Variable)란 프로세스가 컴퓨터에서 동작하는 방식에 영향을 미치는, 동적인 값들의 모임이다. 프로세스(Process)는 컴퓨터에서 실행 중인 프로그램을 의미한다. 환경 변수가 필요한 이유 어떤 기관의 대표 번호로 전화를 하고 내가 원하는 부서를 말하면 그에 맞게끔 전화가 연결되는 경험을 해봤을 것이다. 만약에 대표 번호가 없다면 어떻게 될까? 해당 기관의 모든 부서에 전화를 하며 내가 원하는 부서를 찾아야 할 것이다. 환경 변수가 필요한 이유 또한 이와 비슷하다. 환경 변수는 프로세스가 어떠한 작업을 할 때 필요로 하는 정보를 손쉽게 접근/처리할 수 있도록 해주는 것이다. 위의 전화 예시를 살펴보면, 대표 번호라는..

IDE(통합 개발 환경)란?

목차 통합 개발 환경이란? 통합 개발 환경을 사용하는 이유 통합 개발 환경이란? 통합 개발 환경(IDE, Integrated Development Environment)은 코딩, 디버그, 컴파일, 배포 등 프로그램 개발에 관련된 모든 작업을 하나의 프로그램 안에서 처리하는 환경을 제공하는 소프트웨어이다. 무슨 소리인지 몰라도 괜찮다. 일단, 통합 개발 환경이 하나의 소프트웨어라는 점만 기억하자. 먼저, 통합 개발 환경이 무엇인지 살펴보기 전에 프로그램이 어떻게 실행되는지 살펴보도록 하자. 프로그램의 실행 과정 프로그램을 실행하는 과정은 크게 프로그래밍(코딩), 컴파일 으로 이루어진다. [프로그래밍(코딩)] 먼저 우리가 실행하고자 하는 코드를 짠다. [컴파일] 그 이후에 해당 파일을 우리가 원하는 언어의 ..