본문 바로가기

C++18

[백준] 2150번: Strongly Connected Component (타잔 알고리즘) | C++ 2150번: Strongly Connected Component첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정www.acmicpc.net 정답코드타잔 알고리즘은 크게 세 가지 경우로 나뉜다. 1. 아직 방문하지 않은 노드 → 방문한다. 2. 방문했지만 SCC가 아직 아닌 노드 → id값이 더 작은 걸 저장한다. 3. 방문했고 SCC가 형성된 노드 → through 한다. 이런 경우를 거치고 현재 노드(id[cur]) id값과 저장된(remember) id 값이 같으면 스택에서 현재 노드를 만날 때까지 pop한다. 2번, 3번 경.. 2023. 6. 4.
[기하] C++의 복소수 클래스 complex 기하 문제를 풀 때 c++의 복소수 클래스 complex를 사용할 수 있다. 이 클래스를 이용하면 점과 벡터를 복소수 형태로 표현할 수 있고, 클래스의 기능을 이용하여 점과 벡터를 다룰 수도 있다. typedef long long C; // 정수 좌표를 써도 되는 경우 // typedef long double C; // 정수 좌표를 쓸 수 없는 경우 typedef complex P; #define X real() #define Y imag() 정수 계산이 정확하기 때문에 정수좌표를 사용하는 것을 권장한다. 함수 complex 클래스에는 기하 문제를 풀 때 활용할 수 있는 함수를 제공한다. long double 자료형임을 주의하자. abs(v) 벡터 v={x, y}의 길이를 계산하는 함수이다. sqrt(x.. 2023. 6. 1.
[백준] 2957번: 이진 탐색 트리, 1539번: 이진 검색 트리 | C++ 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 1539번: 이진 검색 트리 P는 크기가 N인 배열이다. P에는 0보다 크거나 같고, N-1보다 작거나 같은 정수가 중복 없이 채워져 있다. 이진 검색 트리는 루트가 있는 이진 트리로, 각각의 노드에 정수 값이 저장되어 있는 트 www.acmicpc.net 거의 같은 문제! 틀린 이유 처음에 2957번 문제를 풀 때 그냥 BST를 구현했었다. #include #include #include #define MAX 100000 #define fse(A,B,C).. 2023. 5. 27.
[백준] 2887번: 행성 터널 | C++ https://www.acmicpc.net/problem/2887 2887번: 행성 터널첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이www.acmicpc.net 접근방법1. MST문제다. union-find 써야 할 것 2. 모든 행성 간 가중치를 구하려면 N! 인데? 3. 행성 간 가중치는 행성 간 3차원 거리가 아니라 min(|xA-xB|, |yA-yB|, |zA-zB|) 이다. 4. x, y, z 대로 정렬 3번 수행하고 인접한 행성의 거리를 구한다. 5. 힙에 넣어 가중치 최솟값을 구한다면? 라고 생각회로 거쳤다. 정렬.. 2023. 5. 22.
[C++] 람다식 (feat. 2887 행성 터널) https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 해당 문제를 풀면서 정렬을 세 번 수행해야 하는데 C++로 람다식 어떻게 쓰나 찾아보고 쓴다. >>> 행성터널 풀이 2023.05.22 - [Computer Science/Problem Solving] - [백준] 2887번: 행성 터널 | C++ [백준] 2887번: 행성 터널 | C++ https://www.acmicpc.net/problem/2887 2887번.. 2023. 5. 20.
[C++] pow함수 double 형의 정확성 문제 https://www.acmicpc.net/problem/1740 1740번: 거듭제곱 3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다. 이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 수를 생각할 수 있다. 예를 www.acmicpc.net 해당 문제를 풀다가 발견한 문제.. 분명 로직은 맞는데 어디서 틀린건지? 으잉? 분명 (맨앞) 1비트씩 차이나는데 왜 pow로 곱한 값은 같은 거지????? 문제를 발견하고 뒤적이기 시작했다. 아..하.. 실수 연산의 차이... 부동소수점.... 2023. 4. 30.
[C++] vector.size()는 unsigned 이다. vector v의 사이즈가 4이고 k가 10일 때 (v.size() - k > 0) 조건이 계속 참이 나왔다. 왜 그러나 (v.size() - k) 를 콘솔에 찍어보니 쓰레기 값이 나왔다..... 쓰레기 값을 30초 들여다보니 아차 싶더라. v.size() 는 양수만 취급한다.size가 음수일리는 없으니 signed 자료형으로 개발했나보다. C만든 사람들 꽤나 직관적이다. unsigned : 양수만 표현 가능 (0 ~ 2^32-1) signed : 맨 앞 비트로 양수/음수를 분별한다. (-2^31 ~ 2^31-1) signed int가 기본형이라 너무 당연하게 v.size()가 음수 표현이 안 될 것이란 생각을 못했다. 바보.......... 2023. 3. 24.
[C++] 달팽이 알고리즘 정방향 행렬에서 시계 방향으로 탐색 시 N, N-1, N-1, N-2, N-2, ... , 2, 2, 1,1 순서로 값이 채워지는 규칙이 있다. 이 규칙을 이용하면 코드 축약에 도움을 준다. sign 을 사용하는 것은 x가 증가하는 쪽으로 변화하면 다음 y는 감소하는 쪽으로 변화하고, 반대로 y가 증가하면 x는 감소하기 때문이다. int size=N*N-1, sign=1; int x=0,y=0; // 초기 N번 한 번 for(int i(0) ; i0 ; i--){ for(int j(0) ; j 2023. 3. 22.

티스토리툴바