C++/문제풀이 기록 (21) 썸네일형 리스트형 [BOJ 11444, 약간 쉬움] 피보나치 수 6 (C++) 개인적인 난이도 약간 쉬움 알면 풀고 모르면 못푼다 모르겠어서 아이디어 부분을 구글링하고 구현만 내가 했다 복습) 피보나치 수열을 컴퓨터로 표현하는 방법은 여러 가지가 있다. 1. 재귀함수를 이용해 계산한다 2. dp를 이용해 계산한다 3. (오늘 배울 방법) : 행렬의 거듭제곱을 이용해 계산한다. 1. 기본적인 모듈러 연산의 성질을 알아야 한다. 모듈러 연산의 합/차/곱에 대해 교환법칙과 분배법칙이 성립함을 알고 있으면 된다. 입력과 출력 사이의 과정에서 매우 큰 수를 다뤄야 할 때 자주 나온다. 2. 분할정복을 이용한 거듭제곱을 할 줄 알아야 한다 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A.. [BOJ 25907, 쉬움] 양과 늑대 (C++) 개인적인 난이도 쉬움 인터랙티브 문제가 처음이라면 https://www.acmicpc.net/problem/23306 이 문제를 먼저 풀어보길 바란다 인터랙티브 문제는 머리가 아프지만 실제 난이도에 비해 티어가 높게 잡히는 것 같기도 하고 풀어보면 재미있다. 개꿀임 성공한 풀이) 내가 컴퓨터고 컴퓨터가 사람이라고 생각한 뒤, 이분탐색을 이용해 컴퓨터랑 스무고개를 한다고 생각하면 된다 양의 숫자와 늑대의 숫자가 같아지기 위한 조건은, 어떤 짝수의 날짜 D에 대해 양의 숫자가 정확히 D/2만큼 존재하는 것이다. 우리는 그러한 날짜 D를 찾아내 ! D로 출력하면 된다. 양의 숫자가 D/2보다 많다면, 그 이후에 늑대와 양의 숫자가 같아지는 어떤 날이 존재할 것이다. 양의 숫자가 D/2보다 적다면, 그 이전에 .. [BOJ 27296, 약간 어려움] 카탈란 마스터의 선분 그리기 게임 (C++) 개인적인 난이도 약간 어려움 문제가 정말 안 읽힌다. 카탈란이 뭔지도 모르겠고 처음엔 이게 무슨 어려운 정수론 문제인 줄 알았으나 한참 생각하고나서야 애드혹인걸 알았다 게임 이론 문제에 ->>> 두 명의 플레이어가 모두 자신이 승리하기 위해 최선으로 행동한다면이라는 내용이 들어가면, 상상도 못한 쉬운 답이 나오는 경우가 많은 것 같다. 과거에도 https://www.acmicpc.net/problem/26074 이거 풀면서 그렇게 생각했다. 접근 방법) 점의 개수가 N이라는 정수로 주어졌을 때, N이 커지면서 그릴 수 있는 다각형의 개수는 수없이 많아진다. 그렇지만 이 문제의 조건은 N이 정해졌을 때 선공이 이긴다 또는 후공이 이긴다 의 결과가 딱 1가지만 존재함을 내포하고 있다. 그러므로 우리는 점의 .. [BOJ 1799, 약간 어려움] 비숍 (C++) 개인적인 난이도 약간 어려움 실패한 풀이) 체스판에서 대각선을 체크하면서 말을 놓는 백트래킹의 구현은 그렇게 어렵지 않으나, 그냥 백트래킹하면 시간초과가 나게 되는 문제이다. 약간의 아이디어로 시간복잡도를 크게 줄일 수 있다. 안되는 이유 최악의 경우, 10*10 의 배열의 모든 칸에 비숍을 배치할 수 있다 검사할 칸의 개수 100개 -> 백트래킹 없이 완전탐색할 경우 2^100~=1e30 대략 1e22초 소요 백트래킹으로 탐색하며 비숍을 배치할 수 있는 위치에만 비숍을 배치한다고 해도 시간초과가 난다. 그 이유는 이러하다. 10*10 크기의 2차원 배열의 경우 20+20 개의 대각선을 그릴 수 있다. 인정?? 인정~ 비숍을 어느 한 위치에 놓을때마다 우상향 방향 대각선 1개와 좌상향 방향 대각선 1개에.. [BOJ 1629, 쉬움] 곱셈 (C++) 개인적인 난이도 쉬움 알면 1분만에 풀고 모르면 그냥 틀린다 매우 중요한 개념이 2 가지 들어있다. 정수론(모듈러 산술) & 분할정복(log N) 몰라서 2번 틀렸다 처음엔 정수론 몰라서 오버플로우로 틀리고 두번째엔 분할정복 몰라서 시간초과로 틀림 성공한 풀이) 핵심 1) 모듈러연산은 신기하게 덧셈 뺄셈 곱셈 분배법칙이 가능하다. 핵심 2) 거듭제곱 계산(pow) 는 분할정복을 이용해 계산하면 log N 안에 끝남 성공한 코드 #include #define fastio cin.tie(0)->sync_with_stdio(0) #define ll long long using namespace std; int main(void) { fastio; ll A,B,C;cin>>A>>B>>C; A%=C; ll ans.. [BOJ 27231, 약간 어려움] 2023년이 기대되는 이유 (C++) 개인적인 난이도 약간 어려움 정석 풀이는 아마 백트래킹으로 문자열 중간에 +를 삽입하는 것이다 근데그냥 브루트포스로 풀어도 풀린다 난 백트래킹 말고 그냥 set 반환하는 재귀함수 만들어서 브루트포스로 풀었다 재귀는 항상 어렵다 dp문제를 풀때도 항상 느끼지만 어떤 연산을 절차적으로 생각하는 건 익숙하지가 않다 그래서 한참 걸려서 풀었다 1시간정도걸림 수련이 부족하다 성공한 풀이) 성공한 코드 #include #define fastio cin.tie(0)->sync_with_stdio(0) #define ll long long using namespace std; ll pow(int a,int b){ if(a==0)return 0; if(a==1)return 1; if(b==0)return 1; retur.. [BOJ 7662, 어려움] 이중 우선순위 큐 (C++) 개인적인 난이도 어려움 생각대로 안돼서 개고생함 이게 왜 골드 4인지 모르겠다 알다시피 priority_queue는 heap으로 구현되어 있고 출력이 최상위 루트를 통해 이루어짐 heapify() 1번의 시간복잡도는 log(N). 입출력시 heapify가 이루어짐 이 문제의 제목을 통해 우선순위 큐 2개를 이용해 푸는 것이라고 짐작할 수 있음 최댓값, 최솟값을 출력해야 하므로, max heap 1개와 min heap 1개를 쓰면 된다고 짐작할 수 있음 그렇다면 입력은 2개의 힙 모두에 이루어질 것이고 출력은 둘 중 하나의 힙에서만 이루어질 것이다~ 그렇다면 두 힙의 동기화가 이 문제의 관건일 것이다~ 라고 짐작할 수 있음 실패한 풀이) insert연산 수행 횟수와 delete연산 수행 횟수가 같아질 때,.. [BOJ 5893, 약간 쉬움] 17배 (C++) 개인적인 난이도 약간 쉬움 난이도에 비해 구현이 어려운 문제임 입력의 크기가 C++의 long long 범위를 벗어나는 경우, C나 C++로는 구현이 어려워진다 vector나 string의 무한 길이의 자료형을 사용해 구현해야 한다. (또는 bigint를 사용해 구현해야 한다고 하는데 안해봤다) C++ 대신 입력의 크기 제한이 없는 파이썬으로 풀면 매우 쉽게 풀리는 문제이고, 그래서인지 난이도가 브론즈 4로 잡혀 있다 [BOJ 10757번: 큰수 A+B] 얘도 비슷하게 파이썬으로 풀면 코드 세줄로 끝나는데 C++로는 1000B정도 작성해야 풀린다 풀이) 숫자 25를 17배한다고 생각해 보자. 25*17 = 25*(16 + 1) = 25*16 + 25 와 동일하다. 25는 이진수로 11001이다 이걸 2배.. [BOJ 25398, 고민중] 트리와 집합과 쿼리 개인적인 난이도 안풀어도되는데굳이고민중 안풀어도되고 난이도도 어렵고 백준 골드따리가 건들필요도 없고 풀어도 도움 안 될 거 같은 문제인데 수학 대학원에서 그래프를 공부중인 (ps는 해본적 없는)친구가 갑자기 문제랑 아이디어를 주길래 고민중이다 이런 문제는 친구네 업계에선 안 어려운 문제라고 함 아이디어가 어려운 문제라면 구현은 쉽지 않을까? 라고 생각해서 도전해보려고 한다 그냥 해본 추측 쿼리가 엮였으니까 세그먼트 트리를 쓰지 않을까 시간내에 안되면 어려운 최적화가 필요하지 않을까 백트래킹으론 안풀리는 문제인가 친구 말 요약 트리 위에서 A에서 B로 순차적으로 돌을 옮기는 게 가능한지를 묻고 있음 아무거나 루트를 하나 잡고 리프를 레벨 0이라고 하면 A에서 가장 레벨이 낮은 B의 점으로 갈 수 있는지를 .. [BOJ 24525, 어려움] SKK문자열 (C++) 개인적인 난이도 어려움 시간많이걸렸다 누적합인거 늦게라도 알아서 풀었지 몰랐으면 못풀었을 것 같다 아이디어가 좋은 문제 같다 실패한 풀이 1) 8개월 전에 한거라 왜 이렇게 했는지도 모르겠다 일단 이때는 누적합 아이디어가 없었음 원형 큐를 이용해 풀이를 시도했다 원형 큐를 이용한다면 S1개 K2개인 경우는 찾아낼 수 있을지도 모르겠으나 K가 S개수의 2배가 되는 경우(문제의 조건)을 찾아낼 수 없다 문제를 잘못 읽었나 보다 아래의 코드는 그냥 보지 마라 실패 코드 //BOJ 24525 SKK문자열 //2022-05-02 #include #include #include using namespace std; int qq[3] = {-2,-2,-2}; // S=1와 K=0의 원형 큐 int qp = 0; //.. 이전 1 2 3 다음
