백준 (7) 썸네일형 리스트형 마작컵 2024 - 우인전 3/4 님만 오면 ㄱ (6솔, C++) 백준의 장점은 가끔씩 씹덕같고 재밌는 문제가 올라온다는 것이고 얘도 그렇다https://www.acmicpc.net/contest/view/927https://www.acmicpc.net/contest/view/938https://www.acmicpc.net/contest/view/939비슷하게 위 대회들도 씹덕같은 문제들이 많아서 좋았고 문제들이 기억에 많이 남는다(난이도는 만만하지 않았다)그건 그렇고 올해는 왜 백준 송년대회랑 신년대회 안열리냐? 인공지능이 발전하고 ps에 관한 관심이 줄어드는 것 같아 아쉽다스코어보드 보면서 얍삽하게 쉬운 문제들만 골라 풀었고 6문제 푸는데 2시간정도 걸렸다6솔 배경과 뱃지를 얻었다https://www.acmicpc.net/problem/33040https://www.. [BOJ 33040, 33041 (조금 어려움)] 마작 거신병 (C++) 개인적인 난이도 :아이디어 - 조금 어려움구현 - 쉬움재미 - 재밌음. 추천해요 https://www.acmicpc.net/problem/33040https://www.acmicpc.net/problem/33041 길이가 W인 수열들 H개로 탑을 쌓아 거신병을 만드는데, 위에 있는 수열의 원소들의 합이 아래에 있는 수열의 원소들의 합보다 크면 안 된다.수열의 원소로는 C개의 1과 D개의 9가 존재하는데, C와 D를 남김없이 써야 한다. 개인적으로는 33041을 먼저 풀고 33040을 나중에 풀었다면 더 쉬웠을 것 같다. 33040의 문제풀이를 주류로 설명하도록 하겠다.기본 아이디어마지막에 for문을 이용해 한 행씩 출력하는데,각 행에는 n개의 9와 W-n개의 1이 포함되어 있을 것이고 원소들이 출력되.. [BOJ 17357, 무난함] 자동차가 차주 김표준의 차를 들면? (C++) solved.ac 마라톤 뛰다가 튀어나왔는데 부동소수점 오차때문에 피똥싼 문제다나같은 사람이 또 있나 궁금해서 구글링해 봤는데 없길래 내가 글을 쓴다https://www.acmicpc.net/problem/17357 이 문제를 풀려면 세가지를 알아야 한다.분산에 대한 지식 (제곱의 평균 - 평균의 제곱)으로 분산을 빠르게 구할 수 있다평균을 빠르게 구하기 위해 누적합을 사용하는 방법부동소수점 오차 줄이기1. 표준편차(분산) 빠르게 구하기표준편차의 제곱은 분산이고, 이 문제에서는 표준편차의 대소비교를 요구하는데표준편차a 표준편차a의제곱 그러니까 표준편차끼리 비교할 필요 없이 분산끼리 비교해도 충분하다.분산의 = 제곱의 평균 - 평균의 제곱 이라는 공식을 활용하면 그나마 빠르게 계산이 가능하다.2. 평균 빠.. [BOJ 27502, 쉬움] 가난한 고흐와 붓 (C++) 개인적인 난이도 쉬움 인터랙티브 문제는 난이도에 비해 solved.ac 티어가 후하게 달리고, 풀면서 재미가 있다 인터랙티브 문제가 처음이라면?? 이거 푸셈 : https://www.acmicpc.net/problem/23306 https://www.acmicpc.net/problem/25907 전략을 잘못 세워서 똑같은 이유로 2번 틀렸다 문제 이해 : 어떻게 하면 고흐를 가난하게(고흐가 붓을 많이 사용하게) 할 수 있을까? 일단 이 문제는 설명만 대충 읽어 보아도, 그래프 문제 같음 근데 몇 가지 경우만 따져봐도 답이 보인다 위 그림처럼 짝수개의 카드와 짝수개의 박스가 있다. 박스에 카드를 최대 한장씩 넣을 수 있고, 모든 카드를 박스에 넣어야 게임이 종료된다. 박스에다가 카드를 이렇게 넣었다고 하면.. 백준 단계별로 풀어보기 - 시간 복잡도 (24262,24263,24264,24265,24267,24313) (C++) 얼마 전에 [백준] - [단계별로 풀어보기] 에 [시간 복잡도] 단계가 추가되었다. 미리 알아야 할 부분) 알고리즘 문제들을 풀다 보면, 시간제한이 빡빡한 문제들이나 주어지는 N의 범위가 매우 큰 문제들이 있다. 이러한 문제들을 풀기 전에 생각을 하고 코드를 짜야 시간 낭비 없이 문제를 풀 수 있다. 시간복잡도를 정확하게 계산할 필요는 없고 우리는 대략적으로 파악한다. 대략적으로만 알아도 충분하다. 그 방법을 Big-O 표기법이라고 하고, 어떤 코드가 작동하면서 계산이 몇번 이루어지는지 다항식으로 표현한 뒤 최고차항의 차수만 따와서 표기하는 것이다. [백준] - [단계별로 풀어보기] - [시간 복잡도] 를 풀어보면, 시간 복잡도를 대략적으로 파악하는 능력을 기를 수 있다. 그래서, 시간복잡도를 대략적으로.. [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연산 수행 횟수가 같아질 때,.. 이전 1 다음
