아롱이의 PS하는 블로그

C++에서는 어떤 자료형이 있고, 어떻게 연산이 진행되는지 구체적으로 알아볼 것이다.주로 PS에서 쓰이는 것들로 알아보자. 자료형 기본 빌트인(built-in) 자료형 void크기:0그냥 아무것도 아닌 자료형이다. 함수 반환 등에 쓰인다. nullpointerdecltype(nullptr)크기:0 논리형bool크기:1 byte범위:0~1예시:bool ok = (x>0); 문자형(signed) char크기: 1 byte범위: -128~127예시:char c='A';작은따옴표를 씀에 주의하자. 큰따옴표를 쓰면 string이다. unsigned char크기: 1 byte범위: 0~255예시:unsigned char s = 'A'; 왜 문자형인데 범위가 정수일까? 이는 사실 C++ 내에서 아스키로 문자를 저장..

다음 템플릿 코드를 먼저 살펴보자. 앞으로 C++로 코딩을 할 때는 웬만하면 여기서부터 시작 할 것이다.#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout ios::sync_with_stdio(false);는 입출력 속도를 매우 빠르게 올려준다. 자세한 원리는 다른 블로그들을 참고하자.그리고 2번째줄에서 using namespace std;를 써줬기때문에 이후 코드에서 그냥 cin, cout만 써줘도 된다. 그렇다. C++에서 입출력을 받을 때는 cin과 cout을 쓴다! 1. cout으로 출력하기 출력을 하는 방법은 간단하다. cout..

https://www.acmicpc.net/problem/2336 풀이일단 문제 설명은 살짝 복잡하지만 잘 읽고 보면, "Inverse Count 문제 유형의 응용이구나"를 알게 된다. 시험이 세 개 있는데, 위에서부터 A, B, C 시험이라고 하자. A에서 1등한 사람부터 살펴볼 것이다.약간의 관찰을 해 보면, A에서 1등한 사람부터 살펴볼 때, 그 사람의 (B에서의 등수, C에서의 등수)가 있을 것인데 이거를 하나씩 추가해나가다 보면, 이미 있던 사람의 B, C 등수보다 둘 다 등수가 크게 되는 경우가 존재하면 그 사람은 굉장한 학생이 아니다.이걸 효과적으로 관리해주기 위해서 세그먼트 트리를 이용한다. A에서 1등한 사람부터 살펴보는 데, 세그먼트 트리의 B에서의 등수 인덱스에 C에서의 등수 값을 넣..

https://www.acmicpc.net/problem/12858 풀이분명 느갱세의 응용 문제라고 들었는데, 느갱세 풀이는 어떻게 하는건지 생각하지도 못하고 오히려 느갱세를 안쓰는 풀이만 생각해버렸다. 먼저 차분 배열 트릭을 이용하면 Range Update를 딱 두 개의 노드에 대해서만 해주어도 된다는 점에서 시작하자.그런데, 잘 생각해보면 어떤 수 a, b, c, d, e의 gcd는 유클리드 호제법에 따라 다음과 같이 구해질 수도 있다. gcd(a, b, c, d, e) = gcd(a, |b-a|, |c-b|, |d-c|, |e-d|) 두 수의 차이는 차분 배열에서 이미 저장하고 있기 때문에, 차분 배열을 그냥 바로 세그트리화 시켜버려서 구간별 gcd를 구할 수 있을 것이다! 그런데 여기서 하나 고려..

나는 맥북을 쓴다.맥북의 장점은, 윈도우보다 좋다는 것이다. 그리고 무엇보다, C++ 컴파일러가 이미 기본적으로 맥에는 깔려있다!!!!!!!! 먼저 이 사이트에서 VSC를 다운받도록 하자.주변 사람들이 왜 지금까지 VSC를 안썼냐고 경악하던데, 파이썬 코더인 나는 원래 Pycharm을 썼다. https://code.visualstudio.com/ Visual Studio Code - Code Editing. RedefinedVisual Studio Code redefines AI-powered coding with GitHub Copilot for building and debugging modern web and cloud applications. Visual Studio Code is free an..

https://www.acmicpc.net/problem/1517 문제N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.입력첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2..

"파이썬으로 구현하는"시리즈 5분할 정복을 이용한 거듭제곱 가끔씩 백준 문제를 풀다가 보면 어떤 수의 거듭제곱을 매우 빠르게 구해야 할 때가 있다. 물론 나머지 연산을 포함해서. 예를 들어 $2^{100}$을 97로 나눈 나머지를 구한다고 하자.2를 100번 곱하는 식의 $O(N)$ 풀이는 시간초과가 난다. 분할 정복을 이용하면 이를 $O(log N)$으로 줄일 수 있다. 사실 구현은 매우 간단하다. $2^{100}$은 $2^{50}$을 두 번 곱한 것이라고 볼 수 있다. 이런식으로 계속 절반으로 줄여나가면서 계산하는 것이다.def mul(b, n): if n == 1: return b if n == 0: return 1 if n % 2 == 1: t..

https://www.acmicpc.net/problem/12771문제세계 경제는 유가에 많은 부분 의존한다. 그래서 석유를 발견하고 시추하는 새로운 방법이 여전히 연구되고 있다. 석유 기업의 이익은 얼마나 석유를 효율적으로 뽑아낼 수 있는지와 관련이 있다. 국제 석유 컨소시엄(ICPC)는 컴퓨터 시뮬레이션을 통해 석유를 어떻게 최선의 방법으로 뽑아낼 수 있는지 알아낼 수 있을 것으로 전망한다.석유를 효율적으로 뽑아내는 것은 날마다 어려워진다. 새로이 발견된 석유 샘은 하나의 덩어리를 이루지 않고 종종 여러 굴로 나뉘어 있기 때문이다. ICPC는 현재 그림 G.1과 같이 층층이 구성된 석유 샘에 관심을 갖고 있다.분석을 간단히 하기 위해 ICPC는 2차원인 경우만 고려한다. 즉, 석유 샘은 지면과 평행한..

https://www.acmicpc.net/problem/14428문제길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ ((10^9)))2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러개인 경우에는 인덱스가 작은 것을 출력한다. (1 ≤ i ≤ j ≤ N, 1 ≤ v ≤ ((10^9)))수열의 인덱스는 1부터 시작한다.입력첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ ((A_i)) ≤ (10^9))셋째 줄에는 쿼리의 개수 M이 주어..

https://www.acmicpc.net/problem/11437문제N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.입력첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.출력M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다. 풀이LCA는 어떤 트리에서 두 정점이 주어질 때 정점들의 최소 공통 조상을 ..