아롱이의 PS하는 블로그

https://www.acmicpc.net/problem/1655풀이우선순위 큐 두 개를 활용해서 해결할 수 있다.최대 힙과 최소 힙 두 종류를 각각 만들고, 각각 '작은 수'와 '큰 수'를 저장한다. (두 힙의 이름은 각각 small, big라고 하자.)현재 들어오는 수가 big의 top보다 작거나 같으면 small로 보내고, 아니면 big으로 보낸다.그리고 두 우선순위 큐의 크기(균형)을 맞춰준다. 항상 두 큐의 크기가 같거나, 아니면 small이 하나 더 크게 만들 수 있다.그러면 각 단계에서 small의 top이 정답이 된다. 이게 무슨 소리냐면,예제 1, 5, 2, 10, -99, 7, 5를 예를 들어보자. 1이 들어왔을 때는 다음과 같다. small 1big(답: 1) 5가 들어오면, smal..

https://www.acmicpc.net/problem/24276풀이처음에는 4색문제인가? 하고 생각했는데 문제를 잘 읽어보면 조금 그래프가 특수한 경우라는 것을 알 수 있다.내부에 교차점이 없다!그러면 그래프는 여러 개의 볼록 다각형이(또는 선분이) 변을 맞대고 붙어있는 구조라는 것을 알 수 있고, 조금만 그림을 그려보면 3색으로 충분히 색칠 가능하다는 것을 알 수 있다. 하지만 이 문제는 애드혹, 해 구성하기 없이 그냥 그래프 탐색으로 풀 수 있다. 내가 생각한 첫 번째 알고리즘(틀림)은 이렇다. 1. 1부터 시작해서 2, 3, 4, ... 순서대로 노드를 방문한다.2. 각 노드에서 연결된 다른 노드들의 색깔을 조사하고, 거기에 안 쓰인 가장 작은 색깔로 노드를 색칠한다. 몇 개의 테스트케이스를 해..

오늘은 집합 자료 구조에 대해 배운다.파이썬에서는 보통 set을 이용해서 집합을 만들고, in을 이용해서 O(1) 안에 원소가 있는지 없는지 찾을 수 있었다.C++에서는 어떻게 할까? 셋과 멀티셋C++ 표준 라이브러리에는 경진 프로그래밍에서 자주 쓰는 집합 자료 구조가 두 개 있다. set균형 잡힌 이진 탐색 트리를 기반으로 만들어졌으며, 연산은 O(log n) 시간에 동작한다. unordered_set해시 테이블을 기반으로 만들어졌으며(python 에서 set과 비슷), 연산은 평균적으로(최악의 경우 O(N)) O(1)에 동작한다. 위 둘 다 중복된 원소는 허용하지 않는다. 둘 다 사용법은 비슷하니 set를 통해 예시를 보도록 하겠다. set s;s.insert(3);s.insert(2);s.inser..

스택다음과 같이 쓸 수 있다.#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); stack st; st.push(3); st.push(4); st.pop(); cout 파이썬과의 차이점이 있다면, pop() 연산자는 그 값을 반환하지 않는다. 그냥 말 그대로 pop하고 사라진다. 큐다음과 같이 쓸 수 있다.#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); queue Q; Q...

배열배열은 파이썬과 다르게 선언한 자료형의 값만 저장할 수 있다.인덱스를 통해 값에 바로 접근할 수 있고,새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.배열의 크기는 처음에 생성할 때 지정할 수 있고 이후 못 바꾼다. 구조가 간단하고 빨라서 PS에서 가장 많이 이용된다. 선언하려면 이렇게 하면 된다.int arr[1001]; 아래는 C++17에서는 지원하지 않는 문법인데, 백준 환경이 GCC 어쩌구여서 가능한 간단한 배열 초기화 방법이다.(위처럼 그냥 선언만 해주면 배열 안에 뭐가 들어있을지 모른다)int arr[1001] = {0}; 이렇게 아예 처음부터 초기값을 정할 수도 있다.int arr[3] = {3, 4, 5}; 아래는 내가 파이썬을 쓰면서 유일하게 C++이 부러웠던 점이다...

조건문 기본적인 틀은 이렇다. 파이썬과의 차이점이라고 하면 elif가 없어서 직접 else if라고 해야한다는 것. 그리고 콜론이 없다는 것.괄호 안에는 불리언 타입이 올 수 있다. int a = 3;if (a == 3) { cout switch문 (25.08.04)if 문을 연달아 쓰는 것도 좋지만, C++에서는 다음과 같은 switch 문법을 지원한다.for (int x = 0; x 반복문1. for 문일단, 파이썬에서 가장 많이 썼던 for i in range(N) 구문은 다음과 같다.for (int i = 0; i 보아하니 저 반복문 자체를 define해서 약어처럼 쓰시는 분들도 계시더라. 혹시 파이썬에서 이터레이터를 for문을 통해서 순회했던 것 처럼 C++에서도 배열이나 문자열 등..

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

나는 맥북을 쓴다.맥북의 장점은, 윈도우보다 좋다는 것이다. 그리고 무엇보다, 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..

왜긴 왜야. 겁나게 빠르니까. 어저께 알고리즘 스터디에서 Bulldozer Trick을 배우고 백준 9484 문제를 풀었었다.https://www.acmicpc.net/problem/9484파이썬으로 아무리 열심히 구현을 해도 메모리 초과가 뜨는 것이 아니겠는가. 친구의 말을 들어보니 파이썬으로 풀기 매우매우 어렵다고 한다.일단 알고리즘 자체는 맞는 것 같은데.... 그래서 GPT의 도움을 받아 '내 코드를 C++로 번역해줘' 했다.바로 AC 맞았다. 허망감을 느낀 나는 파이썬을 버리고 이제 C++로 옮기려고 한다. 하지만 나는 C++을 모른다.처음부터 다시 시작해야한다. 같이 배워요, C++.