노는 게 제일 좋아

재귀나 숫자 범위에 대해 기본적인 문제 좋은 것 같다. https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 음.. 처음 봤을 때 당황 많이했다. int, 4바이트 long long 8바이트 재귀함수까지... 재귀함수는 항상 그게 중요하다. 점화식을 찾는 것... 1번, n번 n+1번까지의 식만 찾으면 굿 맞는 풀이( 틀린 풀이도 집어넣어놨다.) #include using namespace std; using ll = long long; ll remain(ll a, ll b, ll c){ //n = 1일 때 if(..

간단한 산수문제다. 메모리제한 256이 아니라 512네? 우선 두고보자 https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 시간 5분이나 더 썼다. 1,000,000 * 1,000,000 는... 우선 21억을 넘어간다. ㅎㅎ int형으로는 불가능 long long으로 쓰자. 64비트다. int는 32 비트다. 2^32배 더 큰 수를 표현할 수 있다. 21억 * 21억 하면 되겠다. # 맞는..

구현하라는 대로 그냥 구현만 해주는 문제다. 메모리가 아주 적다. https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 문제 범위가 0부터면 쉽겠는데..? 역시 문제를 어렵게 하려면 입력을 드럽게 주면 된다. 하지만 우리가 중요한 것은 연도다. 연도는 해가 한 바퀴 도는 것이 중요하지 연도가 중요하진 않다. 다같이 -1을 해주자 # 맞는 풀이 #include using namespace std; int main(){ int E,S,M; int e,s,m;..

// 2022.02.27 다시 품 어려운 문제는 아닌데.. 정확하게 시키는대로 하는 것이 어렵다. 아니.. 하는 것이 어려운 것보다 우리가 짜는 알고리즘이 어떻게 진행될 지 정확하게 알아야 한다는 것이 포인트다. https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 큐를 이용하는 것 같지만. 여기서 중요한 조건이 뒤에 문서를 확인해야한다는 말이 있다. 즉, 탐색이 가능해야한다는 것이다. 스택, 큐는 전체 탐색이 불가능하다. 그렇게 만들어졌다. 때문에 전..

메모리 heap에 생성되며 동적할당이 가능하여 동적 배열을 대체할 수 있는 std:: 를 알아보자 C++ STL 에서 컨테이너는 크게 두 가지 종류가 있다. 배열 처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너 (sequence container) 키를 바탕으로 대응되는 값을 찾아주는 연관 컨테이너 (associative container) 가 있다. 우리가 알아볼 벡터는 시퀀스 컨테이너다. 벡터에는 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있고 따라서 임의의 위치에 있는 원소를 접근하는 것을 매우 빠르게 수행할 수 있다. 하지만 벡터가 만능인줄 알고 있는 사람들도 있지만 그렇지 않다. 맨 뒤에 원소를 추가하거나 제거하는 것은 빠르지만 임의의 위치에 원소를 추가하거나 제거하는 것은 O(n) 으..

이 문제도 BFS의 기본적인 문제라고 볼 수 있지만 역시나 BFS를 어렵게 하려면 입력을 이상하게 주면 된다. https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 이번 풀이의 핵심은 BFS가 아니다. 문제에서 이 사각형의 넓이를 무엇으로 구할 것이냐? 가 문제다. 또한 주어진 조건에 대해서 어떻게 예외처리를 할 것이냐? 가 문제다. 우리가 지금 노드의 개수와 사각형의 개수가 1:1 대응하는가? 꼭짓점이 노드라고 한다면 8 * 6..

뭐 이것도 BFS의 기본문제라고 볼 수 있겠다 다만 이건 입력을 특이하게 받는 케이스? 라고 보면 된다. https://www.acmicpc.net/problem/1012 #맞는 풀이 하지만 정제되지 않음 손에 익지 않아서 20분정도 걸림 주석포함 솔직히 다른 사람은 어떻게 그렇게 정제된 풀이가 바로 생각나는거지??... 아직 갈 길이 멀다. #include #include #include #define X first #define Y second using namespace std; int tc; int dx[4] = { -1,0,1,0 }; int dy[4] = { 0,1,0,-1 }; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> tc; //t..

BFS의 응용문제로 BFS라고 생각지 않지만 의외로 BFS라서 놀라는 초보인 나에게는 놀라움의 대상이었던 문제다. https://www.acmicpc.net/problem/1697 이 문제도 내가 풀긴 풀었지만 왠지 더 잘 풀수 있을 것 같다. #1 뭔가 틀린 풀이 #include #include #include using namespace std; int dist[100001]; // 0 m >> n; queue Q; fill(dist, dist+100000, -1); // 0~ 100000까지 -1 dist[m] = 0; Q.push(m); while(!Q.empty()){ int cur = Q.front(); Q.pop(); if(cur-1 >= 0 && dist[cur-1] < 0){ dist[c..

이전 글에서 다루지 못했던 작업 증명과 지분 증명을 알아보자. 앞서 public에서 원활하게 합의에 이를 수 있었던 이유는 이익이 커지는 방향으로 행동한다는 가정때문이었다. 보상으로 암호화폐를 제공해서 그렇다고 말했다. 그렇지만 작은 이익을 포기하고 큰 조작을 하려는 무리들이 있기 마련이다. 항상 가정에는 예외가 있는 법 public 환경에서는 항상 그런 무리들이 존재하기 마련이다. 그래서 블록체인에서는 이전에 말한 비잔티움 장애를 이용하여 합의 형성을 이끌어내는 과정을 적용하려고 한다. BFT 알고리즘이라고 한다. ++ Bizantine Fault Tolerance의 약자다 퍼블릭 체인의 대표적인 비트코인은 위 알고리즘을 적용하여 합의를 잘 이끌어내고 있다. ??? BFT가 뭔데라고 할 수 있다. BF..

BFS의 응용문제다. 어렵진 않지만 응용하는 첫번째 단계라고 할 수 있다. www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제도 BFS를 이용한다는 감이 온다. 고려해야 할 조건이 몇가지 있다. 1. 지훈이의 탈출 조건 2. 불이 있는 곳에 지훈이 있을 수 없다. 우선 지훈이는 문제에서 가장자리에 있으면 탈출 할 수 있다. 즉, [ i ][ j ] 위치에서 i 또는 j 가 0을 가지거나 최댓값을 가지면 탈출한 것이다. -> 다시 말해서 가..